All natural numbers are equal.

Question

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.

Answer 1

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.

Answer 2

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$.

Answer 3

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?

Answer 4

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$).

Answer 5

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\}$.

Answer 6

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.

Answer 7

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).

Answer 8

"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

Answer 9

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 !

Answer 10

First, let's recap how mathematical induction works. To prove a statement $\Phi(n, \vec{w})$, where $n \in \mathbb{N}$ is the induction variable and $\vec{w}$ are any additional parameters, we need two things:

1. base step: $\forall \vec{w}: \Phi(1, \vec{w})$ holds.
2. inductive step: $\forall \vec{w} \; \forall n \in \mathbb{N} : \Phi(n, \vec{w}) \rightarrow \Phi(n + 1, \vec{w})$ holds.

Now, let's have a look at the inductive step in the proof:

$$ \forall a \in \mathbb{N} \; \forall b \in \mathbb{N} \; \forall n \in \mathbb{N} [(\max(a - 1,b - 1) = n \rightarrow a - 1 = b - 1) \rightarrow (\max(a, b) = n + 1 \rightarrow a = b)] $$

This is actually a true statement, but there are pathological cases when $a -1 < 1$ and $b - 1 < 1$. However, we can easily fix it by adding $1$:

$$ \forall a \in \mathbb{N} \; \forall b \in \mathbb{N} \; \forall n \in \mathbb{N} [(\max(a ,b) = n \rightarrow a = b) \rightarrow (\max(a + 1, b + 1) = n + 1 \rightarrow a + 1 = b + 1)] $$

Yet again, this is a true statement and without any pathological cases. We can validate the base case and surely enough, it is true. Does it mean the proof is correct after all?

We have one more hurdle to clear. We need to check that the inductive step has the correct form mandated by mathematical induction. Namely, let's extract $\Phi(n, \vec{w})$. One option is:

$$ \Phi(n, \vec{w}) \equiv \Phi(n, a, b) \equiv \max(a ,b) = n \rightarrow a = b $$

Let's plug that back into the inductive step prescription and check that we get the exact same inductive step as was proposed:

$$ \forall a \in \mathbb{N} \forall b \in \mathbb{N} \forall n \in \mathbb{N} [(\max(a,b) = n \rightarrow a = b) \rightarrow (\max(a, b) = n + 1 \rightarrow a = b)] $$

But wait, that's not quite the same thing as was proposed! Maybe we've just used the wrong formula, let's try the other option:

$$ \Phi(n, \vec{w}) \equiv \Phi(n, a, b) \equiv \max(a + 1 ,b + 1) = n + 1 \rightarrow a + 1 = b + 1 $$

Oh no, that's not working either:

$$ \forall a \in \mathbb{N} \forall b \in \mathbb{N} \forall n \in \mathbb{N} [(\max(a + 1,b + 1) = n + 1 \rightarrow a = b) \rightarrow \\ (\max(a + 1, b + 1) = n + 2 \rightarrow a + 1 = b + 1)] $$

So the problem here is that the original proof is not using mathematical induction correctly and hence we can rule it out.

However, let's see if the theorem still holds with the corrected inductive step. And it is easily seen that with the right combination of parameters, it does not. If we put $n=1$, $a=1$, $b=2$, this is true:

$$ max(1,2) = 1 \rightarrow 1=2 $$

but this is false:

$$ max(1,2) = 2 \rightarrow 1=2 $$

This rules out the corrected inductive step as well.

Answer 11

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.

Answer 12

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!