Transfinite idnduction in action

After presenting the method of proof called transfinite induction, I want to show some pretty awesome stuff we can prove with it. So let’s start then:

Comparing order types

My goal here is to prove that if $A,B$ are both well-ordered sets and

f:A\to B

Is an order-preserving map, then:

\text{otp}(A)\leq\text{otp}(B)

This is a quite strong statement, it gives us a connection between the order-types of two well-ordered sets. The only thing we need to do is just find an order-preserving map! That’s it, not even an isomorphism which is way harder to find! (However, if we did find an isomorphism, then we know that those sets have the same order type).

How is that useful? Let’s see an example:

For evert three ordinals $\alpha,\beta,\gamma$ :

\alpha+\gamma\leq\alpha+\beta+\gamma

This statement means that we can create a bigger ordinal by ‘pushing’ some ordinal in-between. Why is that true? Recall that:

\alpha+\gamma=\text{otp}(\alpha\times\{0\}\cup\gamma\times\{1\})\\ \alpha+\beta+\gamma=\text{otp}(\alpha\times\{0\}\cup\beta\times\{1\}\cup\gamma\times\{2\})

So the theorem says that we only need to find an order isomorphism:

f:\alpha\times\{0\}\cup\gamma\times\{1\}\to \alpha\times\{0\}\cup\beta\times\{1\}\cup\gamma\times\{2\}

And that’s not a big problem at all (try to find one, I think it’s pretty easy to find one).

Here is another example:

Suppose that $\alpha_1\leq \alpha_2$ and $\beta_1\leq \beta_2$ . Then

\alpha_1+\beta_1\leq\alpha_2+\beta_2 \\ \alpha_1\beta_1\leq\alpha_2\beta_2

It’s really not a problem, just find order-preserving maps:

f:\alpha_1\times\{0\}\cup\beta_1\times\{1\}\to\alpha_2\times\{0\}\cup\beta_2\times\{1\} \\ g:\alpha_1\times\beta_1\to\alpha_2\times\beta_2

And that’s it, the theorem tells you that it’s enough – try find them yourself, it’s really easy (Recall that $\alpha_1\leq \alpha_2$ is the same as $\alpha_1\sube \alpha_2$ ).

How can we prove it?

In order to prove it, I’ll prove something stronger:

Suppose that $\alpha$ is an ordinal and $A\sube \alpha$ is a subset of $\alpha$ . Thus $\text{otp}(A)\leq \alpha$ .

Recall that a subset of an ordinal is also well-ordered (if it weren’t we could have find a subset of it that has no first element, but it is in fact also a subset of the ordinal which is indeed well-ordered. contradiction!)

So I am going to prove this statement using transfinite induction on $\alpha$ . Let’s do it:

Base case

$\alpha = 0, A\sube \alpha$ . Thus $A=\emptyset$ and: $\text{otp}(A)=0$ .

Induction for successors

Suppose that the statement is true for $\alpha$ . We want to prove that it is also true for $\alpha+1$ .

Suppose that $A\sube \alpha+1$ . And we know that $\alpha+1=\alpha\cup\{\alpha\}$ . So there are two cases now:

If $\alpha\notin A$ : Thus $A\sub \alpha$ and by induction we get that $\text{otp}(A)\leq\alpha<\alpha+1$ .

Otherwise, $\alpha\in A$ : Well we have to use the induction in some way, so let’s define a subset of $\alpha$ :

B=A\setminus\alpha

By induction: $\text{otp}(B)\leq \alpha$ . Therefore:

\text{otp}(B)+1\leq\alpha+1

This fact motivates us to define an order isomorphism:

F:A\to\text{otp}(B)+1\ \ (=\text{otp}(B)\cup\{\text{otp}(B)\})

We can use an order isomorphism $f:B\to\text{otp}(B)$ to define $F$ as:

F(a)=\begin{cases} \text{\text{otp}}(B) & a=\alpha\\ f(b) & a\neq\alpha \end{cases}

This one is indeed an order isomorphism thus:

\text{otp}(A)=\text{otp}(B)+1\leq\alpha+1

As we wanted.

Induction for limit ordinals

Suppose that $\beta$ is a limit ordinal and the statement is true for every $\alpha<\beta$ . Let $A\sub \beta$ be some subset.

Recall that the proof of the statement “every well-ordered set is order-isomorphic to an ordinal” we’ve actually constructed an isomorphism from $\alpha$ to some ordinal.

The isomorhism mapped an element $a\in A$ to an ordinal that is order-isomorphic to the lower set genarated by $a$ (That is, $a_{\downarrow}$ . You can find the proof here.

Now, suppose that $a\in A$ . In particular $a\in \beta$ . Since $\beta$ is a limit ordinal, it has no maximal element. Thus, there exists some $\gamma\in \beta$ such that $a<\gamma$ .

Therefore, $a_{\downarrow}\sub \gamma$ . Now we can use the induction to conclude that:

\text{otp}(a_{\downarrow})\leq\gamma

We can now use the order-isomorphism:

f:A\to\text{otp}(A)

Recall that if $a\in A$ then $a_{\downarrow}\cong f(a)_{\downarrow}$ and $f(a)_{\downarrow}=f(a)$ is an ordinal (since $f(a)$ is an elemenet of an ordinal, it is an ordinal itself. We know that ordinals equals the lower set they generates).

therefore $f(a) = \text{otp}(a_\downarrow)\leq\gamma<\beta$ . However, all the elements in $\text{otp}(A)$ are of the form $f(a)$ for some $a\in A$ ( $f$ is an isomorphism). So all the elements in $\text{otp}(A)$ are smaller than $\beta$ . Thus $\beta$ can’t be one of them:

\beta\notin\text{otp}(A)

And this implies $\text{otp}(A)\leq \beta$ , as we wanted.

Deducing what we want

So we proved this theorem, but how can we deduce what we wanted from the first place? Well let’s try to find out:

Suppose that $A,B$ are well-ordered and $f:A\to B$ is an order-preserving map between them. We want to show that $\text{otp}(A)\leq \text{otp}(B)$ .

Since we are dealing with well-ordered sets, the order-preserving map has to be one-to-one (linearly ordered is enough, I proved it in one of the first posts, right here). Therefore, $A$ is isomorphic to it’s image:

A\cong f[A]\sube B

Now the natural thing to do is ‘move’ to $\text{otp}(B)$ . How exactly? We can pick an order isomorphism:

g:B\to\text{otp}(B)

Thus, under $g$ , $f[A]\sube B$ is isomorphic to it’s image:

f[A]\cong g[f[A]]

But $g[f[A]]$ is a well-ordered subset of the ordinal $\text{otp}(B)$ . So by the theorem we know that:

\text{otp}(g[f[A]])\leq\text{otp}(B)

However:

\text{otp}(A)=\text{otp}(f[A])=\text{otp}(g[f[A]])

So we can conclude:

\text{otp}(A)\leq\text{otp}(B)

As we wanted!

Summary

So we’ve seen another cool use of the transfinite induction. Now if we want to compare order types of sets, it’s enough to find just an order-preserving map to do so.

In the next post I will introduce the term of an ordinal exponantiation, which is a little complicated, so prepare yourself!

Transfinite idnduction in action