Ordinals

Definition one in this chapter

The relation $<$source well-orders $A$source iff it meets these two conditions:

1. $<$source is connected, i.e., for all $a, b \in A$source, either $a < b$source or $a = b$source or $b < a$source;

2. every non-empty subset of $A$source has a $<$source-minimal element, i.e., if $\emptyset \neq X \subseteq A$source then $(\exists m \in X)(\forall z \in X)z \nless m$source

Exercise one in this chapter

Section “The General Idea of an Ordinal” in chapter “Ordinals” presented three example orderings on the natural numbers. Check that each is a well-ordering.

Proposition one in this chapter

If $<$source well-orders $A$source, then every non-empty subset of $A$source has a unique $<$source-least member, and $<$source is irreflexive, asymmetric and transitive.

Proof

If $X$source is a non-empty subset of $A$source, it has a $<$source-minimal element $m$source, i.e., $(\forall z \in X)z \nless m$source. Since $<$source is connected, $(\forall z \in X)m \leq z$source. So $m$source is the $<$source-least element of $X$source.

For irreflexivity, fix $a \in A$source; the $<$source-least element of $\{a\}$source is $a$source, so $a \nless a$source. For transitivity, if $a < b < c$source, then since $\{a, b, c\}$source has a $<$source-least element, $a < c$source. Asymmetry follows from irreflexivity and transitivity

Proposition two in this chapter

If $<$source well-orders $A$source, then for any formula $\phi(x)$source:

Proof

We will prove the contrapositive. Suppose $\lnot(\forall a \in A)\phi(a)$source, i.e., that $X = \Setabs{x \in A}{\lnot\phi(x)} \neq \emptyset$source. Then $X$source has an $<$source-minimal element, $a$source. So $(\forall b < a)\phi(b)$source but $\lnot \phi(a)$source.

Definition two in this chapter

A well-ordering is a pair $\tuple{A, <}$source, such that $<$source well-orders $A$source. The well-orderings $\tuple{A, <}$source and $\tuple{B, \lessdot}$source are order-isomorphic iff there is a bijection $f \colon A \to B$source such that: $x < y$source iff $f(x) \lessdot f(y)$source. In this case, we write $\ordeq{\tuple{A, <}}{\tuple{B, \lessdot}}$source, and say that $f$source is an order-isomorphism.

Lemma one in this chapter

Compositions of isomorphisms are isomorphisms, i.e.: if $f \colon A \to B$source and $g \colon B \to C$source are isomorphisms, then $(g \circ f) \colon A \to C$source is an isomorphism.

Exercise two in this chapter

Prove lemma one in chapter “Ordinals”.

Proof

Left as an exercise.

Corollary one in this chapter

$\ordeq{X}{Y}$source is an equivalence relation.

Proposition three in this chapter

If $\tuple{A, <}$source and $\tuple{B, \lessdot}$source are isomorphic well-orderings, then the isomorphism between them is unique.

Proof

Let $f$source and $g$source be isomorphisms $A \to B$source. We will prove the result by induction, i.e.\ using proposition two in chapter “Ordinals”. Fix $a\in A$source, and suppose (for induction) that $(\forall b < a)f(b) = g(b)$source. Fix $x \in B$source.

If $x \lessdot f(a)$source, then $f^{-1}(x) < a$source, so $g(f^{-1}(x)) \lessdot g(a)$source, invoking the fact that $f$source and $g$source are isomorphisms. But since $f^{-1}(x) < a$source, by our supposition $x =f(f^{-1}(x)) = g(f^{-1}(x))$source. So $x \lessdot g(a)$source. Similarly, if $x \lessdot g(a)$source then $x \lessdot f(a)$source.

Generalising, $(\forall x \in B)(x \lessdot f(a) \liff x \lessdot g(a))$source. It follows that $f(a) = g(a)$source by the proposition on extensionality strictlinearorders. So $(\forall a \in A)f(a) = g(a)$source by proposition two in chapter “Ordinals”.

Definition three in this chapter

When $\tuple{A, <}$source is a well-ordering with $a \in A$source, let $A_a = \Setabs{x \in A}{x < a}$source. We say that $A_a$source is a proper initial segment of $A$source (and allow that $A$source itself is an improper initial segment of $A$source). Let $<_a$source be the restriction of $<$source to the initial segment, i.e., $\funrestrictionto{\mathord{<}}{A_a^2}$source.

