In a my previous blog post, I discussed the canonical well-ordering on
and stated theorem 0.5 below to calculate its
order-type . Subsequent corollaries provided a bound for
, its fixed points and a proof that infinite cardinals were
among these fixed points (and so that cardinal addition and multiplication
is trivial).
In this second part, I’m going to provide the proof of this theorem.
First, we note that for all , there is only one order-type for
, since
the notion of cardinal and ordinal is the same for finite sets.
So indeed
and taking the limit, we get our first infinite fixed point:
For all the ordering on
is as follows: first the
elements of ordered as , followed by
the elements for , followed by
the elements for . Hence
From this, we can try to calculate the next values of after :
The important point is ; in general we will use
several times the property
if .
By a simple recurrence (see proposition 0.1),
we can generalize the expression to arbitrary :
and so taking the limit
which is a limit ordinal not fixed by .
We note another point that will be used later: taking the limit
“eliminates” the smallest terms.
More generally, we can perform the same calculation, starting from any
arbitrary :
Proposition 0.1.
For any limit ordinal and we have
Proof.
For this is the relation for explained
above. If the relation is true for then
and since we have and so
Which shows the result at step .
∎
As above, we can take the limit and say
which is consistent with
. However, if we
consider the Cantor Normal Form
,
then for all we have can use the fact that “ will
eliminate smaller terms on its left” that is
. Then using the
fact that “taking the limit eliminates the smallest terms” we get
. So actually, we have a nicer formula where
is put in Cantor Normal Form:
This can be generalized by the following proposition:
Proposition 0.2.
For any and
such that we have
Proof.
We prove by induction on that for all such
the expression is true. We just verified and the
limit case is obvious by continuity of and of the sum/exponentiation
in the second variable. For the successor step, if
then
a fortiori
.
We can then use the induction hypothesis to prove by induction on
that
. For , this is
just the induction hypothesis of (for the same !). For the
successor step, we need to use the induction hypothesis of
(for ) which is
.
Finally,
, as wanted.
∎
For all ,
so the previous
paragraph also gives
.
Then, we find
And more generally by induction on , we can show that
Then we deduce another fixed point
The following proposition tries to generalize the expression of
.
Proposition 0.3.
For any such that
we have
Proof.
This is done
by induction on for a fixed . We already verified
the case in the previous paragraph and the limit case is obvious
by continuity of and of the sum/exponentiation in the second variable.
For the successor step, we have
and by induction
hypothesis, .
Since we have
and so
.
Finally, as wanted.
∎
For any
and , if
then . Hence
proposition 0.3 gives
Then by continuity of and of the sum/exponentiation in the second
variable, we can consider the limit to get
.
So continuing our calculation we have
and taking the limit we find another fixed point
then again
and taking the limit we find another fixed point
More generally, we have the following proposition:
Proposition 0.4.
For any ordinal and we have
Proof.
From the relation ,
we deduce by induction on that
Taking the limit ,we obtain
We can then show by induction that all the
are actually fixed points, using the previous
relation at successor step, the continuity of at limit step
and the fact that . This means
Then for , we get
∎
Equipped with these four propositions, we have a way to recursively calculate
. We are ready to prove the main theorem:
Theorem 0.5.
For all ordinal , we denote the order-type of
the canonical ordering of . Then can be
calculated as follows:
1.
Finite Ordinals:
For any we have
2.
Limit Ordinals:
For any limit ordinal ,
(a)
If does not
divide then
(b)
Otherwise, we write
for some . If
then
(like the first case but we “decrement in the second factor”)
(c)
Otherwise, and
we write
for some . We have
(like the first case but we “decrement in the second factor”)
3.
Infinite Successor Ordinals:
For any limit ordinal and we have
where is determined as in the previous point.
Proof.
The “Finite Ordinals” has been discussed at the beginning and the
“Infinite Successor Ordinals” is proposition 0.1.
Now let’s consider the Cantor Normal Form
of a limit ordinal
(so and
). First,
from proposition 0.2 we can make successively
extract the terms (by left-multiplying them
by ), then the terms , …
then the terms and finally
terms . We obtain:
We now write where
and are the quotient and remainder
of the Euclidean division of by . We can then use
proposition 0.3 to extract :
means that
does not divide
. In that case,
and so
.
We note that since the remainder is less than
. So actually . Coming back to the expression
of , this term can be grouped with
to
recover the Cantor Normal Form of and
we finally get .
Otherwise, , and
But then and so
. Hence if
, the term
is eliminated in the expression of
and it remains
where . If instead , then the term
is zero and it remains