Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I saw the following "theorem" and its "proof".

I can't explain well why the argument is wrong. Could you give me clear explanation so that kids can understand.

Theorem: All natural numbers are equal. Let $a, b \in \mathbb{N}$, then a=b.

Proof by induction.
Let $m=\max\{a, b\}$. We will prove that the theorem holds for all $m\in \mathbb{N}$.
If $m=1$, then $\max\{a,b\}=1$, so $a=b=1$.

Now assume that it holds for $m=k$ for some number $k$.
Now let $\max\{a, b\}=k+1$. Then $\max\{a-1, b-1\}=k$ and thus by assumption $a-1=b-1$, so $a=b$.

Therefore, the proof is complete.

share|improve this question
3  
To use m = 1 is a bad idea, since this is a one case scenario (there's only one natural in the set {1}). If k > 1, then, after max {a,b} = k, why do you assume that a - 1 = b - 1? –  Francisco Presencia Mar 27 '13 at 5:36
3  
Just a comment on the form: since your theorem does not mention $m$, it is pointless to say the theorem holds for all $m$. What you mean is "Proof by induction on $\max(a,b)$". In general it is good to always let "by induction" be followed by "on [something]". –  Marc van Leeuwen Mar 27 '13 at 9:03
7  
All natural numbers are equal, but some natural numbers are more equal than others. –  Asaf Karagila Mar 27 '13 at 13:27
6  
...but some numbers are more equal than others. –  knutole Mar 27 '13 at 13:50
3  
en.wikipedia.org/wiki/All_horses_are_the_same_color has a similar idea for where it goes wrong that may be useful here. –  JB King Mar 27 '13 at 18:01
show 1 more comment

12 Answers

The error lies in the fact that when decreasing $1$ you may get out of the set $\mathbb{N}$ - and indeed, $\max\{1,2\}=\max\{0,1\}+1$, but $0 \ne 1$, and $0\notin \mathbb{N}$ as you defined it.

share|improve this answer
    
But what would be wrong, if the proof did not target N but Z ?! Then the proof would still not be right & it would be possible to decrease 1... –  Lucian Depold Mar 27 '13 at 15:38
17  
@LucianDepold if the numbers were in $\mathbb{Z}$, you wouldn't be able to provide a base case... –  Alfonso Fernandez Mar 27 '13 at 15:45
    
you are right ! –  Lucian Depold Mar 27 '13 at 15:47
    
All of this is false. You can make a minor modification to the "proof" which leaves it just as obtuse, but avoids this issue. For instance, suppose it says `Now let $max(a+1,b+1) = k+1$. Then $max(a, b) = k$, and by the assumption, $a = b$. Look, even shorter! –  Kaz Mar 28 '13 at 1:11
5  
@Kaz That's still the same mistake: you can't assume that two natural numbers can be written as $a+1,b+1$ where $a,b$ are natural. Namely, it fails for $(a+1,b+1)=(1,2)$. –  Alfonso Fernandez Mar 28 '13 at 2:15
add comment

The problem starts with this sentence:

Now assume that it holds for $m = k$ for some number $k$.

Assume that what holds for some $k$? What is the it that is to be assumed holds?

If $max(a, b) = k$, it means that either

  • $a = k \cap 1 \le b \lt k$; or
  • $b = k \cap 1 \le a \lt k$; or
  • $a = b = k$.

In the special case $k = 1$, the first two cases are ruled out, but they are not ruled out when $k > 1$. So what the proof is assuming true for any $k$ is just the third case:

  • $max(a, b) = k \implies a = b = k$

So this is basically a case of incomplete case analysis: conveniently ignoring cases in the general truth, because they do not occur in the base case, and simply proceeding from the base case via induction without further considering the missing cases.

Another issue with the proof is that it only argues for the equality of the variables $a = b$. This conclusion does not permit us to believe that all numbers are equal. For that, it would be necessary to prove something like $a = a - 1$, for any $a$, which then connects with the base case $a = 1$. To goal of the proof should be to show that any two arbitrarily chosen natural numbers $a$ and $b$ are equal. But in the proof, $a$ and $b$ are anything but independent of each other, or of the parameter $k$.

For the proof to even try to show that the numbers are equal, what it requires us to believe is not simply that $a = b = k$ for an arbitrary $k$, but in fact that literally the original base relation holds for arbitrary $k$. Namely that $max(a, b) = k \implies a = b = 1$ just like in the base case where $k = m = 1$. This is actually the it which is to be assumed. But of course, that just begs the question! If we simply assume that all numbers are equal to 1, then of course they are all equal, Q.E.D.

The proof obfuscates its poor logic by actually not stating it, and alluding to it via the pronoun it which has no clear antecedent. It makes an overture which hints at an inductive structure (base case, inductive step) and hopes that the reader's mind will somehow blunder in trying to connect the pieces.

One more flaw is this use of $a$ and $b$ as distractors to obfuscate vacuous truths. In induction along a single discrete variable, we have some logical proposition $P(n)$ which we show to be true for some base cases, for example showing that $P(1)$ is true. Then we show that the inductive hypothesis is true: namely $P(k)\implies P(k + 1)$. The statement $P$ consists of some equation which involves only functions of $k$, and no other independent variables. If symbols other than $k$ appear, they are either constants, or functions of $k$ (dependent variables). In our proof, the variables $a$ and $b$ are such functions of $k$. In fact, it is assumed that $a = b = k$. So $max(a, b) = k$ really means $max(k, k) = k$, and $a = b$ just means $k = k$.

share|improve this answer
    
+1, very good explanation. The second case should be $b = k \cap 1 \le a \lt k$. –  Leo Mar 27 '13 at 14:26
    
I don't agree. What the induction step is assuming is that whenever $a,b\in\Bbb N$ and $\max(a,b)=k$ then (it has been proven that) $a=b$. Now to prove the same for $a',b'\in\Bbb n$ with $\max(a',b')=k+1$, it tries to apply the indiction hypothesis for $a=a'-1$ and $b=b'-1$. There is no case analysis. The only error is that the proof forgets the necessary check of the condition $a,b\in\Bbb N$ of the induction hypothesis, which of cours cannot be ensured. –  Marc van Leeuwen Mar 27 '13 at 18:01
    
@MarcVanLeeuwen Ha, I was just revising the answer as you wrote your comment. The poor case analysis is a flaw, but not really the smoking gun. –  Kaz Mar 27 '13 at 18:37
2  
This deserves more upvotes!!! –  Pedro Tamaroff Mar 28 '13 at 5:34
add comment

Hint:

The smallest case where your "theorem" is obviously wrong is the set $\{1,2\}$. Now check every step of the "proof" with this example. What goes wrong?

share|improve this answer
add comment

It's true that $a-1$ and $b-1$ may not be in the naturals, but what this fact is really getting at is that you don't have enough initial conditions. The argument is phrased to hide this. Instead of writing the claim as: $$\forall a, \forall b\le a,a = b = \max\{a,b\}$$ which shows that we have to induct over $a$, and then within this, induct over $b$, or perhaps as, $$\forall (a,b)\in \mathbb{N}\times\mathbb{N}, a = b = \max\{a,b\} $$ which would require us to impose an ordering on $\mathbb{N} \times \mathbb{N}$ and induct along this ordering, it is written as: $$\forall m, m = \max\{a,b\}, m = a = b$$ Which hides the quantifiers on $a$ and $b$ (namely, ex. $\forall a,b \le m$).

share|improve this answer
add comment

One obvious problem is that $a-1$ or $b-1$ might be zero. So for $m = 2 $ you have for example $2 = \max\{1,2\}$ and $1 = \max\{0,1\}$.

share|improve this answer
add comment

Sneaky induction proofs always fail in the same way (or at least all the ones I've seen do): the induction step doesn't apply to the base case. When you say, "assume the theorem holds for $m$", you naturally think of $m$ as arbitrary, and hence moderately large. But $m$ is any natural number, so you have to check all of them.

This is very similar to the inductive every horse is the same color proof (in fact, it's probably just the same "proof" reworded in terms of natural numbers). In that proof, there is the same fallacy: the induction step does not apply to the base case (if you take two distinct $2 - 1$ element subsets of a $2$ element set, they do not intersect).

share|improve this answer
    
No, in this proof every instance of the induction step fails, as the lesser of $a,b$ can always be $1$, no matter what value $\max(a,b)$ has. And antyway saying "the induction step doesn't apply to the base case" is not precise, as the base case and the induction step are disjoint (and almost in all correct induction proofs the induction step must use somewhere that this is not the base case). You mean the smallest instance of the induction step, just beyond the base case. –  Marc van Leeuwen Mar 27 '13 at 18:14
add comment

Hint $\ $ Here is a constructive viewpoint. We use $\,0\,$ vs. $\,1\,$ as base case. Suppose we have a natural number computer that has no subtraction operation, but does have a decrement operation. Then we can reduce equality testing of naturals to zero testing, by implementing a recursive algorithm that continually decrements both numbers $\rm\ a= b \!\iff\! a\!-\!1 = b\!-\!1\!\iff\! a\!-\!2 = b\!-\!2\!\iff\cdots\:$ till we reach the "base" case where one is zero; then we test if the other is zero using the zero-test operation. Notice that the algorithm terminates in "base" cases of the form $\rm\:n = 0\:$ or $\rm\: 0 = n,\:$ not in a single base case $\rm\: 0 = 0.\:$ The given "proof" can be viewed as an implementation of this algorithm, presuming that the recursion always terminates in the single base case $\,0 = 0\,$ (or $1 =1$ using $\rm\,n=1\,$ as base case). If that were true, then the equality test would indeed always return true.

share|improve this answer
add comment

"Then max{a−1,b−1}=k and thus by assumption a−1=b−1"
This seems to be the problem in the explanation
By which assumption should these be equal?
The only prior statement that talks about the arguments to max{ } being equal is when k = 1, and that is a specific case and not for any general value
Also, this might be related

share|improve this answer
add comment

If all natural numbers were equal, then for $m=1$, $a=b=1$ but for $m=2$ there have to be some numbers that are greater than $1$! Therefore not all numbers are equal! The induction itself uses natural numbers, that differ from each other. $m=1$ differs from the value $m=2$ ! And with that we try to prove that they don't differ !

share|improve this answer
2  
The question was not if all natural numbers are equal, but why the given proof for this (obviously wrong) statement is incorrect. –  azimut Mar 27 '13 at 15:26
    
yes i know. the the induction step from m=1 to m=2 contains already the contradiction, i wanted to point that out –  Lucian Depold Mar 27 '13 at 15:29
add comment

If $m=2$ then, following your demonstration we have $m=\max\{a,b\}\Rightarrow \max\{a-1,b-1\}=1\Rightarrow a-1=b-1\Rightarrow a=b=2$. So $a$ and $b$ MOST be equal 2. So in general this will only works when $a=b$. That's the error, when $a\neq b$ it just won't work.

share|improve this answer
add comment

the first assumption was $m=k$ or $\max(a,b)=k$, but the theory is letting $\max(a,b)=k+1$ meaning "$\max(a,b)=\max(a,b)+1$" which drives the proof wrong!

share|improve this answer
    
The theory does contradict the assumption: we proceed by induction. And the assumption is the privious step, not an assumption in the next step. –  awllower Mar 27 '13 at 12:19
add comment

If m=1, yes. If m=any other number, no. The proof fails at that point. There's no need to go any further by introducing k.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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