Lemma two in this chapter

If $\tuple{A, <}$source is a well-ordering with $a \in A$source, then $\ordneq{\tuple{A, <}}{\tuple{A_a, <_a}}$source

Proof

For reductio, suppose $f \colon A \to A_a$source is an isomorphism. Since $f$source is a bijection and $A_a \subsetneq A$source, using proposition one in chapter “Ordinals” let $b \in A$source be the $<$source-least element of $A$source such that $b \neq f(b)$source. We'll show that $(\forall x \in A)(x<b \liff x < f(b))$source, from which it will follow by the proposition on extensionality strictlinearorders that $b = f(b)$source, completing the reductio.

Suppose $x < b$source. So $x = f(x)$source, by the choice of $b$source. And $f(x) < f(b)$source, as $f$source is an isomorphism. So $x < f(b)$source.

Suppose $x < f(b)$source. So $f^{-1}(x) < b$source, since $f$source is an isomorphism, and so $f^{-1}(x) = x$source by the choice of $b$source. So $x < b$source.

Lemma three in this chapter

Let $\tuple{A, <}$source and $\tuple{B, \lessdot}$source be well-orderings. If $f \colon A \to B$source is an isomorphism and $a \in A$source, then $\funrestrictionto{f}{A_{a}} : A_a \to B_{f(a)}$source is an isomorphism.

Proof

Since $f$source is an isomorphism:

And $\funrestrictionto{f}{A_a}$source preserves order because $f$source does.

Lemma four in this chapter

Let $\tuple{A, <}$source and $\tuple{B, \lessdot}$source be well-orderings. If $\ordeq{\tuple{A_{a_1}, <_{a_1}}}{\tuple{B_{b_1}, \lessdot_{b_1}}}$source and $\ordeq{\tuple{A_{{a_2}}, <_{a_2}}}{\tuple{B_{{b_2}}, \lessdot_{b_2}}}$source, then ${a_1} < {a_2} \text{ iff }{b_1} \lessdot {b_2}$source

Proof

We will prove left to right; the other direction is similar. Suppose both $\ordeq{\tuple{A_{a_1}, <_{a_1}}}{\tuple{B_{b_1}, \lessdot_{b_1}}}$source and $\ordeq{\tuple{A_{{a_2}}, <_{a_2}}}{\tuple{B_{{b_2}}, \lessdot_{b_2}}}$source, with $f \colon A_{{a_2}} \to B_{{b_2}}$source our isomorphism. Let ${a_1} < {a_2}$source; then $\ordeq{\tuple{A_{a_1}, <_{a_1}}}{\tuple{B_{f({a_1})}, \lessdot_{f({a_1})}}}$source by lemma three in chapter “Ordinals”. So $\ordeq{\tuple{B_{b_1}, \lessdot_{b_1}}}{\tuple{B_{f({a_1})}, \lessdot_{f({a_1})}}}$source, and so ${b_1} = f({a_1})$source by lemma two in chapter “Ordinals”. Now ${b_1} \lessdot {b_2}$source as $f$source's domain is $B_{{b_2}}$source.

Theorem one in this chapter

Given any two well-orderings, one is isomorphic to an initial segment (not necessarily proper) of the other.

Proof

Let $\tuple{A, <}$source and $\tuple{B, \lessdot}$source be well-orderings. Using Separation, let

By lemma four in chapter “Ordinals”, $a_1 < a_2$source iff $b_1 \lessdot b_2$source for all $\tuple{a_1, b_1}, \tuple{a_2, b_2} \in f$source. So $f \colon \dom{f} \to \ran{f}$source is an isomorphism.

If $a_2 \in \dom{f}$source and $a_1 < a_2$source, then $a_1 \in \dom{f}$source by lemma three in chapter “Ordinals”; so $\dom{f}$source is an initial segment of $A$source. Similarly, $\ran{f}$source is an initial segment of $B$source. For reductio, suppose both are proper initial segments. Then let $a$source be the $<$source-least element of $A \setminus \dom{f}$source, so that $\dom{f} = A_a$source, and let $b$source be the $\lessdot$source-least element of $B \setminus \ran{f}$source, so that $\ran{f} = B_b$source. So $f \colon A_a \to B_b$source is an isomorphism, and hence $\tuple{a, b} \in f$source, a contradiction.

