Ordinals, Cardinals, and Transfinite Recursion

Let $W$ be a set. A well-order on $W$ is a total order $\le$ on $W$ (Partial order and partially ordered set) with the property that

$\text{every nonempty }S\subseteq W\text{ has a least element, i.e. an }\mathrm{\ell }\in S\text{ with }\mathrm{\ell }\le s\text{ for all }s\in S\mathrm{.}$

The pair $(W,\le )$ is then a well-ordered set, and $W$ is well-ordered by $\le$.

A least element of $S$ is unique when it exists: two of them are below each other, hence equal by antisymmetry (Partial order and partially ordered set). We may therefore write $\min S$ for it.

Strict form. Everything on this page is more convenient in terms of the associated strict order $x<y:⟺(x\le y\text{ and }x\mathrm{\ne }y)$ (Partial order and partially ordered set). Spelled out strictly, a well-order on $W$ is a relation $<$ that is

• irreflexive: $x<x$ holds for no $x\in W$;
• transitive: $x<y$ and $y<z$ imply $x<z$;
• trichotomous: for all $x,y\in W$ exactly one of $x<y$, $x=y$, $y<x$ holds;
• and such that every nonempty $S\subseteq W$ has an element $\mathrm{\ell }$ with no $s\in S$ satisfying $s<\mathrm{\ell }$.

The two presentations determine each other by $x\le y⟺(x<y$ or $x=y)$, and we write $(W,<)$ or $(W,\le )$ as convenient.

• Totality is not an extra hypothesis. If $\le$ is a partial order on $W$ in which every nonempty subset has a least element, then $\le$ is already total: apply the hypothesis to the two element subset $\{x,y\}$, whose least element is below the other. Totality is nevertheless stated, because in the strict presentation trichotomy has to be written down explicitly.
• A well-order is total, so every subset of a well-ordered set is a chain (Chain in a poset), and $W$ itself is one. Chains are therefore not the interesting invariant here; the least element property is.
• The model case is $(\mathbb{N},\le )$, which is a linear order ($\le$ is a linear order on $\mathbb{N}$) in which every nonempty subset has a least element (The well-ordering principle). Ordinals, defined later on this page, are the exact generalisation of that picture.
• $(\mathbb{Z},\le )$ and $(\mathbb{R},\le )$ are total orders but not well-orders: $\mathbb{Z}$ has no least element at all, and the bounded set $\{x\in \mathbb{R}:0<x<1\}$ has none either. Being bounded below does not help, which is exactly why well-ordering is a strong condition.
• The empty set carries exactly one well-order, the empty relation, vacuously. Every one element set carries exactly one.
• A well-order admits no infinite strictly decreasing sequence $x_0>x_1>x_2>\cdots$, since the set of its terms would have no least element. That direction is a theorem of ZF and is used freely here. The converse, that a total order with no infinite strictly decreasing sequence is a well-order, is a different matter: the natural argument takes a nonempty $S$ with no least element and assembles a decreasing sequence inside it by choosing each term below the previous one, which is exactly the principle of dependent choice (DC), described in The Axiom of Countable Choice (${\mathrm{A}\mathrm{C}}_{\omega }$). DC is not a theorem of ZF unless ZF is inconsistent; that much is recorded in the ledger (The choice ledger: what costs the Axiom of Choice and what does not), which lists DC among the principles not provable in ZF. Granted the consistency of ZF, the converse above is likewise unprovable in ZF, and this is a separate statement that the ledger does not record. The witness for it that the library does record is Cohen's first model (Cohen's first model: an infinite Dedekind-finite set of reals ‡), which contains an infinite set $A\subseteq \mathbb{R}$ with no countably infinite subset. Order $A$ by the order it inherits from $\mathbb{R}$: a strictly decreasing sequence in $A$ would be an injection $\mathbb{N}\to A$, so there is none, while $A$ is not well ordered, since a well-ordered infinite set is order isomorphic to an ordinal at least $\omega$ (Every well-order has a unique order type) and so does have a countably infinite subset. Both statements are external metamathematical results, established by forcing and permutation models; they are quoted from the references below, and neither is proved anywhere in this library, which contains neither technique. Nothing on this page depends on any of it: the library takes the least element formulation as the definition and never uses the descending sequence characterisation, precisely so that no result here inherits that cost.

