# Set Theory/Ordinals

## Finite and transfinite ordinal numbers

edit### Historical context

edit### Preliminaries

edit### Standard representation of ordinal numbers

editThe definition of ordinal numbers offers little insight into their nature. In situations like this pure mathematicians create representations of the objects they wish to study. Such representations are built from familiar mathematical constructions and are equivalent to the obstruce objects. By manipulating the familiar objects in the representation, the pure mathematician may thus investigate the structure of the mysterious abstract entities.

The most common representation of the ordinal numbers, due to Von Neumann, is as follows. The ordinal 0 is defined to be the empty set ; the ordinal 1 is defined to be the set , which is of course equal to
. Similarly, the ordinal 2 is the set ; the ordinal 3 is the set ; the ordinal 4 is the set . Any finite ordinal is defined to be the set (or, in a rigorous notation, the *successor* of an ordinal α is defined as the set ).

In fact this definition extends naturally to transfinite ordinals. The ordinal is the set consisting of every finite ordinal . Again, is the set ; is the set ; and so on.

The ordinal (or ) is the set consisting of all finite ordinals and ordinals of the form , where is a finite ordinal. Thus .

The ordinal is the first uncountable ordinal, and is the set of all countable ordinals.

### Well-orderings

editThe basic property of ordinals is well-ordering. This will allow the above informal discussion to be given a formal definition and additionally allow us to prove some necessary basic facts.

**Definition**: a total ordering of a set P is a **well-ordering** of P if every nonempty subset has a minimal element.
**Definition**: an **initial segment** of a well-ordered set W is a set of the form {w∈W|w<v} for some v∈W.

Well-orderings are a kind of "universal order" in the sense that given any two well-ordered sets, one well-ordered set is order-isomorphic to the other or an initial segment of the other. This will be established in the following few theorems.

**Theorem**: any increasing function from a well-ordered set to itself is rising: if (W, <) is a well-ordered set and f: W→W is a function such that x>y→f(x)>f(y), then for all w∈W, f(w)≥w.

- Proof: if {w∈W: f(w)<w} was nonempty, let v=min {w∈W: f(w)<w}. Then f(v)<v, and because f is increasing, f(f(v)) < f(v), so f(v)∈{w∈W: f(w)<w}. Then f(v)≥v because v is the minimum element of that set, contradicting f(v)<v. Therefore, {w∈W: f(w)<w} must be empty.

**Theorem**: any order-automorphism on a well-ordered set is the identity.

- Proof: Given any automorphism f: W→W, both the function and its inverse must be increasing. By the above theorem, we can conclude:
- f(x) ≥ x
- and also f
^{-1}(x) ≥ x - f is increasing, so f(f
^{-1}(x)) ≥ f(x) - Simplifying, x ≥ f(x).
- f(x) = x

**Theorem**: if *f* and *g* are both order isomorphisms of well-ordered sets V and W, then f=g.

- Proof: g
^{-1}∘f and f∘g^{-1}are both automorphisms on V and W respectively, so they are both equal to the identity function.

**Theorem**: There exists no order isomorphism of a well-ordered set to any of its own initial segments.

- Proof: Let (W, <) be a well-ordering and let S
_{v}= {w∈W|w<v} be an initial segment. If f: W→S_{v}is an order isomorphism, then expanding the range of f to W, f is an increasing function to itself so f(v)≥v. But f(v)∈{w∈W|w<v}, so f(v)<v. So, no such f can exist.

**Theorem**: The restriction of an order isomorphism f: W→V to an initial segment S_{w} of W is an order isomorphism of that initial segment to the initial segment S_{f(w)} of V.

- Proof: for any w'∈S
_{w}, f(w')<f(w) so f(w')∈S_{f(w)}, f maps S_{w}into S_{f(w)}. Furthermore, for any v∈S_{f(w)}, v<f(w) so f^{-1}(v)<f^{-1}f(w)) = w, so f^{-1}(v) is in the domain of the restricted function, where f(f^{-1}(v)) = v, meaning that the restricted function f also maps onto S_{f(w)}. Therefore, restricting the domain of f to S_{w}, it is possible to then shrink its range to S_{f(w)}, making it a bijection.

We now finally come to the main idea behind well-orderings.

**Theorem**: Given any two well-ordered sets, one set is order isomorphic to the other or an initial segment of the other.