Definition four in this chapter

The set $A$source is transitive iff $(\forall x \in A)x \subseteq A$source. Then $A$source is an ordinal iff $A$source is transitive and well-ordered by $\in$source.

Lemma five in this chapter

Every element of an ordinal is an ordinal.

Proof

Let $\alpha$source be an ordinal with $b \in \alpha$source. Since $\alpha$source is transitive, $b \subseteq \alpha$source. So $\in$source well-orders $b$source as $\in$source well-orders $\alpha$source.

To see that $b$source is transitive, suppose $x \in c \in b$source. So $c \in \alpha$source as $b \subseteq \alpha$source. Again, as $\alpha$source is transitive, $c \subseteq \alpha$source, so that $x \in \alpha$source. So $x, c, b \in \alpha$source. But $\in$source well-orders $\alpha$source, so that $\in$source is a transitive relation on $\alpha$source by proposition one in chapter “Ordinals”. So since $x \in c \in b$source, we have $x \in b$source. Generalising, $c \subseteq b$source

Corollary two in this chapter

$\alpha = \Setabs{\beta \in \alpha}{\beta \text{ is an ordinal}}$source, for any ordinal $\alpha$source

Proof

Immediate from lemma five in chapter “Ordinals”.

Theorem: Transfinite Induction

[Transfinite Induction] For any formula $\phi(x)$source:

where the displayed quantifiers are implicitly restricted to ordinals.

Proof

Suppose $\phi(\alpha)$source, for some ordinal $\alpha$source. If $(\forall \beta \in \alpha) \lnot \phi(\beta)$source, then we are done. Otherwise, as $\alpha$source is an ordinal, it has some $\in$source-least element which is $\phi$source, and this is an ordinal by lemma five in chapter “Ordinals”.

Theorem: Trichotomy

[Trichotomy] $\alpha \in \beta \lor \alpha = \beta \lor \beta \in \alpha$source, for any ordinals $\alpha$source and $\beta$source.

Proof

The proof is by double induction, i.e., using theorem “Transfinite Induction” in chapter “Ordinals” twice. Say that $x$source is comparable with $y$source iff $x \in y \lor x = y \lor y \in x$source.

For induction, suppose that every ordinal in $\alpha$source is comparable with every ordinal. For further induction, suppose that $\alpha$source is comparable with every ordinal in $\beta$source. We will show that $\alpha$source is comparable with $\beta$source. By induction on $\beta$source, it will follow that $\alpha$source is comparable with every ordinal; and so by induction on $\alpha$source, every ordinal is comparable with every ordinal, as required. It suffices to assume that $\alpha \notin \beta$source and $\beta \notin \alpha$source, and show that $\alpha = \beta$source.

To show that $\alpha \subseteq \beta$source, fix $\gamma \in \alpha$source; this is an ordinal by lemma five in chapter “Ordinals”. So by the first induction hypothesis, $\gamma$source is comparable with $\beta$source. But if either $\gamma = \beta$source or $\beta \in \gamma$source then $\beta \in \alpha$source (invoking the fact that $\alpha$source is transitive if necessary), contrary to our assumption; so $\gamma \in \beta$source. Generalising, $\alpha \subseteq \beta$source.

Exactly similar reasoning, using the second induction hypothesis, shows that $\beta \subseteq \alpha$source. So $\alpha = \beta$source.

Corollary three in this chapter

If $\exists \alpha\phi(\alpha)$source, then $\exists \alpha(\phi(\alpha) \land \forall \beta(\phi(\beta) \lif \alpha \leq \beta))$source. Moreover, for any ordinals $\alpha, \beta, \gamma$source, both $\alpha \notin \alpha$source and $\alpha \in \beta \in \gamma \lif \alpha \in \gamma$source.

Proof

Just like proposition one in chapter “Ordinals”.

Exercise three in this chapter

Complete the “exactly similar reasoning” in the proof of theorem “Trichotomy” in chapter “Ordinals”.

Corollary four in this chapter

$A$source is an ordinal iff $A$source is a transitive set of ordinals.

Proof

Left-to-right. By lemma five in chapter “Ordinals”. Right-to-left. If $A$source is a transitive set of ordinals, then $\in$source well-orders $A$source by theorem “Transfinite Induction” in chapter “Ordinals” and theorem “Trichotomy” in chapter “Ordinals”.

