Questions about the proof: "all positive integers are equal"

Question

Others have expressed confusion about this proof on Stack and I have looked through every one of them because I don't want to post a duplicate post, however, none of them answer the questions I have and I am still confused.

So we have to find what is wrong with this proof:

We introduce the following notation, for positive integers $x$ and $y$:

$$\text{max}(x, y) = {x \space \text{if}\space x \ge y, y \space \text{if}\space x < y}$$

What is wrong with the following “proof by induction”?

“Theorem:” For every positive integer $n$, if $x$ and $y$ are positive integers with $max(x, y)$ = $n$,then $x = y$.

Basis step: If $max(x, y) = 1$ and $x$ and $y$ are positive integers, then we have $x = 1$ and $y = 1$.

Inductive step:

Let $k$ be a positive integer, and assume that whenever $max(x, y) = k$ and $x$ and $y$ are positive integers, then $x = y$ (this is the IH). Now let $\text{max} (x, y) = k+1$, where $x$ and $y$ are positive integers. Then $\text{max}(x − 1, y − 1) = k$, so by the IH, we have that $x − 1 = y − 1$. By adding $1$ to both sides we obtain that $x = y$, completing the inductive step.

The answer as to why this proof is wrong is because:

The mistake is in the inductive step: The IH says that whenever $\text{max}(x, y) = k$ and $x$ and $y$ are positive integers, then $x = y$. Now consider the following case: $k + 1 = 2$, $x = 1$ and $y = 2$. Then $x$ and $y$ are positive integers and $\text{max}(x, y) = \text{max}(1, 2) = 2 = k + 1$. Then $\text{max}(x − 1, y − 1) = \text{max}(0, 1) = 1 = k$. But $0$ is NOT a positive integer, so the IH does NOT apply.

Questions I have:

1. What I don't understand is why does the notation for max$(x,y)$ say that x has to be $\ge y$ and $x$ has to be $< y$ if it explicitly states in the theorem that $x$ has to $= y$. This is a contradiction

2. In the answer it says to consider the case where $x=1$ and $y=2$ but we CAN'T have that case because $x$ must $= y$, so why did the answer even consider that case

3. I don't even understand what the theorem means tbh, how does it mean 'all positive integers are equal'. To be it says that for every positive integer $n$, the maximum of $2$ positive integers is equal to $n$. So for example, for the positive number $10, a = 10$ and $b = 10$. For the positive number $11, a = 11$ and $b = 11$. The proof seems correct to me because for every positive integer, the max of 2 numbers which are the same would return $1$ number$\dots n$. So how is this saying that all positive numbers are equal?

I'm just confused by this question in general, can anyone please clear this up for me. Thanks in advance

Answer 1

Tha fallacy is in the induction step, when we consider $\max(x − 1, y − 1) = k$ we need that $x,y >1$ but the base case was proved for $x=y=1$.

Then, to proceed by induction, we should verify the base case for $n=2$, which can't be true.

Se also the related:

• Questions on "All Horse are the Same Color" Proof by Complete Induction

---

For your more specific question:

1. The theorem is indeed false
2. This is indeed where the base case fails
3. The problem is constructed considering a false theorem proved by an apparently correct induction. This is a standard exercise to better understand as induction works.

Answer 2

The induction hypothesis is only applicable for positive integers $x$ and $y$. However, it is not guaranteed that $x-1$ and $y-1$ are both positive (this is where the counter-example comes into play).

Moreover, the counter-example is valid, since it satisfies all the conditions required by the "theorem." Sure, the theorem's conclusion ($x=y$) is wrong, but that's exactly why this constitutes a counter-example!

Answer 3

Your third question is

I don't even understand what the theorem means tbh, how does it mean 'all positive integers are equal'.

The false theorem is

“Theorem:” For every positive integer n, if x and y are positive integers with $\,\max(x,y) = n,\,$ then $\,x=y.$

Given any positive integers $\,x\,$ and $\,y,\,$ by the definition of $\,\max\,$ we get that $\,\max(x,y)=n\,$ for some positive integer $\,n.\,$ Then the theorem applies and implies that $\,x=y\,$ which states that $\,x\,$ is equal to $\,y.\,$ But this applies to all integers $\,x\,$ and $\,y\,$ as given to us. Thus, 'all positive integers are equal'.