Let $(P,{\le }_P)$ and $(Q,{\le }_Q)$ be posets (Partial order and partially ordered set).

A function $f:P\to Q$ is an order embedding when for all $x,y\in P$

$x{\le }_{P}y⟺f(x){\le }_{Q}f(y)\mathrm{.}$

An order embedding is automatically injective: $f(x)=f(y)$ gives $f(x){\le }_{Q}f(y)$ and $f(y){\le }_{Q}f(x)$, hence $x{\le }_{P}y$ and $y{\le }_{P}x$, hence $x=y$ by antisymmetry (Partial order and partially ordered set).

An order isomorphism is a surjective order embedding, equivalently a bijection $f:P\to Q$ with $x{\le }_{P}y⟺f(x){\le }_{Q}f(y)$ for all $x,y\in P$. The posets $P$ and $Q$ are order isomorphic, written $P\cong Q$, when an order isomorphism $P\to Q$ exists.

• The condition is an equivalence, not an implication. A bijection satisfying only $x{\le }_{P}y\Rightarrow f(x){\le }_{Q}f(y)$ need not be an order isomorphism: let $P=\{a,b\}$ carry the discrete order, in which $a$ and $b$ are incomparable, and let $Q=\{0,1\}$ carry $0<1$. The bijection $a\mapsto 0$, $b\mapsto 1$ preserves every relation of $P$, because $P$ has none beyond reflexivity, yet its inverse does not preserve $0<1$.
• For total orders the implication form does suffice. If $P$ and $Q$ are totally ordered and $f:P\to Q$ is a bijection with $x{<}_{P}y\Rightarrow f(x){<}_{Q}f(y)$, then $f$ is an order isomorphism: given $f(x){<}_{Q}f(y)$, the alternative $y{\le }_{P}x$ would give $f(y){\le }_{Q}f(x)$, which is impossible. Since a well-order is total (Well-order and well-ordered set), a strictly increasing bijection between well-orders is automatically an order isomorphism.
• Strict form. An order isomorphism satisfies $x{<}_{P}y⟺f(x){<}_{Q}f(y)$, because it is injective and preserves both $\le$ and $=$ in both directions.
• The identity is an order isomorphism, the inverse of an order isomorphism is one, and a composite of two is one. Hence $\cong$ is reflexive, symmetric and transitive on any set of posets. It is not a relation on "all posets", since there is no set of all posets.
• Order isomorphisms transport well-ordering. If $f:P\to Q$ is an order isomorphism and $(P,{\le }_P)$ is a well-order (Well-order and well-ordered set), so is $(Q,{\le }_Q)$: totality transfers because $f$ is a surjective embedding, and a nonempty $S\subseteq Q$ has $f^{-1}[S]$ nonempty, whose least element $\mathrm{\ell }$ is carried by $f$ to a least element of $S$. This transfer is used repeatedly below and is the reason order isomorphism, rather than mere bijection, is the right notion of sameness here.
• Order isomorphisms respect initial segments. If $f:P\to Q$ is an order isomorphism and $x\in P$, then $f$ carries $\{y\in P:y{<}_{P}x\}$ onto $\{z\in Q:z{<}_{Q}f(x)\}$: the strict form gives the inclusion one way, and surjectivity gives it the other, since $z{<}_{Q}f(x)$ has the form $z=f(y)$ with $y{<}_{P}x$. Consequently the restriction of $f$ to that set is again an order isomorphism.
• Functions, bijections, ordered pairs and Cartesian products are built in this library, at A function is a relation $f$ with $(a,b)\in f$ and $(a,c)\in f$ implying $b=c$; $f:A\to B$, the value $f(a)$, domain and codomain, Injection, surjection, bijection, The Kuratowski ordered pair $(a,b):=\{\{a\},\{a,b\}\}$ and The Cartesian product $A\times B:=\{z\in \mathcal{P}(\mathcal{P}(A\cup B)):\mathrm{\exists }a\in A\mathrm{\exists }b\in Bz=(a,b)\}$; "subset" and "union" are built alongside them. This item fixes only the order-theoretic terminology on top of that vocabulary.

Let $(W,<)$ be a well-order (Well-order and well-ordered set).

