* Order Structures (Cont.)

Contents
Contents
 1.  Axiom of Choice
   1.1.  Equivalent Variants
   1.2.  AC and Orders
 2.  Regularity Axiom

1. Axiom of Choice

The axiom of choice is obviously true, the well-ordering principle obviously false, and who can tell about Zorn's lemma?---Jerry Bona

This is the most special axiom in ZFC set theory. After all, the "C" in ZFC stands for choice. Only this axiom is explicitly mentioned when it is used each time, though it is now standard and used without reservation by most mathematicians.

In many cases, we do not need the AC even if we are choosing. For example, for a function f, we have \exists y\, (f(x)=y). Then we can pick this y up and use it for proofs. Similarly, if we choose finitely many elements, then AC is not needed. We just choose them successively. Another example is that we can choose by some available rules, such as the choice function that maps a nonempty subset of \mathbb N to its least element.

However if there are infinitely many choices to be made but no distinguishing property available, then AC is indispensable. Finite choices is doable for us, not so with infinite choices, but AC ensures us of the existence of a set produced from infinitely many choices.

We do not discuss the axiom of choice, or AC, systematically until now because we do need some theory of orders. We will show AC is equivalent to the well-ordering theorem, and also equivalent to Zorn's lemma. These two are the most important variants. Before that, let us take a look at some variants of AC that have a choice function explicitly.

1.1. Equivalent Variants There are actually a lot of equivalent variants of AC. Here are some of them.

We now prove this theorem.

\mathit{1}\Rightarrow\mathit{2}. Actually this has been proved in the proof of Theorem 7.

\mathit{2}\Rightarrow\mathit{1}. For a relation \mathcal R with domain X and range Y, consider the choice function g defined on the nonempty subsets of Y. Suppose B is such a subset, then g(B)\in B. For any x\in X, the set B _ x=\{y\mid x\mathcal Ry\} is a nonempty subset of the range Y. Therefore define a mapping by x\mapsto g(B _ x)\in B _ x for any x\in X. This is a mapping f such that f(x)\in B _ x, indicating x\mathcal R(f(x)). Hence f\subseteq\mathcal R.

\mathit{1}\Rightarrow\mathit{3}. Define the relation \mathcal R by i\mathcal Rx if and only if i\in I and x\in A _ i. Then \mathcal R is a set since it is contained in I\times\bigcup _ {i\in I} A(i). By 1 we have a mapping f with domain I such that f\subseteq\mathcal R. For any i\in I, i\mathcal Rf(i), indicating f(i)\in A _ i.

\mathit{3}\Rightarrow\mathit{1}. For a relation \mathcal R with domain X, the set B _ x=\{y\mid x\mathcal Ry \} is a nonempty subset of the range. The set X can be the index set, so there is a mapping f with domain X such that f(x)\in B _ x, indicating x\mathcal Rf(x). Hence f\subseteq\mathcal R.

\mathit{3}\Rightarrow\mathit{4}. This is easy: The set \mathcal A can be the index set for itself.

\mathit{4}\Rightarrow\mathit{3}. Let \{A _ i\} _ {i\in I} be a set of sets. For each A _ i, define B _ i=\{i\}\times A _ i=\{(i,a)\mid a\in A _ i\}. This is nonempty, and if i\neq j, then B _ i\cap B _ j=\varnothing. Then there is a set C such that C contains exactly one element from each B _ i. Suppose C\cap B _ i=(i,a _ i) where a _ i\in A _ i. Then the mapping i\mapsto a _ i is the one we want.

\mathit{1}\Rightarrow\mathit{5}. Define a relation on \bigcup \mathcal A\times \mathcal A by x\mathcal RA if and only if x\in A. The domain is all of \bigcup \mathcal A. Then there is a mapping f:\bigcup \mathcal A\to\mathcal A such that f\subseteq\mathcal R. Therefore x\mathcal Rf(x), i.e., x\in f(x).

\mathit{5}\Rightarrow\mathit{3}. This is not obvious. Let \mathcal A=\{A _ i\} _ {i\in I} and consider \mathcal B=\{\{A, (a,A)\}\mid a\in A\in\mathcal A\}. Then there is a mapping f with domain \bigcup \{\{A, (a,A)\}\mid a\in A\in\mathcal A\}=\mathcal A \cup\{(a,A)\mid a\in A\in\mathcal A\}, such that A\in f(A)\in\mathcal B for any A in the domain. Since \mathcal A is contained in the domain, we consider the value of f(A _ i), which satisfies A _ i\in f(A _ i)\in \mathcal B, i.e., f(A _ i) is an element of \mathcal B containing A _ i. We infer f(a) must have the form \{A _ i,(a _ i,A _ i)\} where a _ i\in A _ i. We then obtain a mapping A _ i\mapsto a _ i\in A _ i.

