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** !

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

- is not finite.
- is
**absolutely not**. - Similarly, is, again,
**not**.

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 :

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

Then for every ordinal, .

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

First, what is ? Well, you can think of as a ‘function’ that it’s input is an ordinal, and it’s output is **true** or **false**.

represents the -th statement. For example, is statment 0. is statement 1… is statement , and so on…

Now, what “” is saying?

This is a condition on – The condition is:

“If is true for every smaller than . Then, is true as well”.

For example, If , the the condition is:

“If are both true, then is true as well”.

Finally, what a transfinite incduction says, is that if this condition is true for every ordinal, then for every ordinal, is true.

Let’s prove it:

#### Proof of the transfinite induction

Aiming for contradiction, suppose that is not true for all the ordinals.

Since the class of ordinals is well-ordered, there is a first ordinal such that is false. Thus, for every , we must have: is true.

So the statement:

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

Holds for , thus, is true. But that’s a contradiction to it being the first element such that 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 , is true. We need to show that:

- is true
- For every : .
- For every
**limit ordinal**: If for every , is true, then 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 is not true for every .

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

- If , we get a contradiction, since by our assumtion, is true.
- In the case that is a
**successor**, then for some . In particular, , so must be true (since is the minimal element such that is false). By the second condition, we get that is true, and that’s a contradiction. - is a
**limit**ordinal. For every we must have is true. However, by the third condition, we conclude that is true as well. Again, we got a contradiction.

Therefore, is true for every .

## Example

Let’s try to prove that for every ordinal and every ordinal :

\beta \leq \alpha+\beta

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

If then (0 is the first element) so the statment is true for .

Now we’ll show that if then . Using the associative property to get:

\alpha+(\beta+1)=(\alpha+\beta)+1 > \alpha+\beta

By induction we have:

\beta\leq\alpha+\beta<(\alpha+\beta)+1\\ \Downarrow \\ \beta <(\alpha+\beta)+1

Therefore, . Thus and we now have:

\beta+1=\overbrace{\beta}^{\sub (\alpha+\beta)+1}\cup\overbrace{\{\beta\}}^{\subseteq (\alpha+\beta)+1}\subseteq (\alpha+\beta)+1

Finally:

\beta+1< (\alpha+\beta)+1= \alpha+(\beta+1)

As we wanted.

For the last part, suppose that is a **limit ordinal**, and suppose that for every :

\gamma\leq\alpha+\gamma

Thus:

\beta=0+\beta=\sup\{\gamma|\gamma< b\}\leq \sup\{\alpha +\gamma|\gamma< b\}=\alpha+\beta

We proved the transition here are valid in this post (this is the “continuous property” of addition).

And that’s it, we’ve proved that all three conditions hold, therefore, the statement is true!

## Summary

In this post we’ve added a new method of proving statements to our toolkit. In the next posts, we will start to ‘feel’ how useful the method is!