A subset $I\subseteq W$ is an initial segment of $W$ when it is downward closed: if $x\in I$ and $y<x$ then $y\in I$. It is a proper initial segment when $I\mathrm{\ne }W$.

For $a\in W$ write

$W_{<a}:=\{x\in W:x<a\},W_{\le a}:=\{x\in W:x\le a\}=W_{<a}\cup \{a\},$

and call $W_{<a}$ the initial segment determined by $a$.

Every initial segment $I$, carrying the order inherited from $W$, is itself a well-order: the inherited order is total, and a nonempty subset of $I$ is a nonempty subset of $W$, so it has a least element, which lies in $I$.

• $\mathrm{\varnothing }$ and $W$ are initial segments of $W$; each $W_{<a}$ is a proper initial segment, since $a\mathrm{\notin }{W}_{<a}$ by irreflexivity; and each $W_{\le a}$ is an initial segment.
• Every proper initial segment is $W_{<a}$ for exactly one $a$. Let $I⊊W$ be an initial segment and put $a=\min (W\setminus I)$, which exists because $W\setminus I$ is a nonempty subset of the well-order $W$ (Well-order and well-ordered set). If $x<a$ then $x\mathrm{\notin }W\setminus I$ by minimality of $a$, so $x\in I$; hence $W_{<a}\subseteq I$. Conversely let $x\in I$. Then $x\mathrm{\ne }a$, because $a\mathrm{\notin }I$, and $a<x$ is impossible, because downward closure would then put $a\in I$; so $x<a$ by trichotomy, and $I\subseteq W_{<a}$. Therefore $I=W_{<a}$. For uniqueness, suppose $W_{<a}=W_{<b}$ with $a\mathrm{\ne }b$, say $a<b$; then $a\in W_{<b}=W_{<a}$, that is $a<a$, which is impossible.
• Nesting. If $b<a$ then $(W_{<a}{)}_{<b}=W_{<b}$, so an initial segment of an initial segment of $W$ is an initial segment of $W$. This is used whenever two well-orders are compared.
• The initial segments of $W$ are therefore exactly the sets $W_{<a}$ for $a\in W$, together with $W$ itself, and inclusion orders them in the same shape as $W$ with one extra element added on top.
• The corresponding notion for a general poset would be a downward closed set, or "lower set". Nothing on this page needs it outside the well-ordered case, so the definition is stated only there, where the second clause above makes the family of initial segments completely explicit.

Let $(W,<)$ be a well-order (Well-order and well-ordered set) and let $S\subseteq W$ satisfy the following: for every $a\in W$, if $W_{<a}\subseteq S$ then $a\in S$ (Initial segment of a well-order). Then $S=W$.

In property form: if a property $P$ of elements of $W$ satisfies "whenever $P(x)$ holds for every $x<a$, it holds at $a$", then $P(a)$ holds for every $a\in W$.

This is a theorem of ZF. No form of the Axiom of Choice is used. Choice is perfectly available at this point in the library, since Zorn's lemma is proved from it on the previous page; the claim made here is about this proof, which never invokes it.

Where the well-ordering is used. Only once, to produce the least element of $W\setminus S$. Nothing else about $W$ enters the argument, so the same proof establishes the statement for an arbitrary well-founded relation once that notion is available.

No separate base case. Applying the hypothesis at $a=\min W$, when $W$ is nonempty, forces $\min W\in S$, because the initial segment below $\min W$ is empty and is therefore contained in $S$ vacuously. This is why transfinite induction is stated with a single clause where ordinary induction has two, and it is also why the statement holds vacuously for $W=\mathrm{\varnothing }$.

Successors and limits. The scheme that looks stronger, with one clause for the least element, one for successors and one for limits, is the specialisation of this theorem to a well-order in which those three kinds of element are distinguished. Nothing is gained by assuming it separately, and the three-clause form is what gets used once ordinals are available.

Least counterexample. The dual reading is often the useful one: if $S\mathrm{\ne }W$ then the hypothesis must fail somewhere, so there is a least $a$ with $a\mathrm{\notin }S$ and every $x<a$ in $S$. Steps 2.1 to 5.1 are precisely the construction of that least counterexample.

