K

Grad. student in mathematics

Introduction

To understand what ordinals are, it is helpful to examine the following Peano axioms that define the natural numbers.

Peano Axioms. The set of natural numbers \(\mathbb{N}\) together with a successor function \(S\) defined on it are objects satisfying the following axioms:

  1. \(0\) is a natural number.
  2. For any natural number \(n\), \(S(n)\) is also a natural number.
  3. \(S\) is injective.
  4. There is no natural number \(n\) such that \(S(n)=0\).
  5. If another set \(K\) containing \(0\) is closed under \(S\), then \(K\) contains \(\mathbb{N}\).

The mathematical induction we commonly use is actually a proposition derived from the above axioms. In standard set theory textbooks, such as [HJJ] which we used when defining the ZFC axioms and ordered pairs, one would at this point define operations on natural numbers using the following recursion theorem.

Theorem 1 (The recursion theorem) Let a set \(A\) be given. For an element \(a\in A\) of this set and an arbitrary function \(g:A\times \mathbb{N}\rightarrow A\), there exists a unique infinite sequence \(f:\mathbb{N}\rightarrow A\) satisfying the following conditions:

  1. \(f_0=a\),
  2. \(f_{n+1}=g(f_n,n)\) for all \(n\in\mathbb{N}\).
Proof

We only sketch the main idea of the proof. Define an \(m\)-step computation as a finite sequence \(t:\left\{1,2,\cdots,m\right\}\rightarrow A\) satisfying the conditions

\[t_0=a,\quad t_{k+1}=g(t_k,k)\text{ for all }k< m.\]

Clearly \(t\) is a subset of \(\mathbb{N}\times A\). Now for the set

\[\mathfrak{F}=\left\{t\in\mathcal{P}(A)\mid t\text{ is an }m\text{-step computation for some natural number }m\right\}\]

let \(F=\bigcup\mathfrak{F}\). Then

  1. For any \(m\) and \(n\), one can show that an \(m\)-step computation and an \(n\)-step computation are compatible, and through this, show that \(f\) is a function.
  2. Then show that \(\pr_1F=\mathbb{N}\) and \(\pr_2F\subseteq A\). This step requires using induction.
  3. By step 2, we know that \(f=(F,\mathbb{N},A)\) is a function, so we only need to show that this function satisfies the given two conditions.
  4. Finally, for uniqueness, assume some \(h:\mathbb{N}\rightarrow A\) satisfies the conditions of the theorem, then use induction to show that \(f_n=h_n\) holds for all \(n\).

Within the axiom system we have been working with, there is no way to prove the existence of the set of natural numbers, or more generally, infinite sets. Therefore, we need to introduce the following axiom.

The Axiom of infinity There exists a set \(I\) that contains \(0\) and is closed under the successor function.

Natural Numbers and Ordinals

Von Neumann presented a specific model of the natural numbers \(\mathbb{N}\) satisfying the Peo axioms above, which provides good motivation for defining ordinals, so we introduce it first. Von Neumann’s idea is to define a natural number \(n\) as a set with $n$ elements. Then \(0\) is uniquely determined:

\[0=\emptyset.\]

After that, to define \(1\), we need to create a singleton set. However, the only set we have at this point is \(\emptyset\), so there is only one reasonable way to define \(1\):

\[1=\{\emptyset\}.\]

Then we define \(2\) by the equation

\[2=\{0,1\}=\big\{\emptyset,\{\emptyset\}\big\}\]

and define \(3=\{0,1,2\}\) in the same manner. In this model, one can easily verify that \(S\) is defined by the function

\[S(x)=x\cup\{x\}.\]

By definition, \(m<n\) is equivalent to \(m\in n\). For now, we repeat this process to obtain the set of natural numbers. When treating the set of natural numbers as ordinals in this way, we write it as \(\omega\).

However, the above process does not end once we obtain \(\omega\). For instance,

\[S(\omega)=\{0,1,2,\ldots,\omega\}\]

is different from all previous sets.1 Let us call this \(\omega+1\). By repeatedly applying \(S\) in this manner, we obtain

\[S(\omega)=\omega+1,\qquad S(\omega+1)=\omega+2, \ldots\]

and continuing this repetition, we get

\[\omega+1,\omega+2, \ldots, \omega+\omega:=\omega\cdot 2.\]

