Well-Ordered Sets

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:

• Successors and Predecessors of an element
• Successor of a set
• Initial Part of a set
• Well-Ordered Set
• Well-Ordering
• Limit Number
• Principle of Transfinite Induction, see Theorem [#card-th-transfinite-induction]
• Second Principle of Induction, see Theorem [#card-th-second-principle-induction]
• $\theta$-chain

The main results of this unit are:

• The set $\mathbb{N}_0$ of the natural numbers with its standard order is well-ordered (see Theorem [#card-th-natural-numbers-well-ordered]).
• A pair $A = (A, \leq)$ is well-ordered if and only if each initial part $B \subset A$ is an initial segment if and only if if each initial part $B \subset A$ has a successor (see Theorem [#card-th-char-well-ordered-1]).
• If $A = (A, \leq)$ is well-ordered, then each initial segment $A_a$ is either of the form $A_a = \bigcup_{z < a} A_z$ or of the form $A_a = A_b \cup \{b\}$ for an element $b$ of the set $A$ (see Corollary [#card-cor-successor-well-ordered-set]).
• Principle of Transfinite Induction (see Theorem [#card-th-transfinite-induction]).
• Second Principle of Induction (see Theorem [#card-th-second-principle-induction]).
• The Well-Ordering-Theorem, that is, every set can be well-ordered (see Theorem [#card-th-every-set-can-be-well-ordered]).
• Two isomorphisms $\alpha : A \rightarrow B$ and $\beta : A \rightarrow B$ from a well-ordered set $A$ onto a well-ordered set $B$ are always equal (see Theorem [#card-th-isomorphism-well-ordered-sets-unique]).
• Given two well-ordered sets $A$ and $B$, then we either habe $A \cong B$ or one set is isomorphic to an initial segment of the other one (see Theorem [#card-th-existence-isomorphism-well-ordered-set-and-segment]).
• The Axiom of Choice, the Lemma of Zorn and the Well-Ordering Theorem are equivalent (see Theorem [#card-th-equivalence]).

Ordered Sets

We will recall some definitions from former units:

(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.

$$
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$.

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

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

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:

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

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

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

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

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$.

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

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

(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:

(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.

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

(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:

(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.

(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:

(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 \}.
$$

$$
\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 \}.
$$

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

$$
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$.

(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 \}.
$$

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:

$$
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$.

(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:

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:

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}.
$$

$$
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:

$$
\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)$.

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:

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

(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:

(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].

Download

Well-Ordered Sets

The pdf document is the full text including the proofs.

Current Version: 1.0.0 from January 2021