- Proof: Let (V, <) and (W, <) be two well-ordered sets. First, we establish the following fact using the previous theorem: the set of all w∈W such that the initial segment S
_{w}in W is isomorphic to some initial segment S_{v}for some v∈V is *closed downwards*. Given any w∈W, if such an isomorphism exists for S_{w}, then given any w'<w, there also exists a v'∈V such that S_{w'}is order isomorphic to S_{v'}.

This is because by the above theorem, restricting the isomorphism to the initial segment of w' within S_{v} is an order isomorphism of that segment to the initial segment of f(w') within S_{w}, where f is the order isomorphism. But initial segments within S_{v} are also initial segments within V, because order is transitive, and the same goes for initial segments within W.

Suppose there existed a v∈V where S_{v} is not order isomorphic to any S_{w} for w∈W. Then v belongs to the complement of the above mentioned set and is therefore nonempty: let v_{0} be the least such v. Then any v>v_{0} will also belong to the complement: if S_{v} was isomorphic to some S_{w}, then v_{0}<v implies the same must be true for v, which it is not.

For any v∈S_{v0}, v<v_{0}, and given that v_{0} is the least element for which such an isomorphism does not exist, S_{v} must be isomorphic to some S_{w} for w∈W. Furthermore, such a w must be unique, because if S_{v} was also isomorphic to S_{w'} for w'∈W, then without loss of generality, suppose w'<w and let f and g be the isomorphisms to S_{w} and S_{w'} respectively. Then g∘f^{-1}: S_{w}→S_{w'} is an isomorphism of a well-ordered set to its own initial segment, which was proved to not be possible.

This establishes a function f: S_{v0}→W defined by:

f(v) = the unique w∈W such that S__{v} is order isomorphic to S__{w}

We show that the range of f is also closed downwards, meaning that if w∈f(V) and w'<w, then w'∈f(V). If w∈f(V), then there exists a v∈V such that f(v) = w, so there exists an order isomorphism g from S__{v} and S__{w}. For any w'<w, the restriction of f^{-1} to the initial segment by w' in S_{v} is also an order isomorphism to its initial segment by g^{-1}(w'). As remarked earlier, initial segments within initial segments are also initial segments of the whole, by the transitive property. So, S_{g-1(w')} is order isomorphic to S_{w'}, meaning f(g^{-1}(w')) = w'. Therefore, w'∈f(V).

Now to prove that f is an onto function. Note that if it was not, then the complement of the image set W-f(V) is nonempty, so let w_{0}=min W-f(V). w_{0} being the minimum means that for any w<w_{0}, w∈f(V), so S_{w0}⊆f(V). Conversely, if w∈f(V), then w≠w_{0} because w_{0}∉f(V). Second, if w>w_{0}, then because the range is closed downwards, w_{0}∈f(V), which is false. Therefore, w<w_{0}, so w∈S_{w0}, so f(V)=S_{w0}. But this implies that f is an order isomorphism from S_{v0} to S_{w0}, contradicting that v_{0} is defined to be the least such element of V for which such an isomorphism does not exist. Therefore, W-f(V) must be empty and f is onto.

With all that, f is therefore an order isomorphism between S_{v0} and W.

This takes care of the case where there existed a v∈V where S_{v} is not order isomorphic to any S_{w} for w∈W. The same argument goes for the case where there existed a w∈W where S_{w} is not order isomorphic to any S_{v} for v∈V by applying the same result, switching V and W around, and finding an isomorphism between V and an initial segment of W.

Finally, suppose neither exists, and for every v∈V, S_{v}is order isomorphic to S_{w} for some w∈W, and every S_{w}is order isomorphic to S_{v} for some v∈V. Then the function defined, this time as f: V→W with domain as all of V, will be an order isomorphism between V and W.

Note that only one of these three cases can hold, by the impossibility of an order isomorphism of a well-ordered set with its own initial segment.

### Transitive sets and ordinals

editThe basic ordering under the ordinals is the set inclusion relation, ∈. We establish a class of sets such that a<b whenever a∈b. The basic requirement to be an ordinal is transitivity.

Definition: A set T is transitive if S∈T implies S⊆T. Expanding out the definition of subset: a set T is transitive if for all S∈T and R∈S, R∈T.

In a sense, transitive sets are "closed downwards" by the ∈ relation.

Definition: an **ordinal** is a transitive set that is well-ordered by the ∈ relation.

Keep in mind that well-ordered also implies a linear ordering. The symbols ∈ and < will therefore be used interchangeably for elements of ordinals.

We now establish some basic facts for working with ordinals.

