Ordinals and Well-Ordered Sets

This post was machine-translated from the Korean original by Marvin (via Kimi). It may contain errors or awkward phrasing — the Korean original is the source of truth.

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 satisfies the following axioms:

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

Mathematical induction, as we commonly use it, is in fact 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—operations on natural numbers are defined at this point using the following recursion theorem.

Theorem 1 (The recursion theorem) Let a set $A$ be given. For an element $a\in A$ 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:

$f_0=a$,
$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

For any $m$ and $n$, we show that an $m$-step computation and an $n$-step computation are compatible, and hence that $f$ is a function.
We then show that $\pr_1F=\mathbb{N}$ and $\pr_2F\subseteq A$, which requires induction.
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.
Finally, for uniqueness, assuming some $h:\mathbb{N}\rightarrow A$ satisfies the conditions of the theorem, we use induction to show that $f_n=h_n$ 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, of 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 above Peano axioms, which serves as 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.\]

Next, to define $1$, we must create a singleton set. However, the only set we currently have is $\emptyset$, so there is only one reasonable way to define $1$:

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

We then define $2$ by

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

and define $3=\{0,1,2\}$ in the same manner. In this model, one easily verifies that $S$ is given by the function

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

By definition, $m<n$ is equivalent to $m\in n$. Repeating this process yields 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 any set we have seen before.¹ 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 even obtain $\omega\cdot\omega=\omega^2$; repeating 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 the resulting set, we can repeat the same process again.

Well-Ordered Sets

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

Definition 2 A total order $R$ 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 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 matter 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)$.

It remains only to show that $A\setminus S$ is exactly $[a,\infty)$, for then $S=(-\infty, a)$ and the proof is complete. Suppose, for contradiction, 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$, contradicting the assumption that $a$ is the least element of $A\setminus S$. Therefore every $x\in [a,\infty)$ belongs to $A\setminus S$, and hence $A\setminus S=[a,\infty)$.

Remark The above proposition does not say that the set $(-\infty, a]$ cannot be a segment of $A$. Rather, it 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 preceding proposition does not mean that this set is not a segment, but rather that it 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, a segment of the form $(-\infty, a)$ never contains $a$, so no segment of $A$ of this form can equal $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.

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, whereas this set has the maximal element $\omega$. ↩

Share on

Twitter Facebook LinkedIn

K

Introduction

Natural Numbers and Ordinals

Well-Ordered Sets

Share on

댓글남기기