Let $(W,<)$ be a well-order (Well-order and well-ordered set) and let $G$ be a class function: a rule, given by a formula in the language of set theory, that assigns a set $G(h)$ to every function $h$ whose domain is a proper initial segment of $W$ (Initial segment of a well-order). Then there is exactly one function $F$ with domain $W$ such that

$F(a)=G(F\upharpoonright W_{<a})\text{for every }a\in W\mathrm{.}$

Here $F\upharpoonright W_{<a}$ is the restriction of $F$ to the initial segment determined by $a$, so the value of $F$ at $a$ is prescribed in terms of all its earlier values at once.

Because $G$ is a class function rather than a set, this is a theorem schema of ZF: one theorem for each formula defining $G$. It uses Replacement, and it uses no form of the Axiom of Choice.

Which axioms are spent. Separation produces $T$ in step 5.1; Replacement produces the sets of attempts in steps 7.1 and 11.1; Union assembles them. Replacement is genuinely needed and cannot be traded away: the attempts $h_a$ are not subsets of any single set given in advance, so Separation alone cannot collect them. This is the standard reason transfinite recursion is unavailable in Zermelo set theory without Replacement.

No choice is used, and the reason is uniqueness. At every stage the object to be used is the unique attempt with a given domain, singled out by step 4.1, never one of many candidates. A construction phrased as "at stage $a$ pick some element not yet used" is a different theorem and does cost a choice principle; the difference is exactly the content of FALSE: transfinite induction and recursion need the Axiom of Choice.

Class function, not a set function. $G$ has to be allowed to take values anywhere in the universe, since $F(a)$ may be an arbitrary set, so $G$ cannot be assumed to be a set of ordered pairs. That is why the result is a schema. When $G$ happens to be an honest set function, defined on the set of all functions from proper initial segments of $W$ into a fixed set $A$ and taking values in $A$, the statement is an ordinary theorem of ZF and the same proof applies verbatim.

Relation to ordinary recursion. Taking $W=\mathbb{N}$ recovers the familiar recursion on the natural numbers, but not literally the published The recursion theorem: that theorem prescribes $g(\sigma (n))$ in terms of $g(n)$ alone, whereas $G$ here sees the whole earlier history $F\upharpoonright W_{<a}$. Course-of-values recursion on $\mathbb{N}$ is the special case of the present theorem, and it is what later pages use whenever a construction at stage $n$ consults all earlier stages.

Let $(W,<)$ be a well-order (Well-order and well-ordered set) and let $f:W\to W$ be strictly increasing, that is $x<y\Rightarrow f(x)<f(y)$. Then:

(a) $a\le f(a)$ for every $a\in W$;

(b) $W$ is not order isomorphic (Order embedding and order isomorphism) to any proper initial segment $W_{<a}$ of itself (Initial segment of a well-order);

(c) the identity is the only order isomorphism $W\to W$;

(d) for any two well-orders $V$ and $W$ there is at most one order isomorphism $V\to W$.

This is a theorem of ZF; no choice principle is used.

Transfinite induction in disguise. Steps 1.1 to 4.1 are exactly the proof of Transfinite induction specialised to the set $S=\{a\in W:a\le f(a)\}$: if $x\le f(x)$ for all $x<a$ then $a\le f(a)$, because $f(a)<a$ would put $f(a)$ below $a$ with $f(f(a))<f(a)$. The argument can therefore be run by citing that theorem instead of taking a least element by hand, and nothing changes.

Rigidity is what makes order types well defined. Claim (d) says a well-order has no room for a nontrivial symmetry, so "the" isomorphism between two isomorphic well-orders is unique and can be spoken of without choosing anything. That is precisely why no choice principle appears anywhere in the comparison of well-orders (Comparability of well-orders) or in the assignment of order types (Every well-order has a unique order type).

Totality is essential. For a general poset every claim here fails. On the poset $\{a,b\}$ with $a$ and $b$ incomparable, the swap $a\mapsto b$, $b\mapsto a$ is a nonidentity order automorphism, and the strictly increasing condition is vacuous. It is the least element property, used once in step 2.1, that removes this freedom.

