I don't understand this proof: Trichotomy for ordinals (by double transfinite induction)

Question

Hello everyone!

The proof is from this book: https://st.openlogicproject.org/

I think I understand the black bracket (checked). What worries me is the blue bracket (question mark).

As far as I understand, generally speaking, a 'double induction' would "nest" two inductions "into one another", so to speak: Like there is the 'big' surrounding/outer induction on the one side, and one or maybe more 'small' inner inductions happening (as it were) in the middle of it all, on the other side. Right?

Wouldn't we want, then, to show that the if-clause is fulfilled for the outer induction (and maybe, to this end, there will already be neccessary a little induction inside)? For then, we could use the induction (which is a theorem in this case) to show what we want to show?

Instead, we suppose something to do with $\alpha$ and any ordinal, and then, we suppose something 'for further induction'...I really don't know what is going on in this whole paragraph, which appearently explains a plan for how the proof is supposed to work out.

Thanks for reading. :)

Any hints, remarks and suggestions are appreciated..

Answer 1

This is general structure of the proof:

We want to prove that for every ordinal $\alpha$, for every ordinal $\beta$, $\alpha$ is comparable to $\beta$.

Proceeding by induction on $\alpha$, we assume that every element of $\alpha$ is comparable to every ordinal, and want to prove that $\alpha$ is comparable to every ordinal.

So we assume every element of $\alpha$ is comparable to every ordinal. Now we want to prove that for every ordinal $\beta$, $\alpha$ is comparable to $\beta$.

But this is something we want to establish "for every ordinal", and as such we can use induction on ordinals to establish it (induction on $\beta$). So we assume that $\alpha$ is comparable to every element of $\beta$, and want to prove that $\alpha$ is comparable to $\beta$.

So we have two "inductive hypotheses":

1. For the induction on $\alpha$, we are assuming that every element of $\alpha$ is comparable to every ordinal. We want to prove that $\alpha$ is comparable to every ordinal $\beta$.

2. For the subsequent induction on $\beta$, we are assuming that $\alpha$ is comparable to every element of $\beta$. We want to prove that

$\alpha$ is then comparable to $\beta$.

If we prove $\alpha$ is comparable to $\beta$ from these assumptions, we will prove that:

If every element of $\alpha$ is comparable to every ordinal, then $\alpha$ is comparable to every ordinal.

And that will prove, by induction, that

Every ordinal $\alpha$ is comparable to every ordinal.

which is what we want to prove.

Since proving

$\alpha$ is comparable to $\beta$

means proving that either $\alpha\in\beta$ or $\beta\in\alpha$ or $\alpha=\beta$, we can assume $\alpha\notin \beta$, and $\beta\notin\alpha$, and try to prove $\alpha=\beta$.

So our "outside induction hypothesis" is that every element of $\alpha$ is comparable to every ordinal. And our "inner induction hypothesis" is that $\alpha$ is comparable to every element of $\beta$. So to list our assumptions:

1. Every element of $\alpha$ is comparable to every ordinal ("outer" induction hypothesis).
2. $\alpha$ is comparable to every element of $\beta$ ("inner" induction hypothesis).
3. $\alpha\notin \beta$;
4. $\beta\notin\alpha$.

We want to prove that $\alpha=\beta$.

You use 1, 3, and 4 to prove that $\alpha\subseteq\beta$. Then you use 2, 3, and 4 to prove that $\beta\subseteq\alpha$. That proves $\alpha=\beta$, and you are done.