Theorem: Burali-Forti Paradox

[Burali-Forti Paradox] There is no set of all the ordinals

Proof

For reductio, suppose $O$source is the set of all ordinals. If $\alpha \in \beta \in O$source, then $\alpha$source is an ordinal, by lemma five in chapter “Ordinals”, so $\alpha \in O$source. So $O$source is transitive, and hence $O$source is an ordinal by corollary four in chapter “Ordinals”. Hence $O \in O$source, contradicting corollary three in chapter “Ordinals”.

Proposition four in this chapter

Any strictly descending sequence of ordinals is finite.

Proof

Any infinite strictly descending sequence of ordinals $\alpha_0 > \alpha_1 > \alpha_2 > \ldots$source has no $<$source-minimal member, contradicting theorem “Transfinite Induction” in chapter “Ordinals”.

Proposition five in this chapter

$\alpha \subseteq \beta \lor \beta \subseteq \alpha$source, for any ordinals $\alpha, \beta$source.

Proof

If $\alpha \in \beta$source, then $\alpha \subseteq \beta$source as $\beta$source is transitive. Similarly, if $\beta \in \alpha$source, then $\beta \subseteq \alpha$source. And if $\alpha = \beta$source, then $\alpha \subseteq \beta$source and $\beta \subseteq \alpha$source. So by theorem “Trichotomy” in chapter “Ordinals” we are done.

Proposition six in this chapter

$\alpha = \beta$source iff $\ordeq{\alpha}{\beta}$source, for any ordinals $\alpha, \beta$source.

Proof

The ordinals are well-orders; so this is immediate from Trichotomy (theorem “Trichotomy” in chapter “Ordinals”) and lemma two in chapter “Ordinals”.

Exercise four in this chapter

Prove that, if every member of $X$source is an ordinal, then $\bigcup X$source is an ordinal.

Axiom: Scheme of Replacement

[Scheme of Replacement] For any formula $\phi(x, y)$source, the following is an axiom:

Definition five in this chapter

For any formula $\phi(x,y)$source which does not contain “$B$source”, the following is an axiom:

Corollary five in this chapter

For any term $\tau(x)$source, and any set $A$source, this set exists:

Proof

Since $\tau$source is a term, $\forall x \lexists![y][\tau(x) = y]$source. A fortiori, $(\forall x \in A)\lexists![y][\tau(x) = y]$source. So $\Setabs{y}{(\exists x \in A)\tau(x) = y}$source exists by Replacement.

Definition six in this chapter

The theory $\ZFminus$source has these axioms: Extensionality, Union, Pairs, Powersets, Infinity, and all instances of the Separation and Replacement schemes. Otherwise put, $\ZFminus$source adds Replacement to $\Zminus$source.

Theorem five in this chapter

Every well-ordering is isomorphic to a unique ordinal.

Proof

Let $\tuple{A, <}$source be a well-order. By proposition six in chapter “Ordinals”, it is isomorphic to at most one ordinal. So, for reductio, suppose $\tuple{A, <}$source is not isomorphic to any ordinal. We will first “make $\tuple{A, <}$source as small as possible”. In detail: if some proper initial segment $\tuple{A_a, <_a}$source is not isomorphic to any ordinal, there is a least $a \in A$source with that property; then let $B = A_a$source and $\mathord{\lessdot} = \mathord{<_a}$source. Otherwise, let $B = A$source and $\mathord{\lessdot} = \mathord{<}$source.

By definition, every proper initial segment of $B$source is isomorphic to some ordinal, which is unique as above. So by Replacement, the following set exists, and is a function:

To complete the reductio, we'll show that $f$source is an isomorphism $\alpha \to B$source, for some ordinal $\alpha$source.

It is obvious that $\ran{f} = B$source. And by lemma four in chapter “Ordinals”, $f$source preserves ordering, i.e., $\gamma \in \beta$source iff $f(\gamma) \lessdot f(\beta)$source. To show that $\dom{f}$source is an ordinal, by corollary four in chapter “Ordinals” it suffices to show that $\dom{f}$source is transitive. So fix $\beta \in \dom{f}$source, i.e., $\ordeq{\beta}{\tuple{B_b, \lessdot_b}}$source for some $b$source. If $\gamma \in \beta$source, then $\gamma \in \dom{f}$source by lemma three in chapter “Ordinals”; generalising, $\beta \subseteq \dom{f}$source.

