7
$\begingroup$

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.

$\endgroup$
  • 6
    $\begingroup$ Why can you take $p-1,q-1$? They might not be natural numbers. For instance, $\max (1,2)=2$. $\endgroup$ – lulu Jan 26 at 22:54
  • 1
    $\begingroup$ This depends on whether you include $0$ in $\mathbf N$ or not. $\endgroup$ – Bernard Jan 26 at 22:55
  • $\begingroup$ Lulu's answer below is excellent; I just want to point out that the tactic they used is exactly the right way to identify errors in induction proofs - instead of thinking about arbitrary choices of $n$, think specifically about the first few steps. Usually, if an induction proof is going to break down, it'll break down dramatically and clearly in those early steps. $\endgroup$ – Reese Jan 27 at 2:22
  • $\begingroup$ I'd add to the comment by @Reese that the place to look for an error in an induction proof is the smallest numbers where the alleged conclusion is wrong. In the case at hand, that would be where $n=2$ and $\{p,q\}=\{1,2\}$. $\endgroup$ – Andreas Blass Jan 27 at 4:15
  • $\begingroup$ @WaveX: $\Bbb N$ conventionally includes $0$. $\Bbb N$ with $0$ removed is noted $\Bbb N^*$. $\endgroup$ – fgrieu Jan 27 at 8:35
13
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Going by the logic this approach would also work if we did include $0$ in our definition of $\mathbb{N}$. Then we would be looking at $\max (-1,0)$ and once again we fall out of $\mathbb{N}$, am I correct? $\endgroup$ – WaveX Jan 26 at 22:58
  • 2
    $\begingroup$ Exactly right. We'd have $\max (a,b)=0\implies a=b=0$ but you couldn't do the induction, as the example $\max (0,1)=1$ demonstrates. $\endgroup$ – lulu Jan 26 at 22:58
  • $\begingroup$ For what it's worth, this is a nice pattern to know. Basically all absurd fake proofs by induction rely on the 1->2 step being invalid by virtue of something wrong happening when you plug 1 in. $\endgroup$ – R.. Jan 27 at 3:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.