- Theorem: ∅ is an ordinal.
- Proof: it is transitive and well-ordered by ∈ in the vacuous sense.

- Theorem: If β∈α and α is an ordinal, then β is an ordinal.
- Proof: α is transitive so β⊆α, therefore β is also well-ordered by ∈. If γ∈β then γ∈α because β⊆α, and furthermore γ⊆α because α is transitive. Then if δ∈γ, then δ∈α. So δ, γ, and β are all elements of α and δ∈γ∈β, so δ∈β because ∈ is a transitive relation in α.

- Theorem: If β⊆α and β≠α and α and β are both ordinals, then β∈α.
- Proof: α-β is nonempty and a subset of α, let γ = min(α-β).

- If δ∈γ, then δ<γ=min(α-β), so δ∉α-β, meaning δ∈β. Conversely, if δ∈β, then δ∉α-β, and also δ∈α because β⊆α, and α is totally ordered so either δ>γ or δ<γ because they are both elements of α. The first case is actually impossible: γ<δ (or γ∈δ) together with δ∈β implies that γ∈β because β is a transitive set, but γ is supposed to be an element of α-β. Therefore, δ<γ or δ∈γ.
- Therefore, γ=β, and γ∈α-β, so γ∈α.

- Theorem: If α and β are ordinals, one must be a subset of the other.
- Proof: The intersection α∩β is also an ordinal: as a subset of α, it is well-ordered by ∈. It is transitive because if γ∈α∩β, then γ⊆α and γ⊆β, so γ⊆α∩β.

- α∩β must be equal to α or β. Suppose this was not the case: then α∩β⊆α but α∩β≠α so α∩β∈α by the preceding theorem. Likewise, α∩β⊆β but α∩β≠β so α∩β∈β. But α∩β∈α∩β, contradicting that α is well-ordered by ∈ (in particular, ∈ must be a strict order, so it has the anti-reflexive property).

The following corollaries are then easily established.

- Theorem: If α and β are ordinals and α≠β, then α∈β or β∈α. From here on, denote α∈β also as α<β. ∈ is therefore a total ordering of the class of all ordinals.

- Proof: First, verify that ∈ satisfies the transitive and anti-reflexive properties. If α is an ordinal and α∈α, then elements of α need to be well-ordered, in particular anti-reflexive by ∈, which is violated by α∈α. So α∉α for all ordinals. Second, if α, β, and γ are ordinals and α<β, β<γ, then β∈γ and α∈β, therefore α∈γ because γ is a transitive set.
- That ∈ is a total ordering is a consequence of the above theorem.
- Now verify well-orderedness. If C is a nonempty class of ordinals, let α∈C. If α is the minimum of C, then C has a minimum. Else, there exists a β<α where β∈C. Then α∩C is a nonempty subset of α and has a least element, so let γ=min α∩C. Then for all δ∈C, from what was just proven, either δ=α, δ<α, or δ>α. In the first case, γ∈α so γ<α=δ. In the second case, δ∈α so δ∈α∩C, so γ≤δ. In the third case, γ<α and α<δ, so γ<δ. In all three cases, γ≤δ.

- Theorem: If α is an ordinal, then α = {β | β < α}

- Proof: From definition of < between ordinals as ∈.

- Theorem: The intersection of a nonempty class of ordinals is another ordinal and in fact the greatest upper bound (inf) of that class. Henceforth, it shall be denoted inf.

- Proof: Let C be a class of ordinals. Suppose β∈∩C. Then for any γ∈β and δ∈C, β∈δ and δ is an ordinal, so γ∈δ. Therefore, γ∈∩C, so ∩C is transitive. Also, ∩C is a subset of an ordinal, and is therefore well-ordered by ∈.

- Theorem: The union of a set of ordinals is another ordinal, and in fact the least upper bound (sup) of that set. Henceforth, the union of any set of ordinals shall be denoted sup.

- Proof: Let S be a set of ordinals, and let α∈∪S. Then there exists β∈S, α∈β. β is an ordinal and is transitive, so for any γ∈α, γ∈β, thus γ∈∪S. Thus, α⊆∪S, so ∪S is transitive. Furthermore, all elements of ∪S are ordinals, and because all ordinals are well-ordered under < (meaning ∈), any set of ordinals, in particular ∪S is well-ordered under <.

- Theorem: If α is an ordinal, then α∪{α} is an ordinal. If β>α is an ordinal greater than α, then β≥α∪{α}.

