All natural numbers are equal.

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.

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

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

Solution 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?

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