 # Well-Ordered Sets

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 Well-Ordered Sets. 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 second 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 will recall some 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, \leq_A)$ and $(B, \leq_B)$ be two ordered sets, and let $\alpha : A \rightarrow B$ be a mapping from the set $A$ into the set $B$.

(a) The mapping $\alpha : A \rightarrow B$ is called a homomorphism of the set $A$ into the set $B$ if $x \leq_A y$ implies $\alpha(x) \leq_B \alpha(y)$ for all elements $x$ and $y$ of the set $A$.

(b) The mapping $\alpha : A \rightarrow B$ is called an isomorphism of the set $A$ onto the set $B$ if and only if the mapping $\alpha: A \rightarrow B$ is bijective and if we have

$$\alpha(x) \leq_B \alpha(y) \mbox{ if and only if } x \leq_A y \mbox{ for all } x, y \in A.$$

(c) If $\alpha : A \rightarrow B$ is an isomorphism from the set $A$ onto the set $B$, then the sets $A$ and $B$ are called isomorphic. In this case we write $A \cong B$.

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

(a) 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$.

(b) The set

$$T_a := \{x \in A \mid x \geq a \}$$

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

Definition. Let $A = (A, \leq_A)$ be a totally 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)$.

## Successors and Predecessors

We will introduce successors and predecessors of an element:

Definition. Let $A = (A, \leq)$ be a totally ordered set, and let $a$ and $b$ be two elements of the set $A$.

(a) An element $c$ of the set $A$ is called an element between the elements $a$ and $b$ if we have

$$a < c < b \mbox{ or } b < c < a.$$

(b) The element $b$ is called the successor of the element $a$ if we have $a < b$ and if there is no element of the set $A$ between the elements $a$ and $b$.

(c) The element $a$ is called the predecessor of the element $b$ if we have $a < b$ and if there is no element of the set $A$ between the elements $a$ and $b$, that is, if the element $b$ is the successor of the element $a$.

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

(a) Each element of the set $A$ has at most one successor.

(b) Each element of the set $A$ has at most one predecessor.

## Successors of Sets

Successors of sets are a main tool in the investigation of well-ordered sets. Informally, if one has computed the cardinality of a set $A$, then one can add one element, namely the successor of the set $A$.

Definition. Let $A = (A, \leq)$ be a totally ordered set, and let $B$ be a subset of the set $A$. An element $c$ of the set $A$ is called a successor of the set $B$ if the following conditions are fulfilled:

(i) We have

$$x < c \mbox{ for all } x \in B.$$

(ii) If $x$ is an element of the set $A$ such that $x < c$, then there exists an element $b$ of the set $B$ with

$$x \leq b < c.$$

Proposition. Let $A = (A, \leq)$ be a totally ordered set, and let $a$ be an element of the set $A$. Then the element $a$ is the successor of the initial segment

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

Definition. Let $A$ be a totally ordered set, and let $B$ be a subset of the set $A$. The set $B$ is called an initial part of the set $A$ if the following condition is fulfilled:

If $b$ is an element of the set $B$ and if $x$ is an element of the set $A$ such that $x < b$, then the element $x$ is contained in the set $B$.

Theorem. Let $A = (A, \leq)$ be a totally ordered set, let $B$ be an initial part of the set $A$, and let $c$ be an element of the set $A$. Then the following conditions are equivalent:

(i) The element $c$ is a successor of the set $B$.

(ii) We have
$$B = A_c := \{ x \in A \mid x < c \}.$$

Corollary. Let $A = (A, \leq)$ be a totally ordered set, and let $a$ and $b$ be two elements of the set $A$. Then the following statements are equivalent:

(i) The element $b$ is a successor of the element $a$.

(ii) The element $a$ is a predecessor of the element $b$.

(iii) The element $b$ is a successor of the set

$$\bar{A}_a := \{ x \in A \mid x \leq a \}.$$

(iv) We have

$$\bar{A}_a = A_b.$$

## Well-Ordering

In this section we will explain what well-ordered sets are, and we will introduce their elementary properties:

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

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

$$x \geq b \mbox{ for all } x \in B.$$

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

Theorem. Let $A = (A, \leq)$ be a finite totally ordered set. Then the pair $(A, \leq)$ is well-ordered.

Theorem. The pair $(\mathbb{N}_0, \leq)$ is well-ordered (where $\leq$ denotes the standard order).

Theorem. Let $A = (A, \leq_A)$ be a totally ordered set, and let $B = A \mathbin{\dot{\cup}} \{ b \}$ be the one point extension of the set $A$.

If the pair $(A, \leq)$ is well-ordered, then the pair $(B, \leq)$ is well-ordered, too.

Proposition. Let $(A, \leq)$ be a well-ordered set, and let $a$ be an element of the set $A$.

(a) The initial segment $A_a := \{ x \in A \mid x < a \}$ of the set $A$ with respect to the element $a$ is well-ordered.

(b) The set $\bar{A}_a := \{ x \in A \mid x \leq a \}$ is well-ordered.

## Characterizations of Well-Ordered Sets

In this section we will explain the relation between well-ordered sets and initial parts and successors:

Theorem. Let $A = (A, \leq)$ be a totally ordered set. Then the following conditions are equivalent:

(i) The pair $A = (A, \leq)$ is well-ordered.

(ii) Let $B$ be an initial part of the set $A$, and let $B \neq A$. Then the set $B$ is an initial segment of the set $A$.

(iii) Let $B$ be an initial part of the set $A$, and let $B \neq A$. Then the set $B$ has a successor.

Theorem. Let $A = (A, \leq)$ be a totally ordered set. Then the following conditions are equivalent:

(i) The pair $A = (A, \leq)$ is well-ordered.

(ii) Let $B$ be a subset of the set $A$ such that there exists an element $a$ of the set $A$ with

$$x < a \mbox{ for all } x \in B.$$

Then the set $B$ has a successor.

## Initial Segments and Well-Ordered Sets

One idea of well-ordered sets is to start with an initial segment and then to go a step further either by considering a one-point extension or by considering unions of initial segments:

Theorem. Let $A = (A, \leq)$ be a well-ordered set, and let $B$ be an initial part of the set $A$. Then one of the following possibilities occurs:

(i) We have $B = A$.

(ii) The set $B$ is an initial segment of the set $A$, that is, there exists an element $a$ of the set $A$ such that

$$B = \{ x \in A \mid x < a \}.$$

Theorem. Let $A = (A, \leq)$ be a well-ordered set, let $a$ be an element of the set $A$, and let

$$\bar{A}_a := \{ x \in A \mid x \leq a \}.$$

Then one of the following possibilities occurs:

(i) The element $a$ is the maximum of the set $A$, and we have $\bar{A}_a = A$.

(ii) There exists an element $b$ of the set $A$ such that

$$\bar{A}_a = A_b = \{ x \in A \mid x < b \}.$$

Corollary. Let $A$ be a well-ordered set, and let $a$ be an element of the set $A$. Then the element $a$ is the maximum of the set $A$, or it has a successor $b$.

Theorem. Let $A$ be a well-ordered set, and let $\big( A_i \big)_{i \in I}$ be a family of initial segments of the set $A$. Then the set $\bigcup_{i \in I} A_i$ is either an initial segment of the set $A$, or we have

$$A = \bigcup_{i \in I} A_i.$$

Theorem. Let $A$ be a well-ordered set, and let

$$B := \bigcup_{x \in A} A_x.$$

The one of the following possibilities occurs:

(i) The set $A$ has a maximum $m$, and we have $B = A_m$.

(ii) The set $A$ has no maximum, and we have $B = A$.

Corollary. Let $(A, \leq)$ be a well-ordered set, and let $b$ be an element of the set $A$. Then exactly one of the following possibilities occurs:

(i) The element $b$ has no predecessor. In this case we have

$$A_b = \bigcup_{z < b} A_z.$$

(ii) The element $b$ has a (unique) predecessor $a$. In this case the predecessor $a$ is the maximal element of the initial segment $A_b := \{ x \in A \mid x < b \}$, and we have

$$A_b = \bar{A}_a := \{ x \in A \mid x \leq a \} \mbox{ and } A_b = A_a \cup \{ a \}.$$

Definition. Let $(A, \leq)$ be a well-ordered set, and let $a$ be an element of the set $A$ which has no predecessor. Then the number $a$ is called a limit number.

## The Principle of Transfinite Induction

In this section we will explain the principle of transfinite induction which generalizes the principle of induction from the natural numbers to the well-ordered sets. In addition, we will introduce the second principle of induction for natural numbers:

Theorem. (Principle of Transfinite Induction) Let $(A, \leq)$ be a well-ordered set. For an element $z$ of the set $A$, we denote by

$$A_z := \{ x \in A \mid x < z \}$$

the initial segment of the set $A$ with respect to the element $z$. Let $B$ be a subset of the set $A$ fulfilling the following condition:

$A_z \mapsto z$: For all elements $z$ of the set $A$, it follows from $A_z \subseteq B$ that the element $z$ is contained in the set $B$.

Then we have $B = A$.

Theorem. (Second Principle of Induction) Suppose that $(A_n)_{n \in \mathbb{N}_0}$ is a family of sentences with the following properties:

(i) $n = 0$: The sentence $A_0$ is true.

(ii) $\{0, 1, \ldots, n\} \mapsto n + 1$: If the sentence $A_j$ is true for all numbers $j = 0, 1, \ldots, n$, then the sentence $A_{n + 1}$ is also true.

Then every sentence of the family $(A_n)_{n \in \mathbb{N}_0}$ is true.

## The Well-Ordering Theorem

In this section we will explain one of the two main results about well-ordering, namely that every set can be well-ordered:

Theorem. (Zermelo) Every set $A$ can be well-ordered, that is, there exists an order $\leq_A$ on the set $A$ such that the pair $(A, \leq_A)$ is well-ordered.

French / German. Well-ordering theorem = Thórème de Zermelo = Wohlordnungssatz.

## Final Segments in Well-Ordered Sets

One proof of the well-ordering theorem is based on final segments. In this section we will explain final segments in well-ordered sets in order to motivate the (second) proof of the well-ordering theorem:

Definition. Let $A$ be non-empty set, and let $\alpha : {\cal P}(A) \setminus \{ \emptyset \} \rightarrow A$ be a choice function on the set $A$.

The set ${\cal A}$ is called a $\theta$-chain with respect to the pair $(A, \alpha)$ if it fulfills the following conditions:

(i) The set $A$ and the empty set $\emptyset$ are elements of the set ${\cal A}$.

(ii) If the set $X \neq \emptyset$ is an element of the set ${\cal A}$, then the set $X’ := X \setminus \{ \alpha(X) \}$ is also an element of the set ${\cal A}$.

(iii) If $\big( X_i \big)_{i \in I}$ is a family of sets of the set ${\cal A}$ for some index set $I \neq \emptyset$, then we have

$$\bigcap_{i \in I} X_i \in {\cal A}.$$

Proposition. Let $A \neq \emptyset$ be a well-ordered set. For each element $a$ of the set $A$, let

$$T_a := \{ x \in A \mid x \geq a \}$$

be the final segment of the set $A$ with respect to the element $a$. Let

$${\cal T} := \{ T_a \mid a \in A \} \cup \{ \emptyset \},$$

and let

$$\alpha : {\cal P}(A) \setminus \{ \emptyset \} \rightarrow A, \: \alpha : X \mapsto \min(X)$$

where $\min(X)$ denotes the minimal element of the set $X$.

(a) We have

$$\alpha(T_a) := a \mbox{ for all } a \in A.$$

(b) The set ${\cal T}$ is a $\theta$-chain with respect to the pair $(A, \alpha)$.

(c) Let ${\cal S}$ be a further $\theta$-chain with respect to the pair $(A, \alpha)$ such that ${\cal S} \subseteq {\cal T}$. Then we have ${\cal S} = {\cal T}$.

## A Second Proof of the Well-Ordering Theorem

The proof explained in this section is based on $\theta$-chains or, more generally, on Dedekind chains introduced by Richard Dedekind:

Proposition. Let $A$ be a non-empty set, and let

$$\alpha : {\cal P}(A) \setminus \{ \emptyset \} \rightarrow A$$

be a choice function on the set $A$.

Then there exists a minimal $\theta$-chain ${\cal T}$ with respect to the pair $(A, \alpha)$.

Theorem. (Zermelo) Every set $A$ can be well-ordered, that is, there exists an order $\leq_A$ on the set $A$ such that the pair $(A, \leq_A)$ is well-ordered.

## Isomorphisms of Well-Ordered Sets

In this section we will explain the second main theorem about well-ordered sets, namely that any two well-ordered sets are either isomorphic or that one set is isomorphic to an initial segment of the other one:

Theorem. Let $(A, \leq_A)$ and $(B, \leq_B)$ be two well-ordered sets, and let $\alpha : A \rightarrow B$ and $\beta : A \rightarrow B$ be two isomorphisms from the set $A$ onto the set $B$. Then we have $\alpha = \beta$.

Theorem. Let $(A, \leq)$ be a well-ordered set, and let $\alpha : A \rightarrow A$ be an automorphism of the set $A$. Then we have $\alpha = \mbox{id}$.

Theorem. Let $(A, \leq)$ be a well-ordered set, and let $\alpha : A \rightarrow A$ be an injective homomorphism from the set $A$ into itself. Then we have

$$x \leq \alpha(x) \mbox{ for all } x \in A.$$

Theorem. Let $(A,\leq)$ be a well-ordered set. Then the set $A$ is not isomorphic to any of its initial segments.

Theorem. Let $(A,\leq_A)$ and $(B, \leq_B)$ be two well-ordered sets. Then one of the following cases occurs:

(i) The sets $A$ and $B$ are isomorphic.

(ii) There exists an element $a$ of the set $A$ such that the set $B$ is isomorphic to the initial segment $A_a := \{ x \in A \mid x <_A a \}$ of the set $A$.

(iii) There exists an element $b$ of the set $B$ such that the set $A$ is isomorphic to the initial segment $B_b := \{ y \in B \mid y <_B b \}$ of the set $B$.

## The Equivalence of the Axiom of Choice, the Lemma of Zorn and the Well-Ordering Theorem

The axiom of choice is one of the axioms of Zermelo and Fraenkel. As we will explain in this section, the axiom of choice can be replaced by the lemma of Zorn or by the well-ordering theorem. In this sense, they are all equivalent:

Theorem. Let ${\cal U}$ be a mathematical universe fulfilling the axioms ZFC-1 to ZFC-8 and ZFC-10. Then the following statements are equivalent:

(i) The Axiom of Choice (see Unit Families and the Axiom of Choice).

(ii) The Lemma of Zorn (see Unit Ordered Sets and the Lemma of Zorn).

(iii) The well-ordering Theorem (Theorem [#card-th-every-set-can-be-well-ordered]).

## Notes and References

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

Do you want to learn more? The next step is the definition of the so-called ordinal numbers. They are used to “count” the number of elements of a well-ordered set. Ordinal numbers will be explained in Unit [Ordinal Numbers – in preparation].