- Proof: α∪{α} is a set of ordinals, and so is well-ordered under <. It is transitive: if β∈α∪{α}, either β∈α or β=α. In the first case, if γ∈β, then γ∈α and γα∪{α}, so β⊆α∪{α}. In the second case, β=α⊆α∪{α}.

Denote by S(α)=α∪{α}. S(α) is called the successor of α because by the above, there are no ordinals between them: no ordinal β satisfies α<β<S(α) for any ordinal α. Given any α, if there exists an ordinal β such that α=S(β), then α is called a **successor ordinal**. Else, α is called a **limit ordinal**.

The class of all ordinals *Ord* is not a set. If it was a set, sup Ord is an ordinal and sup Ord≥α for any ordinal. But S(sup Ord) is also an ordinal and S(sup Ord)>sup Ord, a contradiction.

We finally come to the main point of ordinals: as "universal well-ordered functions".

- Theorem: every well-ordered set is order isomorphic to a unique ordinal.

- Proof: Let W be a well-ordered set. Consider the formula "F(w) = α when S
_{w}(the initial segment in W by w) is order isomorphic to the ordinal α".

First, note that for a given w∈W, if such an ordinal exists it is unique (otherwise an ordinal would be isomorphic to its own initial segment), and it also exists for all w'<w, and in fact the order isomorphism on S_{w} equals F, restricted to S_{w}. This is because if o is an order isomorphism between S_{w} and α, then for any w'<w, the restriction of o to S_{w'} is an order isomorphism between S_{w'} and o(w')<α. So F(w') = o(w') < F(w). This also shows that F (and also F^{-1}) is monotone when it is defined.

The reverse is also true: if α=F(w) for some w∈W and β<α, then there exists a w'<w such that β=F(w'). This is because as remarked before, F restricted to S_{w} is an order isomorphism between S_{w} and α, and in particular it is surjective. Furthermore, note that for any w∈W, if F is defined for all w'<w, then it is defined on w and in fact equal to F(S_{w}). First, F is monotone, so it is an isomorphism between its domain an image, so all that's needed is to prove that F(S_{w}) is an ordinal. It is a set of ordinals and thus well-ordered by ∈. Also if α ∈ F(S_{w}) and β<α, then β ∈ F(S_{w}) by what was just proven, so F(S_{w}) is a transitive set. Therefore, F(S_{w}) is an ordinal.

This shows that in fact, F is defined on all of W: otherwise, let v = min { w∈W | S_{w} is not isomorphic to any ordinal }. Then F is defined on all v'<v, so it is defined on v by the above paragraph, a contradiction.

Now adjoin to W one element that is greater than all elements of W, call it m. The resulting set remains a well-ordered set. Then the above statements also apply to this new well-ordered set, and so F(m) is defined it, meaning S_{m} is order isomorphic to the ordinal F(m). But W=S(m).

### First few ordinals

editDefine 0 = ∅. Then define the successors of 0:

1 = S(0), 2 = S(1), 3 = S(2), and so on.

0 is a limit ordinal. Denote by ω the first nonzero limit ordinal. The existence of ω follows from the axiom of infinity. Ordinals that are less than ω are called **finite** or **natural numbers**. The set of natural numbers is sometimes denoted N, which is also equal to ω.

### Induction, recursion

editWell-orderedness allows "counting upwards." This is given in the induction principle:

If a class C satisfies 3 properties:

1. 0∈C 2. α∈C → S(α)∈C 3. α is limit ordinal and (β<α→β∈C) together imply α∈C

Then C contains all ordinals. This follows from well-ordering: if Ord-C is nonempty, then min(Ord-C) is either 0, a successor ordinal, or a nonzero limit ordinal. Then either 0∉C (violating 1), S(α)=min(Ord-C) for some α implying α∈ while S(α)∉C (violating 2), or min(Ord-C) is a limit ordinal and all β<min(Ord-C) are elements of C by minimality, violating 3.

One main purpose of induction is defining recursive functions, namely proving that such a recursive function exist. When recursion is done on ordinals, it is often called "transfinite recursion." The main idea is that given a "class function" G that takes in functions with domain being an ordinal, there exists a unique class function F such that F(α)=G(F restricted to α) for all ordinals α. Note that "restricted to α" means a domain restricted to all elements of α, meaning all ordinals less than α.

Proof of transfinite recursion:

### Ordinal arithmetic

editAddition, multiplication, and exponentiation can now be defined using transfinite recursion.