The equivalence of these statements are proved.□

1.2. AC and Orders

We begin with a theorem which does not require AC.

Let \beta be an ordinal number such that there is an injection f from \beta into A. Denote B=f(\beta)\subseteq A. For any x,y\in\beta, We define f(x)\leqslant _ B f(y) if and only if x\leqslant _ \beta y, i.e., x\in y or x=y. Then f is an isomorphism, and (\beta,\leqslant _ \beta)\cong(B,\leqslant _ B). They have the same ordinal number, \beta.

We collect all such ordinal numbers \beta and try to form a set \alpha. It suffices to show all (B,\leqslant _ B), where B\subseteq A and \leqslant _ B is a well-order, can form a set W. This can be seen easily. Since B\subseteq A, B\in\mathcal P(A), so (B,\leqslant _ B)\in\mathcal P(A)\times \mathcal P (A\times A). Thus W is a set, and by replacement axiom, we can see \alpha is also a set.

As \alpha is a set, there exists an ordinal number not belonging to \alpha (Theorem thm444). Suppose \gamma\in\beta\in\alpha. By transitivity of \beta, \gamma\subseteq\beta\preccurlyeq A, so \gamma\preccurlyeq A and \gamma\in\alpha, implying \alpha is transitive. By Theorem thm443 \alpha is an ordinal number. We can show \alpha is the "Hartogs number". Since \alpha\notin\alpha, there is no injection from \alpha into A, and if \beta\in\alpha, by construction \beta\preccurlyeq A.□
.

We use this theorem, together with AC, to prove the following sort of amazing theorem, well-ordering theorem, which is also known as Zermelo's theorem.

Clearly the set (\mathbb R,\leqslant) of real numbers is not a well-order structure, but the well-ordering theorem claims that there exists a well-order on \mathbb R. So what is the well-order on \mathbb R? Unfortunately, the following proof can hardly provide useful information on the answer.

Let G be the choice function for the nonempty subsets of A and \alpha be the Hartogs number of A. We will define a mapping F on \alpha by transfinite recursion, as we did in the proof of Theorem thm431. Specifically, for any \beta\in\alpha, we define

F(\beta)=\begin{cases}
G(A\setminus F(\downarrow<\beta)),& A\setminus F(\downarrow<\beta)\neq\varnothing,\\
u,& A\setminus F(\downarrow<\beta)=\varnothing.
\end{cases}

Here u\notin A. If F(\gamma)=u for \gamma\in \alpha, then \gamma\in\beta\in\alpha implies F(\beta)=u. Suppose \gamma\in\beta\in\alpha and F(\beta)\neq u. Then F(\gamma)\neq u, and since F(\beta) is chosen from A\setminus F(\downarrow<\beta), F(\beta)\neq F(\gamma)\in F(\downarrow<\beta).

We infer u is in the range of F. Otherwise F is injective and then \alpha\preccurlyeq A, a contradiction. Suppose \delta\in\alpha is the least element such that F(\delta)=u. Then F(\downarrow<\delta)=A. It is not difficult to see that the well-order on \downarrow<\delta induces a well-order \leqslant _ A on A, so that F| _ {\downarrow<\delta} is an isomorphism from (\downarrow<\delta,\leqslant _ \delta) onto (A,\leqslant _ A).

The well-ordering theorem is proved. Since \downarrow<\delta=\delta is an ordinal number, the numeration theorem is also proved.□
.

We can now prove the important Zorn's lemma. It is a powerful tool of great versatility and broad applicability in mathematics.

By assumption P is nonempty, otherwise the empty chain has no upper bound in P.

By well-ordering theorem, there is a well-order \leqslant on P. To avoid confusion, the original partial order of P is denoted by \preccurlyeq. Suppose \alpha is the ordinal number of P and (P,\leqslant)\cong (\alpha,\leqslant _ \alpha). The partial order \preccurlyeq also induces a well-order \preccurlyeq _ \alpha on \alpha, such that any \preccurlyeq _ \alpha--chain in \alpha has a \preccurlyeq _ \alpha--upper bound in \alpha. Below \preccurlyeq _ \alpha is simply denoted by \preccurlyeq, and similarly for \prec _ \alpha.

We then use transfinite recursion to construct a \prec--chain. For any \beta\in\alpha, we define by transfinite recursion a mapping by

F(\beta)=\begin{cases}
1,& \forall \gamma\in \{\delta\in{\downarrow<\beta}\mid F(\delta)=1\}\, (\gamma\prec\beta),\\
0,& \exists \gamma\in\cdots\, (\gamma\nprec\beta).
\end{cases}

The condition means that we add \beta into our list if it is a \prec--upper bound of the list. Therefore we obtain a set C=\{\beta\in\alpha\mid F(\beta)=1\} from F. As can be seen, C is a \prec--chain in which {\prec}\Leftrightarrow{\in}, so it has a \preccurlyeq--upper bound \mu in \alpha.

