Ordinal Numbers

The present unit is part of the following walks

Introduction

Please note that the text on this web page only gives a short summary of the Unit Ordinal Numbers. The full text including explanations, proofs and historical notes is available as a separate pdf-document at the end of this page.

The present unit is the third unit of the walk The Cardinality of Sets.

You will learn the meaning of the following terms:

The main results of this unit are:

Ordered Sets

We recall the following definitions from former units:

Definition. Let $A$ be a set.

(a) A relation $\leq$ on the set $A$ is called an order or, equivalently, a partial order on the set $A$ if it fulfills the following conditions:

(i) The relation $\leq$ is reflexive, that is, $x \leq x$ for all elements $x$ of the set $A$.

(ii) The relation $\leq$ is antisymmetric, that is, $x \leq y$ and $y \leq x$ imply $x = y$ for all elements $x$ and $y$ of the set $A$.

(iii) The relation $\leq$ is transitive, that is, $x \leq y$ and $y \leq z$ imply $x \leq z$ for all elements $x$, $y$ and $z$ of the set $A$.

(b) A set $A$ with a (partial) order $\leq$ is called an ordered set or, equivalently, a partially ordered set and is often denoted by $A = (A, \leq)$.

(c) A (partial) order $\leq$ on a set $A$ is called a total order if we have $x \leq y$ or $y \leq x$ for all elements $x$ and $y$ of the set $A$. A set $A$ with a total order $\leq$ is called a totally ordered set.

Definition. Let $A = (A, \leq_A)$ be an ordered set, let $B$ be a subset of the set $A$, and let $\leq_B$ be the order on the set $B$ such that

$$
x \leq_B y \mbox{ if and only if } x \leq_A y \mbox{ for all } x, y \in B.
$$

The order $\leq_B$ is called the order on the set $B$ induced by the order $\leq_A$.

Often we write $A = (A, \leq)$ and $B= (B, \leq)$ without explicitly distinguishing between the order $\leq_A$ on the set $A$ and the induced order $\leq_B$ on the set $B$.

Definition. Let $A = (A, \leq)$ be an ordered set, and let $B$ be a subset of the set $A$.

(a) An element $b$ of the set $B$ is called a minimal element or a minimum of the set $B$ if we have $x \geq b$ for all elements $x$ of the set $B$.

(b) An element $b$ of the set $B$ is called a maximal element or a maximum of the set $B$ if we have $x \leq b$ for all elements $x$ of the set $B$.

Definition. Let $A = (A, \leq_A)$ be an ordered set, and let $b$ be an element not contained in the set $A$. Set $B := A \mathbin{\dot{\cup}} \{ b \}$. We define an order $\leq_B$ on the set $B$ as follows:

For each two elements $x$ and $y$ of the set $A$, set $x \leq_B y$ if and only if $x \leq_A y$. For each element $x$ of the set $B$, set $x \leq_B b$.

The pair $(B, \leq_B)$ is called the one point extension of the pair $(A, \leq_A)$.

Definition. Let $(A, \leq_A)$ and $(B, \leq_B)$ be two ordered sets, and let $\alpha: A \rightarrow B$ be a function from the set $A$ into the set $B$.

(a) The function $\alpha: A \rightarrow B$ is called a homomorphism of ordered sets if we have

$$
\alpha(x) \leq_B \alpha(y) \mbox{ for all } x, y \in A \mbox{ such that all } x \leq_A y .
$$

A homomorphism of ordered sets is also called a homomorphism if no danger of confusion arises.

(b) A bijective homomorphism $\alpha: A \rightarrow B$ with the property that the inverse function $\alpha^{-1} : B \rightarrow A$ is also a homomorphism is called an isomorphism of ordered sets.

(c) The ordered sets $(A, \leq_A)$ and $(B, \leq_B)$ are called isomorphic if there exists an isomorphism $\alpha: A \rightarrow B$ from the set $A$ onto the set $B$. If the sets $A$ and $B$ are isomorphic, then we write $A \cong B$.

Definition. Let $(A, \leq)$ be an ordered set, and let $a$ be an element of the set $A$. Then the set

$$
A_a := \{x \in A \mid x < a \}
$$

is called the initial segment of the set $A$ with respect to the element $a$.

Definition. Let $A$ be a set. Then the set $A^+ := A \cup \{ A \}$ is called the successor of the set $A$.

Theorem. Let $n$ be a natural number.

(a) We have $n + 1 = \{0, 1, 2, \ldots, n\}$.

(b) For each natural number $n$, the set $n + 1 := n \cup \{ n \}$ is a natural number.

(c) We have $\big( \mathbb{N}_0 \big)_n := \{ x \in \mathbb{N}_0 \mid x < n \} = n$ (initial segment).

Definition of Ordinal Numbers

Definition. Let $(A, \leq)$ be a totally ordered set.

(a) The pair $(A, \leq)$ is called well-ordered if every non-empty subset $X$ of the set $A$ has a minimal element, that is, if for every subset $X$ of the set $A$ there exists an element $z$ of the set $X$ such that

$$
z \leq x \mbox{ for all } x \in X.
$$

(b) If the pair $(A, \leq)$ is well-ordered, then the order $\leq$ is called a well-ordering.

