* Order Structures

Contents
Contents
 1.  Isomorphic well-orders
 2.  Ordinal Numbers

(Continued.)

1. Isomorphic well-orders In this section we study the well-orders that "look alike". They are called isomorphic well-orders. Then in the next section we will use the transfinite recursion theorem to construct ordinal numbers on a well-order structure (A,\leqslant). By transfinite recursion we have a mapping F with domain A such that for any a\in A, F(a)=F(\downarrow<a)=\{F(x)\mid x<a\}. We will see the range of F is the ordinal number we want.

With the notations above, let \alpha be the range of F. This is a set equinumerous to A, as we will show, and there is more similarity. A well-order on A induces a well-order on \alpha under \in.

The similarity between two structures can be formalized in terms of isomorphisms. This is a general concept in mathematics.

Consider two relations \mathcal R,\mathcal R' on two sets A,A' respectively. If there is a bijection f:A\to A' such that
\[a\mathcal Rb\Leftrightarrow f(a)\mathcal R'f(b),\]

we call f an isomorphism from (A,\mathcal R) onto (A',\mathcal R'), and say (A,\mathcal R) is isomorphic to (A',\mathcal R'), denoted by (A,\mathcal R)\cong (A',\mathcal R'). When the context is clear, we can simply write A\cong A'.

It is not difficult to check that isomorphism relation \cong has the properties of an equivalence relation: reflexivity, symmetry and transitivity.

The following proposition is also not difficult to prove. (proof omitted)

For two well-order structures, we can always find an isomorphism inside them: Either they are isomorphic or one is isomorphic to a segment of the other. We begin with the following easy proposition. (proof omitted)

If one is sloppy this order is simply denoted by (B,\leqslant). A more precise but convenient notation might be (B,\leqslant^\circ), in which {}^\circ is used to indicate that the order is \leqslant restricted to B\times B.

The following theorem indicates the possibility to "compare" two sets.

The proof of it and the following two theorems will be given soon. Before that, let us return to the investigation of \alpha.

Define a binary relation \leqslant _ \alpha on \alpha such that F(a)\leqslant _ \alpha F(b) if and only if F(a)\in F(b) or a=b. First we show that F(a)\notin F(a) for any a\in A, implying at most one of the conditions can hold. Let S=\{a\in A\mid F(a)\in F(a)\}. If it is nonempty, it has a least element m. We have F(m)\in F(m)=F(\downarrow< m), so there is an element m'<m such that F(m)=F(m'), indicating F(m')\in F(m'), contradicting the leastness of m. Hence S=\varnothing and F(a)\notin F(a) for any a\in A.

With this property, we will further prove the following theorem.

A set S is called transitive if y\in x\in S\Rightarrow y\in S, or equivalently, x\in S\Rightarrow x\subseteq S. It is not difficult to see that \alpha is a transitive set. It turns out that we can use a transitive set to characterize a well-order structure.

The following theorem is the key for the construction of ordinal numbers.

Proofs. For Theorem 3, the idea is to pair the elements of the two sets in the natural way. The pairing is obtained by transfinite recursion.

We pick u\notin B. Then by transfinite recursion, there exists a unique mapping F on A such that
\[
F(a)=\begin{cases}
\min(B\setminus F(\downarrow< _ A a)),&B\setminus F(\downarrow< _ A a)\neq\varnothing,\\
u,&B\setminus F(\downarrow< _ A a)=\varnothing.
\end{cases}
\]

Here \min(\cdot) is the least element of a nonempty set. There are three cases for the range of F: u\in F(A), F(A)=B and F(A)\subsetneq B.

Case 1. The set \{x\in A\mid F(x)=u\} is nonempty and then has a least element a. We show F| _ {\downarrow< _ Aa} is an isomorphism from (\downarrow<a,\leqslant _ A^\circ) to (B,\leqslant _ B). For notational convenience, we denote F| _ {\downarrow< _ Aa} simply by F in this case.

We can see that the range of F is just B, i.e., F is surjective. Suppose x _ 1\leqslant _ A x _ 2< _ A a. Then \downarrow< _ Ax _ 1\subseteq {\downarrow< _ A}x _ 2 and F(\downarrow< _ Ax _ 1)\subseteq F({\downarrow< _ A}x _ 2), so B\setminus F(\downarrow< _ Ax _ 2)\subseteq B\setminus F(\downarrow< _ Ax _ 1), indicating F(x _ 1)\leqslant _ B F(x _ 2).

