Cantor's Diagonal Argument - using induction on infinite row lengths?

Question

I've read some simple explanations of Cantor's diagonal method.

It seems to be:

1) Changing the i-th value in a row.
2) Do the same to the next row with the (i+1)th element.
3) Now you get an element not in any other row. So add it to list.
4) This process never ends.

This looks very like induction since it uses the (n+1) trick.

However, induction only works for finite numbers.

And the row lengths are not finite.

So how did Cantor get around this?

Answer 1

You don't need induction to prove that the new number is different than any already listed number.

You have a construction for the new number. For any element in the list, there is some digit that is not the same, and based on where it is in the list, you can say exactly which one. This statement does not depend on previous digits differing for other numbers.

Answer 2

Cantor's diagonal proof is not infinite in nature, and neither is a proof by induction an infinite proof.

---

For Cantor's diagonal proof (I'll assume the variant where we show the set of reals between $0$ and $1$ is uncountable), we have the following claims:

• Every real number (between $0$ and $1$) has a representation as an infinite string $0.d_0d_1d_2d_3\cdots$, where each $d_i$ is a digit, i.e. $0$, $1$, $2$, ... or $9$.
• If the real numbers were countable, then we can make a function such that each real is assigned some natural number $n\in\Bbb N$ and vice versa, also known as a countable list of real numbers.
• It is possible to define a real that is not assigned any natural number: we define the $i$th digit of our new real to be $5$ if the $i$th digit of the real number associated with the natural number $i$ is unequal to $5$, and otherwise we define the $i$th digit to be $6$. Note that we define this real all at once. We do not need to know the construction of earlier steps, so we do not use induction.
• This new real is not part of our list, since for any number of the list, there is some digit on which it disagrees.

None of these steps need you to do an infinite process. The only infinite thing we do is that we work with infinite sets of elements.

---

Induction in itself (which is unrelated to Cantor's diagonal argument) is also not an infinite process. To show that a property $\phi$ holds for all natural numbers, we prove that $\phi$ holds for $0$, and that if $\phi$ holds for $n$, then it holds for $n+1$. These are two finite proofs.

Then, to show that the property holds for every natural number, we pick an arbitrary number $m$. If we can show the property holds for $m-1$, then it must hold for $m$, so we try to show it holds for $m-1$. If it holds for $m-2$, then it must hold for $m-1$, so we try to show it holds for $m-2$. Et cetera, until we reach $m-m=0$. This is the base case, which we have already proved.

Therefore, we can show that the property holds for all natural numbers, since for any number, we only have to work back a finite number of steps to get to the base case.

---

As a sidenote, induction can be used on any well-founded class, regardless of it being infinite or finite.

The trick is not that you show some property of interest for every element individually (which does indeed cost an infinite number of steps), but that you show that the property of an individual depends only on its predecessors having the property. You show "if all predecessors have the property, then this individual has the property".

If we then want to prove that an individual does not have the property, you would need to be able to find a predecessor that does not have the property.

In a well-founded set, there are no infinitely descending chains, so for any predecessor that is not the base case, we must be able to find a predecessor of this predecessor that does not have the property. We only can do this finitely many times, since a well-founded set has no infinitely descending chains.

It follows that eventually we will reach the base case, and for the base case we (presumably) have already proved that it has the property. Therefore our finite chain of predecessors must all have the property, which means our original element of interest must have the property.