We show that \mu is \preccurlyeq--maximal, i.e., \mu\preccurlyeq\lambda implies \mu=\lambda. If \mu\prec\lambda, then F(\lambda)=1 and \lambda\in C. Therefore \lambda\preccurlyeq\mu, a contradiction.□
.

In Chapter 3, we did not define the cardinal number of an infinite set, but assumed it is well--defined and has the property that two sets have the same cardinal number if and only if they are equinumerous. In addition, Theorem thm331 is not proved completely.

It is time to give a formal definition.

We check the validity of this definition. Let \alpha be the Hartogs number of A and consider \{\beta\in\alpha\mid \beta\sim A\}. This is a set of ordinal numbers, which is nonempty by numeration theorem. By Theorem thm443 it has a least element. Thus the cardinal number is well--defined. It is also easy to see that for any two sets A and B, A\sim B if and only if |A|=|B|.

With Zorn's lemma, we prove Theorem thm331 (4).

Consider the injective mappings from a subset of A into B. Let

\mathcal F=\{f:X\hookrightarrow Y\mid (X\subseteq A)\wedge(Y\subseteq B)\wedge(f(X)=Y)\}.

Here we have used the notation \hookrightarrow to indicate f is injective. On this set, define a partial order \leqslant _ {\mathcal F}: f _ 1\leqslant _ {\mathcal F}f _ 2 if and only if X _ 1\subseteq X _ 2, Y _ 1\subseteq Y _ 2 and f _ 2| _ {X _ 1}= f _ 1, i.e., f _ 2 is an extension of f _ 1.

Suppose \{f _ i\} _ {i\in I} is a chain of \mathcal F. Define X'=\bigcup X _ i, Y'=\bigcup Y _ i and f=\bigcup f _ i. It is easy to check f is a mapping: Suppose (x,y _ 1)\in f and (x,y _ 2)\in f. There are two mappings f _ i,f _ j\in\{f _ i\} _ {i\in I} such that y _ 1=f _ i(x) and y _ 2=f _ j(x). Since f _ i\leqslant _ {\mathcal F}f _ j or f _ j\leqslant _ {\mathcal F}f _ i, (x,y _ 1) and (x,y _ 2) are in the same f _ i or f _ j, so y _ 1=y _ 2. Similarly, suppose (x _ 1,y)\in f and (x _ 2,y)\in f. Then x _ 1=x _ 2, so f is a bijection from X' to Y'. We also have X'\subseteq X and Y'\subseteq Y. Hence f\in\mathcal F is a \leqslant _ {\mathcal F}--upper bound of the chain.

Given that the premises of Zorn's lemma hold, \mathcal F has a maximal element f _ 0:X _ 0\to Y _ 0, a bijection from X _ 0\subseteq A onto Y _ 0\subseteq B. If neither X _ 0\neq A nor Y _ 0\neq B, then A\setminus X _ 0 and B\setminus Y _ 0 are both nonempty, so we can extend f _ 0 by mapping an element of A\setminus X _ 0 to an element of B\setminus Y _ 0 and the extension is in \mathcal F, implying f _ 0 is not a maximal element. Therefore X _ 0=A (in which case A\preccurlyeq B) or Y _ 0=B (in which case B\preccurlyeq A).□

We have proved that AC \Rightarrow well-ordering theorem \Rightarrow Zorn's lemma \Rightarrow cardinal comparability.

The well-ordering theorem can be proved easily from cardinal comparability. Suppose A is a set. By Hartogs' theorem and cardinal comparability, there is an ordinal number \alpha such that A\preccurlyeq \alpha. The well-order on \alpha induces a well-order on A.

Finally we prove AC from Zorn's lemma. The proof is quite similar to that of Theorem 7, so we sketch the main idea. Suppose \{A _ i\} _ {i\in I} is a family of nonempty sets: for any i\in I, A _ i\neq\varnothing. We consider the set of "partial choice functions". Let

\mathcal F=\{(J,f)\mid (J\subseteq I)\wedge(f:J\to\bigcup A _ i)\wedge((\forall j\in J)\, f(j)\in A _ j)\}.

On this set, define a partial order \leqslant _ {\mathcal F}: (J _ 1,f _ 1)\leqslant _ {\mathcal F}(J _ 2,f _ 2) if and only if J _ 1\subseteq J _ 2 and f _ 2| _ {J _ 1}= f _ 1, i.e., f _ 2 is an extension of f _ 1.

Suppose \{(J _ k,f _ k)\} _ {k\in K} is a chain of \mathcal F. Define J'=\bigcup J _ k and f'=\bigcup f _ k. Then, as in the preceding proof, J'\subseteq I and f' is a mapping from J' to \bigcup A _ i. Moreover, f'(j)\in A _ j for any j\in J'. Hence (J',f')\in\mathcal F and it is a \leqslant _ \mathcal F--upper bound of the chain.

