Transfinite induction - The 'infinite' induction

If you are a math major, you probably proved theorems using induction countless of times. And that’s not suprising – induction is one of the most powerful tools a mathematician has in his toolkit. However, induction has one major problem – It is finite.

For example, if you managed to prove that union of two ‘open sets’ is an open set, so by induction you can also prove that finite union of open sets, is an open set.

Sometimes, finite is just not enough! It would be nice to generalize the induction such that we will be able to prove more than just finite statements.

How can we do such things? ‘Infinity’ is not really a number, intuitivly, ‘infinity’ plus one is ‘infinity’ and ‘infinity’ plus ‘infinity’, is also infinity.

Wait… I’ve already said in the previous posts. When dealing with infinity we can’t trust our intuition. And in the matter of fact, we do have an ‘infinity’ that acts just like we want him to act in order to apply induction. Do you know what I am talking about? I am talking about the ordinal $\omega$ !

After defining the natural numbers in a formal way, and defining addition on ordinals, it is clear to us that:

$\omega$ is not finite.
$\omega + 1$ is absolutely not $\omega$ .
Similarly, $\omega +\omega$ is, again, not $\omega$ .

Those facts invites us to define an ‘infinte induction’. And that’s what we will call: a transfinite induction

What is transfinite induction?

Suppose that for every $\alpha\in\text{ON}$ :

(\forall\beta<\alpha:\varphi(\beta))\to \varphi(\alpha)

Then for every ordinal, $\varphi(\alpha)$ .

What is going on here? let’s try to understand it step-by-step:

First, what is $\varphi(\alpha)$ ? Well, you can think of $\varphi$ as a ‘function’ that it’s input is an ordinal, and it’s output is true or false.

$\varphi(\alpha)$ represents the $\alpha$ -th statement. For example, $\varphi(0)$ is statment 0. $\varphi(1)$ is statement 1… $\varphi(\omega)$ is statement $\omega$ , and so on…

Now, what “ $\forall\beta<\alpha:\varphi(\beta))\to \varphi(\alpha)$ ” is saying?

This is a condition on $\alpha$ – The condition is:

“If $\varphi(\beta)$ is true for every $\beta$ smaller than $\alpha$ . Then, $\varphi(\alpha)$ is true as well”.

For example, If $\alpha = 2$ , the the condition is:

“If $\varphi(0),\varphi(1)$ are both true, then $\varphi(2)$ is true as well”.

Finally, what a transfinite incduction says, is that if this condition is true for every ordinal, then for every ordinal, $\varphi(\alpha)$ is true.

Let’s prove it:

Proof of the transfinite induction

Aiming for contradiction, suppose that $\varphi(\alpha)$ is not true for all the ordinals.

Since the class of ordinals is well-ordered, there is a first ordinal $\alpha$ such that $\varphi(\alpha)$ is false. Thus, for every $\beta <\alpha$ , we must have: $\varphi(\beta)$ is true.

So the statement:

(\forall\beta<\alpha:\varphi(\beta))\to \varphi(\alpha)

Holds for $\alpha$ , thus, $\varphi(\alpha)$ is true. But that’s a contradiction to it being the first element such that $\varphi(\alpha)$ is false.

And, that’s it! A really simple proof for a really powerful tool!

An Equivalent statement

After we’ve proved the transfinite induction, I want to present an equivalent statement, that will be more useful. It allows us to split the proof and deal with limit ordinals and successor ordinals separatly.

Here is the proposition:

If we want to prove that for all $\alpha\in\text{ON}$ , $\varphi(\alpha)$ is true. We need to show that:

$\varphi(0)$ is true
For every $\beta\in \text{ON}$ : $\varphi(\beta)\to\varpho(\beta+1)$ .
For every limit ordinal $\alpha\neq 0$ : If for every $\beta$ , $\varphi(\beta)$ is true, then $\varphi(\alpha)$ is true.

Notice that if we are dealing with the natural number only and assuming that the third condition always holds, then we will get the induction we are familiar with!

Let’s prove it:

Same as before, I am aiming for contradiction, and assuming that $\varphi(\alpha)$ is not true for every $\alpha$ .

Again, Denote the first element with this property as $\alpha$ . There are three cases now:

If $\alpha = 0$ , we get a contradiction, since by our assumtion, $\varphi(0)$ is true.
In the case that $\alpha$ is a successor, then $\alpha = \beta+1$ for some $\beta$ . In particular, $\beta<\alpha$ , so $\varphi(\beta)$ must be true (since $\alpha$ is the minimal element such that $\varphi(\alpha)$ is false). By the second condition, we get that $\varphi(\alpha)$ is true, and that’s a contradiction.
$If$ $\alpha\neq 0$ is a limit ordinal. For every $\beta<\alpha$ we must have $\varphi(\beta)$ is true. However, by the third condition, we conclude that $\varphi(\alpha)$ is true as well. Again, we got a contradiction.

Therefore, $\varphi(\alpha)$ is true for every $\alpha$ .

Example

Let’s try to prove that for every ordinal $\alpha$ and every ordinal $\beta$ :

\beta \leq \alpha+\beta

Of course, we will prove it using transfinite induction, which will be done on $\beta$ . However, we will prove it using the equivalent definition. So there are 3 thing to show:

If $\beta=0$ then $0\leq \alpha+0=\alpha$ (0 is the first element) so the statment is true for $0$ .