Definition seven in this chapter

If $\tuple{A, <}$source is a well-ordering, then its order type, $\ordtype{A, <}$source, is the unique ordinal $\alpha$source such that $\ordeq{\tuple{A, < }}{\alpha}$source.

Corollary six in this chapter

Where $\tuple{A, <}$source and $\tuple{B, \lessdot}$source are well-orderings:

Proof

The identity holds by proposition six in chapter “Ordinals”. To prove the second claim, let $\ordtype{A, <} = \alpha$source and $\ordtype{B, \lessdot} = \beta$source, and let $f \colon \beta \to \tuple {B, \lessdot}$source be our isomorphism. Then:

by proposition three in chapter “Ordinals”, lemma three in chapter “Ordinals”, and corollary two in chapter “Ordinals”.

Definition eight in this chapter

For any ordinal $\alpha$source, its successor is $\ordsucc{\alpha} =\alpha \cup \{\alpha\}$source. We say that $\alpha$source is a successor ordinal if $\ordsucc{\beta} = \alpha$source for some ordinal $\beta$source. We say that $\alpha$source is a limit ordinal iff $\alpha$source is neither empty nor a successor ordinal.

Proposition seven in this chapter

For any ordinal $\alpha$source:

1. $\alpha \in \ordsucc{\alpha}$source;

2. $\ordsucc{\alpha}$source is an ordinal;

3. there is no ordinal $\beta$source such that $\alpha \in \beta \in \ordsucc{\alpha}$source.

Proof

Trivially, $\alpha \in \alpha \cup \{\alpha\} = \ordsucc{\alpha}$source. Equally, $\ordsucc{\alpha}$source is a transitive set of ordinals, and hence an ordinal by corollary four in chapter “Ordinals”. And it is impossible that $\alpha \in \beta \in \ordsucc{\alpha}$source, since then either $\beta \in \alpha$source or $\beta = \alpha$source, contradicting corollary three in chapter “Ordinals”.

Theorem: Simple Transfinite Induction

[Simple Transfinite Induction] Let $\phi(x)$source be a formula such that:

1. $\phi(\emptyset)$source; and

2. for any ordinal $\alpha$source, if $\phi(\alpha)$source then $\phi(\ordsucc{\alpha})$source; and

3. if $\alpha$source is a limit ordinal and $(\forall \beta \in \alpha)\phi(\beta)$source, then $\phi(\alpha)$source.

Then $\forall \alpha \phi(\alpha)$source.

Proof

We prove the contrapositive. So, suppose there is some ordinal which is $\lnot\phi$source; let $\gamma$source be the least such ordinal. Then either $\gamma = \emptyset$source, or $\gamma = \ordsucc{\alpha}$source for some $\alpha$source such that $\phi(\alpha)$source; or $\gamma$source is a limit ordinal and $(\forall \beta \in \gamma)\phi(\beta)$source.

Definition nine in this chapter

If $X$source is a set of ordinals, then $\supstrict(X) = \bigcup_{\alpha \in X} \ordsucc{\alpha}$source.

Proposition eight in this chapter

If $X$source is a set of ordinals, $\supstrict(X)$source is the least ordinal greater than every ordinal in $X$source.

Proof

Let $Y = \Setabs{\ordsucc{\alpha}}{\alpha \in X}$source, so that $\supstrict(X) = \bigcup Y$source. Since ordinals are transitive and every member of an ordinal is an ordinal, $\supstrict(X)$source is a transitive set of ordinals, and so is an ordinal by corollary four in chapter “Ordinals”.

If $\alpha \in X$source, then $\ordsucc{\alpha} \in Y$source, so $\ordsucc{\alpha} \subseteq \bigcup Y = \supstrict(X)$source, and hence $\alpha \in \supstrict(X)$source. So $\supstrict(X)$source is strictly greater than every ordinal in $X$source.

Conversely, if $\alpha \in \supstrict(X)$source, then $\alpha \in \ordsucc{\beta} \in Y$source for some $\beta \in X$source, so that $\alpha \leq \beta \in X$source. So $\supstrict(X)$source is the least strict upper bound on $X$source.