Apply Zorn's lemma and obtain a maximal element (J _ 0,f _ 0). As in the preceding proof, it is not difficult to show J _ 0=I so that f _ 0 is the choice function we want.□
.

Finally we discuss some simple properties of cardinal numbers. Let \alpha be the cardinal number of a set A: \alpha=|A|. Then \alpha\sim A. As a set, \alpha has its own cardinal number, and we can see it is \alpha itself, i.e., |\alpha|=\alpha.

We previously defined the order of cardinal numbers by the rule |A|\leqslant|B| if and only if A\preccurlyeq B. We can easily verify that this is the same as the \in order of ordinal numbers. Suppose A,B are two sets with cardinal numbers \alpha,\beta respectively. Then (\alpha\in\beta)\vee(\alpha=\beta) \Rightarrow\alpha\subseteq\beta\Rightarrow \alpha\preccurlyeq\beta\Rightarrow\alpha\leqslant\beta. On the other hand, \beta\in\alpha\Rightarrow\beta\subsetneq\alpha\Rightarrow(\beta\preccurlyeq\alpha)\wedge(\beta\not\sim\alpha), implied by the fact that a cardinal number is not equinumerous to any smaller ordinal number. Hence \beta<\alpha. We conclude that (\alpha\in\beta)\vee(\alpha=\beta) \Leftrightarrow\alpha\leqslant\beta.

Like ordinal numbers, a set of cardinal numbers also has a least element.

For the set \mathbb N of natural numbers, the cardinal number is \aleph _ 0. Suppose the Hartogs number of \mathbb N is \alpha. Then \alpha\not\preccurlyeq\mathbb N, and for any set A, |A|\in\alpha\Rightarrow A\preccurlyeq \mathbb N, i.e., A is a countable set. Therefore \alpha is the least uncountable ordinal and the least ordinal after \aleph _ 0. Usually, it is denoted by \aleph _ 1. Similarly, we have \aleph _ 2,\aleph _ 3,\dots

2. Regularity Axiom This section introduces our 9\textsuperscript{th} axiom of set theory, the regularity axiom.

9. Regularity Axiom: Every nonempty set A has a member x such that x\cap A=\varnothing.

This axiom seems unmotivated. In fact, regularity shines when we discuss the rank of a set, a concept that will not be discussed in detail here.

The idea of the rank is to formalize the intuitive idea that sets are built iteratively in layers. All sets are organized into a cumulative hierarchy of levels. Each layer is a set V _ \alpha for an ordinal number \alpha.

V _ {\varnothing}\subseteq\dots\subseteq V _ \alpha\subseteq\dots\subseteq V _ \beta\subseteq\dots

If a set has its all elements in V _ \alpha, then this set is in the "higher level" V _ \beta for any \alpha\in\beta. There are more and more sets in V _ \alpha as \alpha gets larger. We say a set A is grounded if the elements of A all belong to V _ \alpha for some ordinal number \alpha, i.e., A\subseteq V _ \alpha.

It turns out that if we want every set is grounded, then regularity is needed, and actually is an equivalent characterization.

We do not touch more detail of ranks here.

If x\in x, we might think the hierarchy of x continues nesting down to infinity. Now consider the set \{x\}, which is indeed a set when x is a set. Then it should has a member y such that y\cap\{x\}=\varnothing. Since \{x\} has only one element x, y=x and x\cap\{x\}=\varnothing. On the other hand, x\in x and x\in\{x\} imply x\in x\cap\{x\}. The contradiction shows x\notin x.

If x,y are two sets such that x\in y and y\in x. We consider \{x,y\}. Then x\cap\{x,y\}=\varnothing or y\cap\{x,y\}=\varnothing. If x\cap\{x,y\}=\varnothing, then it contradicts y\in x\cap\{x,y\}. The other case is similar.

If x _ 0,x _ 1,\dots is a sequence such that x _ {n+1}\in x _ {n} for all n\in\mathbb N. Consider the set A=\{x _ 0,x _ 1,\dots\}, which is the range of mapping x defined on \mathbb N. For any n\in\mathbb N, x _ n\in A, so we have x _ {n+1}\in x _ n\cap A. On the other hand, by regularity there is an element x _ n of A such that x _ n\cap A=\varnothing. The contradiction shows the desired sequence does not exist.□
.

The axioms we have currently are:

Extensionality axiom
Empty set axiom
Pairing axiom
Union axiom
Power set axiom
Subset axioms
Replacement axioms
Choice axiom
Regularity axiom
(Infinity axiom)

Only one axiom, infinity axiom, has not been introduced yet. Actually we have used this axiom heavily previously, such as all the statement involving \mathbb N, a set whose existence relies on the infinity axiom.