Only one direction is available. Claim (a) says $f$ never moves a point strictly down, and no bound in the other direction holds: on $(\mathbb{N},\le )$ the map $n\mapsto 2n$ is strictly increasing and moves every nonzero point strictly up, as far up as one likes.

Let $(V,{<}_V)$ and $(W,{<}_W)$ be well-orders (Well-order and well-ordered set). Then exactly one of the following holds (Order embedding and order isomorphism, Initial segment of a well-order):

(i) $V\cong W$;

(ii) $V\cong W_{<b}$ for a unique $b\in W$;

(iii) $V_{<a}\cong W$ for a unique $a\in V$.

In particular any two well-orders are comparable: one of them is order isomorphic to an initial segment of the other. No choice principle is used, which is what makes this the choice-free substitute for cardinal comparability.

Where no choice enters. The relation $f$ is carved out of $V\times W$ by Separation, and the isomorphisms witnessing $V_{<v}\cong W_{<w}$ are never selected: by rigidity (Rigidity of well-orders) there is at most one of them, so the definition of $f$ quantifies over them rather than picking one. That is the entire reason comparability of well-orders is a ZF theorem while comparability of arbitrary sets is not.

An alternative proof by recursion. One can instead define $f$ by transfinite recursion (Transfinite recursion), sending $v$ to the least element of $W$ not already in the image of $V_{<v}$, and stopping when $W$ is exhausted. That route needs the recursion theorem and a little care about where the construction halts; the argument above needs only Separation and is recorded here for that reason.

Comparability is not trichotomy of size. The statement compares well-orders, not sets. Two sets need not be comparable in size in ZF at all; that they always are is equivalent to the Axiom of Choice. What survives choice-free is this lemma together with Hartogs: an ordinal that does not inject into a given set, and the ledger of what each costs is The choice ledger: what costs the Axiom of Choice and what does not.

Reading it as a linear order on order types. Once every well-order is assigned an ordinal (Every well-order has a unique order type), case (ii) reads "the order type of $V$ is smaller than that of $W$" and case (iii) reads the reverse, so this lemma is the statement that the ordinals are linearly ordered, proved before ordinals are available.

A set $\alpha$ is an ordinal when both of the following hold.

1. $\alpha$ is a transitive set: every element of $\alpha$ is also a subset of $\alpha$, that is $x\in \alpha \Rightarrow x\subseteq \alpha$.
2. The membership relation restricted to $\alpha$, namely $\{(x,y)\in \alpha \times \alpha :x\in y\}$, is a strict well-order of $\alpha$ (Well-order and well-ordered set): it is irreflexive, transitive as a relation, trichotomous on $\alpha$, and every nonempty subset of $\alpha$ has an $\in$-least element.

Ordinals are written with lowercase Greek letters, and for ordinals we set

$\alpha <\beta :⟺\alpha \in \beta ,\alpha \le \beta :⟺(\alpha \in \beta \text{ or }\alpha =\beta )\mathrm{.}$

Write $0:=\mathrm{\varnothing }$, which is an ordinal because both clauses hold vacuously, and write ${\alpha }^{+}:=\alpha \cup \{\alpha \}$ for the successor of $\alpha$.

