This fallacy is given in Bartle's Introduction to Real Analysis (page 15) and I am trying to figure out where the problem is in the "fake proof".
Here we are using $\mathbb{N} = \{1,2,3 \dots \} $
If $n \in \mathbb{N}$ and if $\max (p,q) = n $ for $p,q \in \mathbb{N}$, then $p=q$
The base case $n=1$ does check out. If $\max (p,q) = 1$, then we do have that $p=q$ since $p,q \in \mathbb{N}$.
Then we assume the statement is true for $k \ge 1$ and we want to prove the statement is true for $k+1$.
Suppose $\max (p,q) = k+1$. Then we have $\max (p-1, q-1) = k$. Thus, we have $p-1 = q-1 \implies p=q $ $\tag*{$\square$}$
Obviously this is an absurd statement, as this is not true in general. It is clear that the base case is correct, so the flaw must be somewhere in the induction step.
My only guess is that it stems from saying $\max(p-1,q-1) = k$ and that somehow we have a subtle violation going on. I would like to be able to clearly see the violation. Any help would be greatly appreciated.
Best Answer
The problem is that $p-1,q-1$ might not be in $\mathbb N$. For instance, consider $\max (1,2)=2$ . The induction would direct us to look at $\max(0,1)=1$ but that was not covered in the base case.
Note: if we considered $0$ as a natural number then the base case is false as presented (since $\max (0,1)=1$ is a counterexample). Of course, we could consider the base case $n=0$ and that would still be correct.