Repeating this again, we obtain \(\omega\cdot 2, \omega\cdot 2+1, \ldots, \omega\cdot 3, \ldots,\) and repeating once more, we finally obtain \(\omega\cdot\omega=\omega^2\), and repeating this yet again gives \(\omega^3, \ldots, \omega^\omega\), then \(\omega^{\omega^{\omega}}, \ldots\). Of course, when this process finishes and we assign a new symbol to this set, we can repeat the same thing again.

Well-Ordered Sets

The above discussion is intuitive but not sufficiently rigorous to be accepted as a definition.

Definition 2 A totally ordered set \(R\) defined on a set \(A\) is a well-ordering if every non-empty subset \(X\) of \(A\) has a least element.

Example 3 \(\mathbb{N}\) is a well-ordered set, but \(\mathbb{R}\) is not.

Having a least element for the entire set is not a sufficient condition for a set to be well-ordered. For example, \(\mathbb{R}^{\geq 0}\) has the least element \(0\), but its subset \(\mathbb{R}^{>0}\) has no least element. Also, \(\mathbb{Z}\) is not well-ordered, so the size of the set does not affect this either.

Definition 4 Let \((A,\leq)\) be an ordered set. A subset \(S\) of \(A\) is called an initial segment of \(A\) if it satisfies the following condition:

If \(x\in S\), \(y\in A\), and \(y\leq x\), then \(y\in S\).

In most cases, an initial segment is simply called a segment for brevity.

Proposition 5 Let \((A,\leq)\) be a well-ordered set. Every segment of \(A\) other than \(A\) itself is of the form \((-\infty, a)\) for some \(a\in A\).

Proof

Let \(S\neq A\) be an arbitrary segment. Since \(A\) is well-ordered, \(A\setminus S\) also has a least element. Call it \(a\). By definition, every element of \(A\setminus S\) is greater than or equal to \(a\), so \(A\setminus S\) is a subset of \([a,\infty)\).

Now we only need to show that \(A\setminus S\) is exactly \([a,\infty)\), and then \(S=(-\infty, a)\), completing the proof. Assume to the contrary that some \(x\in [a,\infty)\) is not an element of \(A\setminus S\). That is, \(x\) satisfies both \(a\leq x\) and \(x\in S\). But since \(S\) is a segment, \(a\leq x\) implies \(a\in S\), which contradicts the assumption that \(a\) is the least element of \(A\setminus S\), so \(x\not\in S\). Therefore, \(A\setminus S\) is exactly \([a,\infty)\), and the proof is complete.

Remark The above proposition does not say that the set \((-\infty, a]\) cannot be a segment of \(A\). This theorem means that if \((-\infty, a]\) is a segment of \(A\), then this set can also be written in the form \((-\infty, a')\) for some \(a'\in A\).

For example, in \(\mathbb{N}\), the set \((-\infty, 3]\) is by definition \(\{0,1,2,3\}\). The previous proposition does not mean this set is not a segment, but rather that this set can also be written as \((-\infty, 4)\).

Of course, this need not hold for general ordered sets. For instance, \(\mathbb{R}\) is not well-ordered, and its segment \((-\infty, a]\) cannot be written in the form \((-\infty, a')\).

In any case, the set \((-\infty, a)\) is always a segment of an ordered set. This set is called the segment with endpoint \(a\), denoted by \(S_a\). For any ordered set \(A\), the following holds:

\[\bigcup_{a\in A}S_a=\begin{cases}A&\text{if there is no greatest element of $A$}\\ A\setminus\{b\}&\text{if }b\text{ is the greatest element of $A$}\end{cases}.\]

However, in any case, a segment of the form \((-\infty, a)\) does not contain \(a\), so a segment of \(A\) with this form cannot be \(A\) itself.

References

[HJJ] K. Hrbacek, T.J. Jeck, and T. Jech. Introduction to Set Theory. Lecture Notes in Pure and Applied Mathematics. M. Dekker, 1978.
[Bou] N. Bourbaki, Theory of Sets. Elements of mathematics. Springer Berlin-Heidelberg, 2013.

  1. Of course, this set has the same cardinality as \(\mathbb{N}\) since it is obtained by adding just one element to \(\mathbb{N}\). However, as an ordered set, the set of natural numbers has no maximal element, while this set has the maximal element \(\omega\). ↩

댓글남기기