Ordinal Numbers
- Introduction
- Ordered Sets
- Definition of Ordinal Numbers
- Isomorphisms between Ordinal Numbers
- The Standard Order on the Ordinal Numbers
- The Theorem of Burali-Forti
- Well-Ordered Sets and Ordinal Numbers
- Notes and References
- Download
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:
- The set $\mathbb{N}_0$ of the natural numbers with its standard order is an ordinal number (see Theorem [#card-th-nz-ordinal-number]).
- Every natural number is an ordinal number (see Theorem [#card-th-natural-number-ordinal-number]).
- If $\alpha : A \rightarrow B$ is an isomorphism from an ordinal number $A = (A, \leq_A)$ onto an ordinal number $B = (B, \leq_B)$, then we have $(A, \leq_A) = (B, \leq_B)$ and $\alpha = \mbox{id}$ (see Theorem [#card-th-ordinal-numbers-isomorphic-identical]).
- Two ordinal numbers are either identical or one ordinal number is an initial segment of the other one (see Theorem [#card-th-ordinal-number-classification]).
- Let $A = (A, \leq_A)$ and $B = (B, \leq_B)$ be two ordinal numbers. Then we have
$$
A \in B \mbox{ if and only if } A \subset B.
$$
(see Theorem [#card-th-ordinal-number-element-is-subset]). - The standard order on a set of ordinal numbers is a total order (see Theorem [#card-th-total-order-ordinal-numbers]).
- Let $A = (A, \leq_A)$ be an ordinal number. Then the ordinal number $A$ is either a natural number or we have $\mathbb{N}_0 \leq A$ (see Theorem [#card-th-finite-ordinal-numbers]).
- A set of ordinal numbers is well-ordered with respect to its standard order (see Theorem [#card-th-ordinal-numbers-well-ordered]).
- The union of ordinal numbers is again an ordinal number (see Theorem [#card-th-ordinal-number-union]).
- Theorem of Burali-Forti: The ordinal numbers do not form a set (see Theorem [#card-th-burali-forti]).
- 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$ (see Theorem [#card-th-well-ordered-isomorphic-ordinal-number]).
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
The pdf document is the full text including the proofs.
Current Version: 1.0.0 from January 2021