Definition. Let $A = (A, \leq)$ be a well-ordered set. The pair $(A, \leq)$ is called an ordinal number if all elements $a$ of the set $A$ fulfill the following condition:

$$
a = A_a := \{ x \in A \mid x < a \},
$$

that is, each element $a$ of the set $A$ equals the initial segment $A_a$ of the set $A$ with respect to the element $a$.

Theorem. Let $A = (A, \leq_A)$ be an ordinal number, and let $A^+ := A \mathbin{\dot{\cup}} \{ A \}$ be the successor set of the set $A$. Define the pair $(A^+, \leq_{A^+})$ to be the one point extension of the pair $(A, \leq_A)$.

Then the pair $(A^+, \leq_{A^+})$ is also an ordinal number.

Definition. A set $A$ is called a transitive set if every element of the set $A$ is at the same time a subset of the set $A$.

Theorem. The pair $(\mathbb{N}_0, \leq)$ with the standard order is an ordinal number.

Theorem. Let $n$ be a natural number, and let $\leq$ be the standard order on the natural numbers. Then the pair $(n, \leq)$ (induced order) is an ordinal number.

Isomorphisms between Ordinal Numbers

Theorem. Let $(A, \leq_A)$ and $(B, \leq_B)$ be two ordinal numbers which are isomorphic as ordered sets.

(a) We have $(A, \leq_A) = (B, \leq_B)$, that is, the ordinal numbers are identical.

(b) Let $\alpha : (A, \leq_A) \rightarrow (B, \leq_B)$ be an isomorphism from the ordered set $A$ onto the ordered set $B$. Then we have $\alpha(x) = x$ for all elements $x$ of the set $A$.

Theorem. Let $A = (A, \leq_A)$ and $B = (B, \leq_B)$ be two ordinal numbers. Then exactly one of the following cases occurs:

(i) We have $(A, \leq_A) = (B, \leq_B)$.

(ii) We have $A = b = B_b$ for some element $b$ of the set $B$, and the order $\leq_A$ is induced by the order $\leq_B$. In particular, we have $A \in B$ and $A \subset B$.

(iii) We have $B = a = A_a$ for some element $a$ of the set $A$, and the order $\leq_B$ is induced by the order $\leq_A$. In particular, we have $B \in A$ and $B \subset A$.

Theorem. Let $A = (A, \leq)$ and $B = (B, \leq)$ be two ordinal numbers. Then the following two conditions are equivalent:

(i) The set $A$ is an element of the set $B$, that is, $A \in B$.

(ii) The set $A$ is a proper subset of the set $B$, that is, $A \subset B$.

The Standard Order on the Ordinal Numbers

Definition. Let $A = (A, \leq)$ and $B = (B, \leq)$ be two ordinal numbers. We define the order

$$
A \leq B \mbox{ if and only if } A \subseteq B.
$$

The so defined order $\leq$ is called the standard order on the ordinal numbers.

Theorem. Let ${\cal A}$ be a set of ordinal numbers. Then the standard order on the ordinal numbers is a total order on the set ${\cal A}$.

Theorem. Let $A$ be an ordinal number. Then exactly one of the following possibilities occurs:

(i) There is a natural number $n$ such that $A = n$.

(ii) We have $\mathbb{N}_0 \leq A$.

Theorem. Let ${\cal A}$ be a set of ordinal numbers. Then the pair $( {\cal A}, \leq)$ is well-ordered where $\leq$ denotes the standard order on the ordinal numbers.

The Theorem of Burali-Forti

Theorem. Let ${\cal A}$ be a set of ordinal numbers, and let

$$
S := \bigcup_{X \in {\cal A} } X.
$$

(a) The set $S$ is an ordinal number.

(b) The ordinal number $S$ is the only ordinal number with the following properties:

(i) We have $A \leq S$ for all ordinal numbers $A$ of the set ${\cal A}$.

(ii) If $T$ is an ordinal number such that $A \leq T$ for all ordinal numbers $A$ of the set ${\cal A}$, then we have $S \leq T$

Note that the ordinal number $S$ is not necessarily contained in the set ${\cal A}$.

Theorem. (Burali-Forti) The ordinal numbers do not form a set. In other words, there is not set ${\cal A}$ with the property that

$$
A \in {\cal A} \mbox{ if and only if } A \mbox{ is an ordinal number}.
$$

Well-Ordered Sets and Ordinal Numbers

Theorem. Let $A = (A, \leq_A)$ be a well-ordered set. Then there exists exactly one ordinal number $B = (B, \leq)$ isomorphic to the set $A$.

Notes and References

A list of textbooks about set theory is contained in Unit [Literature about Set Theory].

Do you want to learn more? In Unit Finite Sets and their Cardinalities we have defined the cardinalities of finite sets. In Unit Well-Ordered Sets we have studied the process of counting which led us to the well-ordered sets. In this unit we introduced the counting of well-ordered sets which led us to ordinal numbers. However, ordinal numbers are too fine to be cardinal numbers. In Unit [Cardinal Numbers – in preparation] you will learn how ordinal numbers can be used to define the cardinality of a set.

Download

Ordinal Numbers

math_garden_card_ordinal_numbersDownload

The pdf document is the full text including the proofs.

Current Version: 1.0.0 from January 2021