• Two different transitivities. Clause 1 is about the set $\alpha$: it contains all members of its members. Clause 2 asks in part that the relation $\in$ be transitive on $\alpha$. If every element of $\alpha$ is itself a transitive set then the relation $\in$ is transitive on $\alpha$; the converse holds given clause 1, and fails without it. For $\alpha =\{\{\{\mathrm{\varnothing }\}\}\}$ the relation $\{(x,y)\in \alpha \times \alpha :x\in y\}$ is empty, hence vacuously transitive, yet the sole element $\{\{\mathrm{\varnothing }\}\}$ of $\alpha$ is not a transitive set, since $\{\mathrm{\varnothing }\}\in \{\{\mathrm{\varnothing }\}\}$ while $\mathrm{\varnothing }\mathrm{\notin }\{\{\mathrm{\varnothing }\}\}$. Under clause 1 the two readings do coincide, because then every member of a member of $\alpha$ again lies in $\alpha$, where the relation has something to say. Neither clause implies the other, and both are needed.
• Every ordinal is literally the set of all smaller ordinals. By clause 1 and the notation above, $\alpha =\{\beta :\beta <\alpha \}$, so the ordinals carry their own order relation as membership. This is von Neumann's device, and it is what makes it unnecessary to define an order type as an equivalence class of well-orders: apart from the class of the empty well-order, which is the singleton $\{\mathrm{\varnothing }\}$, such a class is a proper class rather than a set, whereas the representative chosen here is always a set.
• The natural numbers are ordinals, and so is $\omega$. Each natural number is a transitive set (Every natural number is a transitive set and is not a member of itself), and on $\mathbb{N}$ membership coincides with the usual strict order, so each natural number and $\mathbb{N}=\omega$ itself (The natural numbers $\mathbb{N}$ (von Neumann)) satisfy both clauses. Both facts are proved in $\omega$ is the least limit ordinal, where they are needed; they are recorded here because they are the intended picture.
• The Axiom of Foundation is not used here. Some treatments define an ordinal as a transitive set linearly ordered by $\in$, which is equivalent to the definition above only in the presence of Foundation (The Axiom of Foundation: $\mathrm{\forall }S(\mathrm{\exists }t(t\in S)\to \mathrm{\exists }s(s\in S\wedge \mathrm{\neg }\mathrm{\exists }u(u\in s\wedge u\in S)))$), since Foundation is what supplies the least element. The least element property is written into the definition instead, so nothing on this page depends on Foundation even though the library does state it as an axiom of ZFC.
• The definition is absolute in a strong sense: whether a set is an ordinal depends only on its members and the membership relation among them, with no reference to any ambient construction. That is why ordinals can be used to index constructions in any model of ZF without further hypotheses.

Let $\alpha$ and $\beta$ be ordinals (Ordinal (von Neumann)). Then:

(a) every element of $\alpha$ is an ordinal;

(b) $\alpha \mathrm{\notin }\alpha$;

(c) ${\alpha }^{+}=\alpha \cup \{\alpha \}$ is an ordinal;

(d) if $A$ is a nonempty set of ordinals then $\bigcap A$ is an ordinal;

(e) if $A$ is any set of ordinals then $\bigcup A$ is an ordinal;

(f) $\alpha \subseteq \beta$ if and only if $\alpha \in \beta$ or $\alpha =\beta$;

(g) any two ordinals are comparable under inclusion: $\alpha \subseteq \beta$ or $\beta \subseteq \alpha$.

Everything here is a theorem of ZF and uses no choice principle.

The successor is the immediate successor. Claim (c) makes ${\alpha }^{+}$ an ordinal, and it is the least ordinal strictly above $\alpha$: any $\gamma$ with $\alpha \in \gamma$ satisfies ${\alpha }^{+}\subseteq \gamma$, hence ${\alpha }^{+}\le \gamma$ by claim (f). So the ordinals have no gaps immediately above a given point, which is what makes the successor and limit dichotomy of Successor and limit ordinals exhaustive.

Suprema come for free. Claim (e) says a set of ordinals always has a least upper bound, namely $\bigcup A$: it contains every member of $A$ as a subset, hence lies weakly above each by claim (f), and any ordinal weakly above all of them contains $\bigcup A$. Claim (d) gives the dual statement for a nonempty set. Neither needs any completeness assumption, in sharp contrast with the situation for $\mathbb{R}$.

Nonemptiness in claim (d) is essential. The intersection of the empty family is not a set, so the hypothesis cannot be dropped. The union of the empty family, by contrast, is $\mathrm{\varnothing }=0$, which is why claim (e) needs no such hypothesis.

Claim (g) is a departure from the usual bookkeeping. It is normally derived alongside trichotomy. It is proved here because claim (e) cannot be proved without it, and separating them would either duplicate the argument or create a circular dependency between this lemma and Trichotomy and well-ordering of the ordinals.

The naturals are the model case. Every natural number is a transitive set and satisfies $n\mathrm{\notin }n$ (Every natural number is a transitive set and is not a member of itself), which is exactly claims (a) and (b) in the situation this definition abstracts, and $\sigma (n)=n\cup \{n\}$ is the successor operation of claim (c). That every natural number, and $\omega$ itself, really is an ordinal is proved in $\omega$ is the least limit ordinal.

For ordinals $\alpha$ and $\beta$ (Ordinal (von Neumann)), exactly one of