If in addition x _ 1,x _ 2 are distinct, then F(x _ 1)\neq F(x _ 2), because F(x _ 1)\in F(\downarrow< _ A x _ 2) but F(x _ 2)\in B\setminus F(\downarrow< _ A x _ 2). Therefore F(x _ 1)\neq F(x _ 2) and F is injective. We conclude that F is an isomorphism from (\downarrow<a,\leqslant _ A^\circ) to (B,\leqslant _ B).

Case 2. If F(A)=B, we can apply the same argument as Case 1. In this case (A,\leqslant _ A)\cong(B,\leqslant _ B).

Case 3. The range of F is a proper subset of B. Suppose b=\min(B\setminus F(A)). We show F(A)=\downarrow< _ Bb. By definition \downarrow< _ Bb\subseteq F(A). For any x\in A, F(x) is the least element of B\setminus F(\downarrow< _ A x), and this is a set containing b. Hence F(x)\leqslant _ B b, so F(x)< _ B b by b\notin F(A).

It still holds that F is injective and preserves order, so in this case (A,\leqslant _ A)\cong(\downarrow< _ Bb,\leqslant^\circ _ B)
.

Next we turn to Theorem 4. By definition of \alpha, F is surjective. We show F is also injective. Suppose a\neq a' and a is the smaller one. Then F(a)\in F(a'), and knowing that F(a')\notin F(a') we infer F(a)\neq F(a'). Therefore F is bijective and A\sim\alpha.

Now if a\leqslant b, then either a<b or a=b. We have shown F(a)\leqslant _ \alpha F(b)\wedge (a\neq b) if and only if F(a)\in F(b), so it suffices to show a<b if and only if F(a)\in F(b). The "only if " part is immediate. For the "if" part, suppose F(a)\in F(b)=\{F(x)\mid x<b\}. There is some c<b such that F(a)=F(c). Since F is injective, a=c, so a<b.

It can be seen easily that F(a)< _ \alpha F(b) is just F(a)\in F(b).
.

Finally, Theorem 5. If \alpha _ 1=\alpha _ 2=\alpha, then (A _ 1,\leqslant _ 1)\cong (\alpha,\leqslant _ \alpha)\cong (A _ 2,\leqslant _ 2). Conversely, suppose f:A _ 1\to A _ 2 is an isomorphism from A _ 1 onto A _ 2, and F _ 1:A _ 1\to\alpha _ 1 and F _ 2:A _ 2\to\alpha _ 2 are the usual isomorphisms of the well-orders. We assert that F _ 1=F _ 2\circ f, so that
\begin{gather*}
\alpha _ 1=\{F _ 1(a _ 1)\mid a _ 1\in A _ 1\}=\{F _ 2(f(a _ 1))\mid a _ 1\in A _ 1\}\\
=\{F _ 2(a _ 2)\mid a _ 2\in A _ 2\}=\alpha _ 2.
\end{gather*}

We shall use transfinite induction. Suppose A _ 0=\{a _ 1\in A _ 1\mid F _ 1(a _ 1)=F _ 2(f(a _ 1))\}. We show \downarrow< _ 1t\subseteq A _ 0\Rightarrow t\in A _ 0. Calculate F _ 1(t)=\{F _ 1(a _ 1)\mid a _ 1< _ 1t\}=\{F _ 2(f(a _ 1))\mid a _ 1< _ 1t\}. It is easy to check that this set is just \{F _ 2(a _ 2)\mid a _ 2< _ 2f(t)\}, which equals F _ 2(f(t)). Therefore F _ 1(t)=F _ 2(f(t)) and t\in A _ 0. By transfinite induction, A _ 0=A _ 1, indicating F _ 1=F _ 2\circ f.□

2. Ordinal Numbers We can now introduce ordinal numbers formally.

This definition may seem wierd, since we call a set which is the domain of a mapping a "number". However, in later chapters we can define a number as a specific set, and we will see an ordinal number can be such a set.

Theorem 4 shows that an ordinal number is a transitive set that can be equipped with a strict well-order by \in. The converse is also true: A set with a well-order under \in may not be transitive, such as \{\{\varnothing\},\{\{\varnothing\}\}\} (\varnothing\in\{\varnothing\} but it does not in this set). A transitive set may not be able to have a well-order under \in, such as \{\varnothing,\{\varnothing\},\{\{\varnothing\}\}\}, in which \varnothing\notin\{\{\varnothing\}\}. But if both of the two holds, the set is an ordinal number.

It can be checked that (\alpha,\leqslant _ \alpha) is a well-order. Then we consider an element x\in\alpha. If y< _ \alpha x then y\in x, and if y\in x, then by transitivity of \alpha, y\in \alpha, so y< _ \alpha x. This means y< _ \alpha x if and only if y\in x.

Thus, x consists of all y such that y< _ \alpha x, indicating x={\downarrow< _ \alpha x}.

Let F be the mapping from \alpha onto its ordinal number. We shall show F(x)=x for all x\in \alpha. Consider transfinite induction. Assume F(x)=x for all x\in {\downarrow< _ \alpha a}. Then F(a)=\{F(x)\mid x\in {\downarrow< _ \alpha a}\}=\{x\mid x\in{\downarrow< _ \alpha}a\}={\downarrow< _ \alpha a}=a. By transfinite induction, F is the identity mapping on \alpha.□
.

We have known some basic properties of ordinal numbers. For example, a well-ordered set is isomorphic to its ordinal number, and two well-ordered sets are isomorphic if and only if they have the same ordinal number. And there are more.
.

(Theorem 8)

Let F:A\to\alpha be the isomorphism onto the ordinal number. We have shown F(a)\notin F(a) for any a\in A. We can infer \alpha\notin\alpha. Otherwise \alpha=F(a)\in\alpha, contradicting F(a)\notin F(a).

Theorem 7 provides a sufficient condition for a set to be an ordinal number. Suppose \alpha is an ordinal number and \beta\in\alpha. We verify \beta is transitive, so we shall show \delta\in\beta under the assumption \delta\in \gamma\in\beta. Since \gamma\in\beta\in\alpha and \alpha is transtive, \gamma\in\alpha, so \delta\in\gamma\in\alpha implies \delta\in\alpha, indicating \delta< _ \alpha\gamma< _ \alpha\beta. Hence \delta< _ \alpha\beta and \delta\in\beta. On the other hand, \beta can inherit the well-order from \alpha. Therefore \beta, an arbitrary element of \alpha, is an ordinal number.

With these observations, we can state the "ordinal number version" of the Theorem 3, i.e., for ordinal numbers \alpha,\beta, exactly If any two of them holds, we will obtain \alpha\in\alpha, so at most one of them holds. Theorem 3 tells us that at least one of them holds. For example, if (\alpha,\leqslant _ \alpha) is isomorphic to a segment of \beta, say (\downarrow< _ \beta\gamma,\leqslant _ \beta^\circ). From the proof of Theorem 7, we know an initial segment below \gamma is \gamma itself. Together with {\leqslant _ \beta^\circ}={\leqslant _ \gamma}, we know (\alpha,\leqslant _ \alpha)\cong(\gamma,\leqslant _ \gamma), indicating \alpha=\gamma and therefore \alpha\in\beta.
.

(Theorem thm443)

With these properties, We now consider a set S of ordinal numbers. If S is nonempty, we assert that S has a least element. Suppose \alpha\in S. For any ordinal number \beta\in S, if it always holds that either \alpha\in \beta or \alpha=\beta, then \alpha is the least element of S. Otherwise, there are some elements of S that also belongs to \alpha. This subset S'=\alpha\cap S has a least element \gamma, and we show it is the least element of S. For \beta\in S, if \beta\in\gamma, then we infer from \alpha is transitive that \beta\in\alpha, indicating \beta is the smaller than \gamma in S', a contradiction. Therefore \gamma=\beta or \gamma\in\beta, and \gamma is the least element of S.

From this we know S is well-ordered under \in, so if additionally S is transtive, then S is an ordinal number. This is a useful result.

Specially, we take S=\alpha\cup\{\alpha\}. As can be seen, S is transtive, implying S is an ordinal number: Suppose \beta\in\alpha\cup\{\alpha\}, then either \beta\in\alpha or \beta=\alpha. If \beta\in\alpha, then by the transitivity of \alpha, we infer \beta\subseteq \alpha\subseteq\alpha\cup\{\alpha\}. If \beta=\alpha, then \beta=\alpha\subseteq\alpha\cup\{\alpha\}. In either case we have \beta\subseteq\alpha\cup\{\alpha\}, indicating \alpha\cup\{\alpha\} is transitive.

Similarly, we can show \bigcup S is an ordinal number when S is a set of ordinal numbers. Let \beta\in\bigcup S. There is an element \alpha of S such that \beta\in \alpha. Since \alpha is transitive, \beta\subseteq\alpha, so \beta\subseteq\bigcup S. Therefore \bigcup S is transitive and thus an ordinal number.

We summarize the above results.

We end this section with a paradox. Cantor developed the theory of ordinal numbers, but he formed a set using unrestricted formation principle of sets: For property P, \{x\mid P(x)\} is a set. This leads to several early appearing paradoxes such as the Burali-Forti paradox and Russel's paradox. The Burali-Forti paradox is the earliest one to be published.

If such a set exists, then it is transitive and well-ordered under \in, so it is an ordinal number. Hence it belongs to itself, but this is impossible for an ordinal number.□