# Ordered Sets and the Lemma of Zorn

- Introduction
- Ordered Sets
- Isomorphisms of Ordered Sets
- Initial Segments
- Chains of Ordered Sets
- The Lemma of Zorn
- Notes and References
- Download

## Introduction

Please note that the text on this web page gives a summary of the Unit **Ordered Sets and the Lemma of Zorn**. A full text including the proofs is available as a separate pdf-document at the end of this page.

The present unit explains the concept of ordered sets and the Lemma of Zorn.

### Ordered Sets:

Mathematics often uses features of everyday life and transforms them into an exact and well defined mathematical context. Ordered sets are a good example for such a procedure.

The starting point are observations like *Tom is bigger than Mary*, *Karl has more money than Tom* or *Mary is happier than Karl*. The method to transform these observations into mathematics are relations: A **relation on a set **$A$ is a subset $R$ of the direct product $A \times A$. Two elements $x$ and $y$ of the set $A$ are called **related with respect to the relation** $R$ if we have

$$

(x, y) \in R.

$$

Relations are explained in detail in Unit *Direct Products and Relations*.

Order relations are relations with additional properties that are inspired by the comparison *smaller than or equal to*.

Firstly, any object is smaller than or equal to itself, hence we require

$$

x R x \mbox{ for all } x \in A.

$$

Secondly, if we have the situation that the height of one house $H_1$ is smaller than or equal to the height of another house $H_2$, and if the height of the house $H_2$ is smaller than or equal to the height of the house $H_1$, then the heights of the houses $H_1$ and $H_2$ are equal.

Hence, our second requirement for an order relation $R$ is as follows: If $x$ and $y$ are two elements of the set $A$ such that $x R y$ and $y R x$, then we have $x = y$.

Finally, our third requirement corresponds to the following observation: If $x$ is smaller than or equal to $y$ and if $y$ is smaller than or equal to $z$, then $x$ is smaller than or equal to $z$. In other words, if $x R y$ and $y R z$, then we have $x R z$.

In general, we use the more intuitive symbol $\leq$ for an order relation such that our requirements become:

(1) $x \leq x$ for all $x \in A$.

(2) $x \leq y$ and $y \leq x$ imply $x = y$ for all $x, y \in A$.

(3) $x \leq y$ and $y \leq z$ imply $x \leq z$ for all $x, y, z \in A$.

For more details see the definition of a partially ordered set. Note that the relation $\leq$ is still a subset of the direct product $A \times A$.

We do not require that every two elements of an ordered set may be compared. For example, the set

$$

A := \{ a, b, c \}

$$

with $a \leq b$ and $a \leq c$ is an ordered set, but we neither have $b \leq c$ nor $c \leq b$. Therefore an order is also called a **partial order**. The set theoretical inclusion $\subseteq$ is a typical example for a partial order.

In a **totally ordered** set $A$ we have $x \leq y$ or $y \leq x$ for all elements $x$ and $y$ of the set $A$. Hence, we can order all elements of the set $A$ linearly.

Given a subset $B$ of an ordered set $A$ the set $B$ inherits the order of the set $A$ (see Proposition [#nst-prop-existence-induced-order]).

Often the “simple” substructures play a crucial role for the development of a mathematical theory. Such a simple substructure of an ordered set is a chain: A **chain** is a totally ordered subset of an ordered set. Chains will play a main role in the Lemma of Zorn.

Given an order on a set $A$ often the question arises whether there exist maximal elements in the set $A$. For example, the number 3 is the maximal element of the set $\{ 1, 2, 3\}$ with the natural order, and the elements $b$ and $c$ are the maximal elements of the set $\{ a, b, c \}$ with the order $a \leq b$ and $ a \leq c$.

The open interval $]0, 1[$ does not have a maximal element, but within the set $\mathbb{R}$ of the real numbers the set $]0, 1[$ has upper bounds like 1 or 2. The upper bound 1 is the smallest upper bound which is called a supremum. More formally, if $B$ is a subset of a set $A$. then we have

$m$ **maximum of** $B : \: \Leftrightarrow m \in B$ and $x \leq m$ for all $x \in B$.

$u$ **upper bound of** $B :\: \Leftrightarrow u \in A$ and $x \leq u$ for all $x \in B$

$s$ **supremum of** $B : \: \Leftrightarrow s \in A$ and $x \leq s$ for all $x \in B$ and

$\big( x \leq t \mbox{ for all } x \in B \Rightarrow s \leq t \big)$

(see Definition [#nst-def-maximal-set-order]).

In Unit *Functions and Equivalent Sets* we have defined extensions of functions. The main idea is that we have a family of functions $f_i : A_i \rightarrow B_i$ from some sets $A_i$ into some sets $B_i$ and that we want to extend these functions to *one* function

$$

f : \bigcup_{i \in I} A_i \rightarrow \bigcup_{i \in I} B_i.

$$

For that purpose we need a totally ordered index set $I$, two chains $\big(A_i\big)_{i \in I}$ and $\big(B_i\big)_{i \in I}$ with the property that

$$

A_i \subseteq A_j \mbox{ and } B_i \subseteq B_j \mbox{ if } i \leq j

$$

and functions $f_i : A_i \rightarrow B_i$ from sets $A_i$ into sets $B_i$ with the property that for each two elements $i$ and $j$ of the set $I$ such that $i \leq j$ the function $f_i : A_i \rightarrow B_i$ is induced by the function $f_j : A_j \rightarrow B_j$, that is, we have

$$

f_i(x) = f_j(x) \mbox{ for all } x \in A_i.

$$

For more details see Theorem [#nst-th-extension-bijective-function-to-union].

### Isomorphisms of Ordered Sets:

Given two ordered sets

\begin{eqnarray*}

A & := & \{ a, b, c \} \mbox{ with } a \leq b \mbox{ and } a \leq c \mbox{ and} \\

B & := & \{ x, y, z \} \mbox{ with } x \leq y \mbox{ and } x \leq z

\end{eqnarray*}

the sets are more or less identical if we look at the following correspondence:

$$

\alpha : a \mapsto x, \: b \mapsto y, \: c \mapsto z.

$$

The mapping $\alpha : A \rightarrow B$ is called an **isomorphism of ordered sets**, and it allows to transfer properties from an ordered set $A$ to all ordered sets $B$ isomorphic to the set $A$.

An isomorphism from an ordered set $A$ onto itself is called an **automorphism** of the set $A$. The set of the automorphisms of an ordered set $A$ forms a subgroup of the group of all bijective mappings from the set $A$ onto itself (see Theorem [#nst-th-bijective-functions-group]).

### Initial Segments:

Given an ordered set $A$ and an element $a$ of the set $A$ the **initial segment** $A_a$ is defined to be the set

$$

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

$$

In other words the initial segment is a “first part” of the set $A$. Initial segments will play an important role in the context of well ordered sets (see Unit [*Well Ordered Sets* – in preparation]) and in the context of ordinal numbers (see Unit [*Ordinal Numbers* – in preparation]).

In the present unit we will only introduce some elementary properties of initial segments such as:

The mapping $x \mapsto A_x$ is a bijective mapping from a totally ordered set $A$ onto the set of the initial segments of the set $A$ (see Proposition [#nst-prop-initial-segment-Ax-equals-Ay-then-x-equals-y]).

### Chains of Ordered Sets:

A chain of ordered sets is a family $\big(A_i, \leq_i\big)_{i \in I}$ of ordered sets where one set $A_i$ is embedded in the “next” set $A_j$. More formally, a chain of ordered sets is defined as follows:

Let $I$ be a totally ordered index set. A family $(A_i, \leq_i)_{i \in I}$ is called a **chain of ordered sets** if the following conditions are fulfilled:

(i) The family $(A_i)_{i \in I}$ is a chain, that is, we have $A_i \subseteq A_j$ whenever $i \leq j$.

(ii) For each two elements $i$ and $j$ of the set $I$ such that $i \leq j$, the order $\leq_i$ on the set $A_i$ is induced by the order $\leq_j$ on the set $A_j$, that is, we have

$$

x \leq_i y \mbox{ if and only if } x \leq_j y \mbox{ for all } x, y \in A_i.

$$

An important property of chains of ordered sets is that we can move from the family $\big(A_i, \leq_i\big)_{i \in I}$ of ordered sets to the set

$$

A := \bigcup_{i \in I} A_i

$$

with an order $\leq$ on the set $A$ in such a way that the set $A = (A, \leq)$ is an ordered set and that the orders $\leq_i$ of the sets $A_i$ are all induced by the order $\leq$. In other words, the orders $\leq_i$ can be replaced by one order $\leq$. See Theorem [#nst-th-ordered-chain-order-union].

A similar construction deals with initial segments: If the set $A_i$ is an initial segment of the set $A_j$ whenever $i < j$, then we can simplify this setting by the observation that each set $A_i$ is an initial segment of the set $A := \bigcup_{i \in I} A_i$ (or $A = A_i$). For more details see Theorem [#nst-th-chain-ordered-sets].

Finally, under suitable conditions, one can extend isomorphisms $\alpha_i : A_i \rightarrow B_i$ where $\big( A_i \big)_{i \in I}$ and $\big( B_i \big)_{i \in I}$ are chains of ordered sets to one isomorphism

$$

\alpha : A := \bigcup_{i \in I} A_i \rightarrow B := \bigcup_{i \in I} B_i.

$$

Fore more details see Theorem [#nst-th-extension-order-isomorphism-to-union]. All these results will be helpful in the investigation of well ordered sets and ordinal numbers.

### The Lemma of Zorn:

The Lemma of Zorn is by far the most important result of the present unit. It is *the* tool for many existence theorems in mathematics such as

- the existence of a well ordering on an arbitrary set (see Unit [
*Well Ordered Sets*– in preparation], - the existence of a base in an arbitrary vector space (see Unit [
*Vector Spaces*– in preparation]) or - the existence of a maximal ideal in an arbitrary unitary ring (see Unit
*Ideals in Rings*– in preparation]).

The Lemma of Zorn guarantees the existence of maximal elements in an ordered set $A$ provided that every chain of the set $A$ has an upper bound in the set $A$. More precisely:

Let $A = (A, \leq)$ be an ordered set such that every chain $C$ of the set $A$ has an upper bound in the set $A$. Then the set $A$ contains a maximal element.

The Lemma of Zorn is a consequence of the axiom of choice explained in Unit *Families and the Axiom of Choice*. In fact, both assertions are equivalent.

## Ordered Sets

### Definition of Partial and Total Orders:

Ordered sets are sets with a specific sort of relations. Recall that a relation $R$ on a set $A$ is a subset of the direct product $A \times A$. Fore more details about relations and direct products see Unit *Direct Products and Relations*.

**Definition. ** Let $A$ be a set, and let $R$ be a relation on the set $A$.

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

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

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

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

(b) A partial order is often denoted by $\subseteq$ or by $\leq$.

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

(d) 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**.

**French / German.** (Partially) Ordered Set = Ensemble (partiellement) ordonné = (Partiell) geordnete Menge. Totally ordered set = Ensemble totalement ordonné = Vollständig geordnete Menge.

**Remark. ** A totally ordered set can be visualized as follows:

### Induced Orders:

The following proposition explains how a subset $B$ of an ordered set $A$ inherits the order of the set $A$.

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

Then there exists exactly one order $\leq_B$ 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.

$$

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

$$

See Proposition [#nst-prop-existence-induced-order].

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

**French / German.** Induced order = Ordre induit = Induzierte Ordnung.

**Proposition. ** Let $A = (A, \leq)$ be an ordered set, and let $B = (B, \leq)$ be a subset of the set $A$ with the induced order.

If the pair $A = (A, \leq)$ is totally ordered, then the pair $B = (B, \leq)$ is also totally ordered.

**Definition. ** A subset $C$ of an ordered set $A = (A, \leq)$ is called a **chain** if the subset $C = (C, \leq)$ is totally ordered with respect to the order induced by the order of the set $A$. In particular, a totally ordered set is a chain.

**French / German.** Chain = Chaîne = Kette.

### Elementary Properties of Ordered Sets:

**Proposition. ** The pair $(\emptyset, R)$ is an ordered set if and only if $R = \emptyset$. The pair $(\emptyset, \emptyset)$ is even a totally ordered set.

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

(a) Set $a < b$ if $a \leq b$ and $a \neq b$.

(b) Set $a \geq b$ if $b \leq a$.

(c) Set $a > b$ if $a \geq b$ and $a \neq b$, that is, if $b < a$.

**Proposition. ** Let $A = (A, \leq)$ be an ordered set.

(a) The relation $\geq$ defined in Definition [#nst-def-smaller] is an order on the set $A$.

(b) If the relation $\leq$ is a total order, then the relation $\geq$ is also a total order.

(c) If $a$, $b$ and $c$ are three elements of the set $A$, then we have

(i) If $(a \leq b)$ and $(b < c)$, then we have $(a < c)$.

(ii) If $(a < b)$ and $(b \leq c)$, then we have $(a < c)$.

(iii) If $(a \geq b)$ and $(b > c)$, then we have $(a > c)$.

(iv) If $(a > b)$ and $(b \geq c)$, then we have $(a > c)$.

### Maxima and Suprema of Ordered Sets:

**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 **maximal element** or a **maximum** of the set $B$ if we have

$$

x \leq b \mbox{ for all } x \in B.

$$

Note that the element $b$ (if it exists) is contained in the set $B$.

(b) 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 \mbox{ for all } x \in B.

$$

Note that the element $b$ (if it exists) is contained in the set $B$.

(c) An element $a$ of the set $A$ is called an **upper bound** of the set $B$ if we have

$$

x \leq a \mbox{ for all } x \in B.

$$

Note that the element $a$ (if it exists) is contained in the set $A$, but not necessarily in the set $B$.

(d) An element $a$ of the set $A$ is called a **lower bound** of the set $B$ if we have

$$

x \geq a \mbox{ for all } x \in B.

$$

Note that the element $a$ (if it exists) is contained in the set $A$, but not necessarily in the set $B$.

(e) An element $a$ of the set $A$ is called a **supremum** of the set $B$ if the following conditions are fulfilled:

(i) The element $a$ is an upper bound of the set $B$.

(ii) If $c$ is a second upper bound of the set $B$, then we have $a \leq c$. In other words, the element $a$ is the smallest upper bound of the set $B$.

Note that that the supremum $a$ (if it exists) is an element of the set $A$, but not necessarily of the set $B$.

(f) An element $a$ of the set $A$ is called an **infimum** of the set $B$ if the following conditions are fulfilled:

(i) The element $a$ is a lower bound of the set $B$.

(ii) If $c$ is a second lower bound of the set $B$, then we have $a \geq c$. In other words, the element $a$ is the biggest lower bound of the set $B$.

Note that that the infimum $a$ (if it exists) is an element of the set $A$, but not necessarily of the set $B$.

**French / German.** Maximum = Maximum = Maximum. Minimum = Minimum = Minimum. Maximal element = Élément maximal = Maximales Element. Minimal element = Élément minimal = Minimales Element. Upper bound = Majorant = Obere Schranke. Lower bound = Minorant = Untere Schranke. Supremum = Borne supérieure (or supremum) = Supremum. Infimum = Borne inférieure (or infimum) = Infimum.

**Example. ** Let $A$ be a set, let ${\cal P}(A)$ be the power set of the set $A$, and let $\subseteq$ denote the subset relation. Then the pair $\big( {\cal P}(A), \subseteq \big)$ is a partially ordered set.

The set $A$ is the only maximal element of the set ${\cal P}(A)$, and the empty set $\emptyset$ is the only minimal element of the set ${\cal P}(A)$.

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

(a) If the set $B$ admits a maximum, then the maximum is unique.

(b) If the set $B$ admits a minimum, then the minimum is unique.

(c) If the set $B$ admits a supremum in $A$, then the supremum is unique.

(d) If the set $B$ admits an infimum in $A$, then the infimum is unique.

### Direct Products of Chains:

**Proposition. ** Let $I$ be a totally ordered index set, and let $(A_i)_{i \in I}$ be a family of sets such that the set $A_j$ is a subset of the set $A_k$ if $j \leq k$. Then we have

$$

\big( \bigcup_{i \in I} A_i \big) \times \big( \bigcup_{i \in I} A_i \big) = \bigcup_{i \in I} \big( A_i \times A_i \big).

$$

### One Point Extensions:

One point extensions will be needed in the study of ordinal sets. See Unit [*Ordinal Numbers* – in preparation].

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

**French / German.** The notion *one point extension* is probably no standard notion in mathematics. It is based on the notion *one-point compactification* of Alexandroff. I am not aware of a corresponding French expression. One point extension = Einpunkt-Erweiterung.

**Proposition. ** Let $(A, \leq_A)$ be an ordered set, and let $(B, \leq_B)$ be a one point extension of the pair $(A, \leq)$ where $b$ is an element of the set $B$ not contained in the set $A$.

(a) The order $\leq_A$ of the set $A$ is induced by the order $\leq_B$ of the set $B$.

(b) The pair $(A, \leq_A)$ is totally ordered if and only if the pair $(B, \leq_B)$ is totally ordered.

### Extensions of Functions:

We recall the definition of a function. For more details see Unit *Functions and Equivalent Sets*.

**Definition. ** Let $A$ and $B$ be two sets.

(a) A **function** $f : A \rightarrow B$ from the set $A$ into the set $B$} is a triple $(f, A, B)$ where the set $f$ is a subset of the direct product $A \times B$ with the following property:

For each element $x$ of the set $A$ there is exactly one element $y$ of the set $B$ such that the pair $(x, y)$ is contained in the set $f$.

(b) Let $f : A \rightarrow B$ be a function from the set $A$ into the set $B$, and let $x$ be an element of the set $A$. The unique element $y$ of the set $B$ such that the pair $(x, y)$ is contained in the set $f$ is denoted by $y = f(x)$. We also write $f : x \mapsto y$ or, equivalently, $f : x \mapsto f(x)$.

**Theorem. ** Let $A$ and $B$ be two sets, and let $\alpha : A \rightarrow B$ and $\beta : A \rightarrow B$ be two functions from the set $A$ into the set $B$. Then we have

$$

\alpha = \beta \mbox{ if and only if } \alpha(x) = \beta(x) \mbox{ for all } x \in A.

$$

**Theorem. ** Let $I$ be a totally ordered index set, and let $(A_i)_{i \in I}$ and $(B_i)_{i \in I}$ be two families of sets with the following properties:

(i) The families $(A_i)_{i \in I}$ and $(B_i)_{i \in I}$ are chains, that is, we have

$$

A_i \subseteq A_j \mbox{ and } B_i \subseteq B_j \mbox{ if } i \leq j.

$$

(ii) For each element $i$ of the set $I$, there exists a function $\alpha_i : A_i \rightarrow B_i$ from the set $A_i$ into the set $B_i$.

(iii) For each two elements $i$ and $j$ of the set $I$ such that $i \leq j$ the function $\alpha_i : A_i \rightarrow B_i$ is induced by the function $\alpha_j : A_j \rightarrow B_j$, that is, we have

$$

\alpha_i(x) = \alpha_j(x) \mbox{ for all } x \in A_i.

$$

Let

$$

A := \bigcup_{i \in I} A_i \mbox{ and } B := \bigcup_{i \in I} B_i.

$$

(a) There exists exactly one function $\alpha : A \rightarrow B$ from the set $A = \bigcup_{i \in I} A_i$ into the set $B =\bigcup_{i \in I} B_i$ such that $\alpha|_{A_i} = \alpha_i$ for all elements $i$ of the set $I$.

(b) If the functions $\alpha_i : A_i \rightarrow B_i$ are injective for all elements $i$ of the set $I$, then the function $f : A \rightarrow B$ is also injective.

(c) If the functions $\alpha_i : A_i \rightarrow B_i$ are surjective for all elements $i$ of the set $I$, then the function $f : A \rightarrow B$ is also surjective.

(d) If the functions $\alpha_i : A_i \rightarrow B_i$ are bijective for all elements $i$ of the set $I$, then the function $f : A \rightarrow B$ is also bijective.

**Remark. ** Theorem [#nst-th-extension-bijective-function-to-union] allows to replace the functions $\alpha_i : A_i \rightarrow B_i$ by *one* function $\alpha : A \rightarrow B$.

### Historical Notes:

Partially ordered sets have been introduced by Felix Hausdorff:

*Nehmen wir an, zwischen je zwei verschiedenen Elementen $a$, $b$ einer Menge $A$ bestehe jetzt nicht mehr, wie bei geordneten Mengen, eine und nur eine von zwei Beziehungen ($a < b$, $a > b$), sondern eine und nur eine von drei Beziehungen*

$$

a < b, \: a > b, \: a \parallel b,

$$

*die wir lesen wollen: $a$ vor $b$, $a$ nach $b$, $a$ unvergleichbar mit $b$. Von den beiden ersten setzen wir dieselben Eigenschaften wie im Falle geordneter Mengen voraus, was für die dritte Beziehung notwendig ihre Symmetrie zur Folge hat, d.h.*

*aus* $ a < b, \: a > b, \: a \parallel b$ *folgt* $b > a, \: b < a, \: b \parallel a$;

*aus* $a < b, \: b < c$ *folgt* $a < c$ *(transitives Gesetz)*.

*Eine solche Menge heißt eine teilweise geordnete Menge; die geordneten Mengen sind Spezialfälle der teilweise geordneten, nämlich wenn Paare unvergleichbarer Elemente nicht existieren […]*

See [Hausdorff-1914], p. 139.

*Suppose that between two different elements $a$, $b$ of a set $A$ no longer exist, as with ordered sets, one and only one of two relationships ($a < b$, $a > b$), but one and only one of three relationships*

$$

a < b, \: a > b, \: a \parallel b,

$$

*we want to read: $a$ before $b$, $a$ after $b$, $a$ incomparable with $b$. From the first two we assume the same properties as in the case of ordered sets, which necessarily results in their symmetry for the third relationship, i.e.*

*from* $a < b, \: a > b, \: a \parallel b$ *follows* $b > a, \: b < a, \: b \parallel a$;

*from* $a < b, \: b < c$ *follows* $a < c$ *(transitive law)*.

*Such a set is called a partially ordered set; the ordered sets are special cases of the partially ordered ones, namely when pairs of incomparable elements do not exist […]*

(Translation by the author.)

## Isomorphisms of Ordered Sets

**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

$$

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

$$

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

(b) An injective homomorphism $\alpha: A \rightarrow B$ is called a **monomorphism of ordered sets**.

(c) A surjective homomorphism $\alpha: A \rightarrow B$ is called an **epimorphism of ordered sets**.

(d) 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**.

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

(f) An isomorphism $\alpha: A \rightarrow A$ from the set $A$ onto itself is called an **automorphism of the set $A$**

**French / German.** Homomorphism = Homomorphisme (or morphisme) = Homomorphismus. Monomorphism = Monomorphisme = Monomorphismus. Epimorphism = Épimorphisme = Epimorphismus. Isomorphism = Isomorphisme = Isomorphismus. Automorphism = Automorphisme = Automorphismus.

**Proposition. ** 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$. Then the mapping $\alpha : A \rightarrow B$ is 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.

$$

**Example. ** Let $A = (A, \leq)$ be the ordered set $A := \{a, b, c\}$ such that $a \leq b$ and $a \leq c$. Then the mapping $\alpha : A \rightarrow A$ defined by $\alpha : a \mapsto a$, $b \mapsto c$ and $c \mapsto b$ is an automorphism of the ordered set $A$.

### Elementary Properties of Isomorphisms between Ordered Sets:

**Proposition. ** Let $(A, \leq_A)$ and $(B, \leq_B)$ be two ordered sets, and let $\alpha : A \rightarrow B$ be an isomorphism. Then we have

$$

x <_A y \mbox{ if and only if } \alpha(x) <_B \alpha(y) \mbox{ for all } x, y \in A.

$$

**Proposition. ** Let $(A, \leq_A)$ and $(B, \leq_B)$ be two ordered sets, and let $\alpha: A \rightarrow B$ be an isomorphism from the set $A$ onto the set $B$.

Then the function $\alpha^{-1}: B \rightarrow A$ is an isomorphism from the set $B$ onto the set $A$.

For the proof of Proposition [#nst-prop-isomorphism-ordered-sets-composite] we will need the following elementary property of bijective functions:

**Proposition. ** Let $A$, $B$ and $C$ be three sets, and let $f : A \rightarrow B$ and $g : B \rightarrow C$ be two functions from the set $A$ into the set $B$ and from the set $B$ into the set $C$, respectively.

(a) If the functions $f : A \rightarrow B$ and $g : B \rightarrow C$ are injective, then the function $g \circ f : A \rightarrow C$ is also injective.

(b) If the functions $f : A \rightarrow B$ and $g : B \rightarrow C$ are surjective, then the function $g \circ f : A \rightarrow C$ is also surjective.

(c) If the functions $f : A \rightarrow B$ and $g : B \rightarrow C$ are bijective, then the function $g \circ f : A \rightarrow C$ is also bijective.

**Proposition. ** Let $(A, \leq_A)$, $(B, \leq_B)$ and $(C, \leq_C)$ be three ordered sets.

(a) Suppose that there exist two isomorphisms $\alpha : A \rightarrow B$ and $\beta : B \rightarrow C$ from the set $A$ onto the set $B$ and from the set $B$ onto the set $C$, respectively.

Then the composite $\gamma := \beta \circ \alpha : A \rightarrow C$ is an isomorphism from the set $A$ onto the set $C$.

(b) If $A \cong B$ and $B \cong C$, then we have $A \cong C$.

We will need the following elementary properties of groups in Theorem [#nst-th-isomorphism-ordered-sets-subgroup-functions]:

**Definition. ** (a) A pair $(G, *)$ consisting of a non-empty set $G$ and an operation $* : G \times G \rightarrow G$ on the set $G$ is called a **group** if the following conditions are fulfilled:

(i) We have

$$

x * y \in G \mbox{ for all } x, y \in G \mbox{ (closure)}.

$$

(ii) We have

$$

(x * y) * z = x * (y * z) \mbox{ for all } x, y, z \in G \mbox{ (associativity)}.

$$

(iii) There exists an element ${\rm id}$ of the group $G$ such that

$$

x * {\rm id} = {\rm id} * x = x \mbox{ for all } x \in G \mbox{ (existence of an identity element)}.

$$

(iv) For each element $x$ of the group $G$ there exists an element $y = y_x$, denoted by $x^{-1}$, of the group $G$ such that

$$

x * y = {\rm id} = y * x \mbox{ (existence of an inverse element)}.

$$

A group $G = (G, *)$ is called a **commutative group** or, equivalently, an **abelian group** if we have

$$

x * y = y * x\mbox{ for all } x, y \in G.

$$

(b) If $U$ is a non-empty subset of a group $G = (G, *)$ such that the pair $(U, *_U)$ (where $*_U$ denotes the operation on the set $G$ restricted to the set $U$) is also a group, then the pair $(U, *_U)$ is called a **subgroup of the group** $G$. It is denoted by $U = (U, *)$.

**Proposition. ** Let $G = (G, *)$ be a group, and let $U$ be a non-empty subset of the set $G$.

(a) The pair $U = (U, *)$ is a subgroup of the group $G$ if and only if the following conditions are fulfilled:

(i) We have

$$

u * v \in U \mbox{ for all } u, v \in U.

$$

(ii) For each element $u$ of the set $U$ the inverse $u^{-1}$ is an element of the set $U$.

(b) If the group $G$ is abelian, then the subgroup $U$ is also abelian.

For more details about groups and subgroups see Unit [*Groups and Subgroups* – in preparation].

We recall that the set of the bijective functions from a set $A$ onto itself forms a group:

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

$$

{\cal B}(A) := \{ f : A \rightarrow A \mid f \mbox{ is bijective} \}

$$

be the set of the bijective functions from the set $A$ into itself.

Then the pair $\big( {\cal B}(A), \circ \big)$ is a group where $\circ$ denotes the composition of two functions of the set ${\cal B}(A)$. In general, this group is not abelian.

For more information see Unit *Functions and Equivalent Sets*.

**Theorem. ** Let $(A, \leq)$ be an ordered set, and let

$$

{\cal B}(A) := \{ f : A \rightarrow A \mid f \mbox{ is bijective} \}.

$$

Then the set ${\rm Aut}(A)$ of the automorphisms of the set $A$ is a subgroup of the group ${\cal B}(A)$.

**Definition. ** Let $(A, \leq)$ be an ordered set, and let $G$ be the group of the automorphisms of the set $A$ (Theorem [#nst-th-isomorphism-ordered-sets-subgroup-functions]).

(a) The group $G$ is called the **full automorphism group of the ordered set** $(A, \leq)$. It is denoted by ${\rm Aut}(A)$.

(b) Every subgroup of the group $G$ is called an **automorphism group of the ordered set** $(A, \leq)$.

**French / German.** Automorphism group of an ordered set = Groupe d’automorphismes d’un ensemble ordonné = Automorphismengruppe einer geordneten Menge.

**Proposition. ** Let $(A, \leq)$ be an ordered set, and let ${\rm id} :A \rightarrow A$ be the identity, that is, ${\rm id}(x) = x$ for all elements $x$ of the set $A$.

Then the function ${\rm id} :A \rightarrow A$ is an automorphism of the set $A$.

**Proposition. ** Let $(A, \leq_A)$ and $(B, \leq_B)$ be two ordered sets, and let $\alpha: A \rightarrow B$ be an isomorphism from the set $A$ onto the set $B$.

If the pair $(A, \leq_A)$ is totally ordered, then the pair $(B, \leq_B)$ is totally ordered, too.

### Historical Notes:

Isomorphisms of ordered sets have been introduced by Georg Cantor:

*Zwei geordnete Mengen $M$ und $N$ nennen wir ähnlich, wenn sie sich gegenseitig eindeutig einander so zuordnen lassen, dass wenn $m_1$ und $m_2$ irgend zwei Elemente von $M$, $n_1$ und $n_2$ die entsprechenden Elemente von $N$ sind, alsdann immer die Rangbeziehung von $m_1$ zu $m_2$ innerhalb $M$ dieselbe ist wie die von $n_1$ und $n_2$ innerhalb $N$. Eine solche Zuordnung ähnlicher Mengen nennen wir eine Abbildung derselben aufeinander.*

See [Cantor-1895], p. 497.

*We call two ordered sets $M$ and $N$ similar if they can be clearly assigned to one another such that if $m_1$ and $m_2$ are any two elements of $M$ and if $n_1$ and $n_2$ are the corresponding elements of $N$, then the rank relationship of $m_1$ and $m_2$ within $M$ is always the same as that of $n_1$ and $n_2$ within $N$. We call such an assignment of similar sets a mapping from one set on the other.*

(Translation by the author.)

## Initial Segments

### Definition of Initial Segments:

Initial segments will play an important role in the study of ordinal numbers (see Unit [*Ordinal Numbers* – in preparation]). Here we only present some elementary properties.

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

**French / German.** Initial segment = Section commençante (or Segment initial) = Anfangsstück.

### Elementary Properties of Initial Segments:

**Proposition. ** Let $(A, \leq)$ be an ordered set, let ${\cal A}$ be the set of the initial segments of the set $A$, and let $\alpha : A \rightarrow {\cal A}$ be the mapping from the set $A$ into the set ${\cal A}$ defined by

$$

\alpha : x \mapsto A_x := \{ z \in A \mid z < x \}.

$$

If the set $A$ is totally ordered, then the mapping $\alpha : A \rightarrow {\cal A}$ is bijective.

**Proposition. ** Let $A$ be an ordered set, let $a$ be an element of the set $A$, and let $A_a := \{ x \in A \mid x < a \}$ be the initial segment of the set $A$ with respect to the element $a$. Let $z$ be an element of the initial segment $A_a$.

Then we have

$$

\big( A_a \big)_{z} = A_z

$$

where the sets $A_z$ and $\big( A_a \big)_{z}$ denote the initial segments of the sets $A$ and $A_a$ with respect to the element $z$, respectively.

**Proposition. ** Let $(A, \leq_A)$ and $(B, \leq_B)$ be two ordered sets, and let $\alpha : A \rightarrow B$ be an isomorphism from the ordered set $A$ onto the ordered set $B$.

Let $a$ be an element of the set $A$, and let $A_a := \{ x \in A \mid x < a \}$ be the initial segment of the set $A$ with respect to the element $a$. Then the set $\alpha(A_a)$ is the initial segment of the set $B$ with respect to the element $b := \alpha(a)$, that is,

$$

\alpha(A_a) = B_b = B_{\alpha(a)}.

$$

The following proposition describes the complement of an initial segment:

**Proposition. ** Let $A$ be a totally ordered set, let $a$ be an element of the set $A$, and let

$$

A_a := \{ x \in A \mid x < a \} \mbox{ (initial segment) and } T_a := \{ x \in A \mid x \geq a \}.

$$

(a) We have $A = A_a \mathbin{\dot{\cup}} T_a$.

(b) We have $\big( A_a \big)^c = T_a$ (complement of the set $A_a$ in the set $A$).

(c) We have $\big( T_a \big)^c = A_a$ (complement of the set $T_a$ in the set $A$).

## Chains of Ordered Sets

### Definition of Chains of Ordered Sets:

**Definition. ** Let $I$ be a totally ordered index set. A family $(A_i, \leq_i)_{i \in I}$ is called a **chain of ordered sets** if the following conditions are fulfilled:

(i) The family $(A_i)_{i \in I}$ is a chain, that is, we have $A_i \subseteq A_j$ whenever $i \leq j$.

(ii) For each two elements $i$ and $j$ of the set $I$ such that $i \leq j$, the order $\leq_i$ on the set $A_i$ is induced by the order $\leq_j$ on the set $A_j$, that is, we have

$$

x \leq_i y \mbox{ if and only if } x \leq_j y \mbox{ for all } x, y \in A_i.

$$

**French / German.** Chain of ordered sets = Chaîne d’ensembles ordonnés = Kette geordneter Mengen.

**Theorem. ** Let $I$ be a totally ordered index set, let $(A_i, \leq_i)_{i \in I}$ be a chain of ordered sets, and let $A := \bigcup_{i \in I} A_i$.

(a) There exists exactly one order $\leq_A$ on the set $A$ such that for all elements $i$ of the set $I$ we have

$$

x \leq_A y \mbox{ if and only if } x \leq_i y \mbox{ for all } x, y \in A_i,

$$

that is, the orders $\leq_i$ are induced by the order $\leq$ for all elements $i$ of the set $I$.

(b) If we have $A = A_i$ for an element $i$ of the set $I$, then we have $(A, \leq_A) = (A, \leq_i)$.

Theorem [#nst-th-ordered-chain-order-union] allows to replace a chain of ordered sets by *one* ordered set.

**Definition. ** Let $I$ be a totally ordered index set, let $(A_i, \leq_i)_{i \in I}$ be a chain of ordered sets, and let $A := \bigcup_{i \in I} A_i$.

The order $\leq_A$ on the set $A$ defined in Theorem [#nst-th-ordered-chain-order-union] is called the **order of the set** $A = \bigcup_{i \in I} A_i$ **induced by the chain of ordered sets** $(A_i, \leq_i)_{i \in I}$.

**French / German.** Order induced by a chain of ordered sets = Ordre induit par une chaîne d’ensembles ordonnés = Durch eine Kette geordneter Mengen induzierte Ordnung.

The following proposition prepares the proof of Theorem [#nst-th-chain-ordered-sets].

**Proposition. ** Let $(A, \leq_A)$, $(B, \leq_B)$ and $(C, \leq_C)$ be three ordered sets fulfilling the following conditions:

(i) The set $A$ is a subset of the set $B$, and the set $B$ is a subset of the set $C$.

(ii) The order $\leq_A$ is induced by the order $\leq_B$, that is, we have

$$

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

$$

(iii) The order $\leq_B$ is induced by the order $\leq_C$, that is, we have

$$

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

$$

(a) The order $\leq_A$ is induced by the order $\leq_C$, that is, we have

$$

x \leq_A y \mbox{ if and only if } x \leq_C y \mbox{ for all } x, y \in A.

$$

(b) If there exist two elements $b$ and $c$ of the sets $B$ and $C$, respectively, such that

\begin{eqnarray*}

A & = & \{ x \in B \mid x <_B b \} \mbox{ and } \\

B & = & \{ x \in C \mid x <_C c \},

\end{eqnarray*}

then we have $A = \{ x \in C \mid x <_C b \}$.

**Theorem. ** Let $I$ be a totally ordered index set, and let $(A_i, \leq_i)_{i \in I}$ be a chain of ordered sets fulfilling the following condition:

If $i$ and $j$ are two elements of the set $I$ such that $i < j$, then we have $(A_i, \leq_i) = (A_j, \leq_j)$, or there exists an element $b_{ij}$ of the set $A_j$ such that $A_i = \{ x \in A_j \mid x <_j b_{ij} \}$, that is, the set $A_i$ is an initial segment of the set $A_j$.

Let $A := \bigcup_{i \in I} A_i$, and let $\leq$ be the order on the set $A$ induced by the chain $(A_i, \leq_i)_{i \in I}$ of ordered sets. Then for each element $i$ of the set $I$, one of the following possibilities occurs:

(i) We have $(A_i, \leq_i) = (A, \leq)$.

(ii) There exists an element $b_i$ of the set $A$ such that $A_i = \{ x \in A \mid x < b_i \}$.

In other words, for each element $i$ of the set $I$, the set $A_i$ is either an initial segment of the set $A$, or we have $A_i = A$.

**Theorem. ** Let $I$ be a totally ordered index set, and let $\big( (A_i, \leq_{A_i}) \big)_{i \in I}$ and

$\big( (B_i, \leq_{B_i}) \big)_{i \in I}$ be two families of ordered sets with the following properties:

(i) The families $(A_i)_{i \in I}$ and $(B_i)_{i \in I}$ are chains of ordered sets.

(ii) For each element $i$ of the set $I$, there exists an isomorphism $\alpha_i : A_i \rightarrow B_i$.

(iii) For each two elements $i$ and $j$ of the set $I$ such that $i \leq j$, we have $\alpha_j|_{A_i} = \alpha_i$, that is, we have

$$

\alpha_j(x) = \alpha_i(x) \mbox{ for all } x \in A_i.

$$

Let

$$

A := \bigcup_{i \in I} A_i \mbox{ and } B := \bigcup_{i \in I} B_i,

$$

and let $\leq_A$ and $\leq_B$ be the orders on the sets $A$ and $B$ induced by the chains of ordered sets $(A_i)_{i \in I}$ and $(B_i)_{i \in I}$, respectively.

Then there exists exactly one isomorphism

$$

\alpha : (A, \leq_A) \rightarrow (B, \leq_B)

$$

from the ordered set $A$ onto the ordered set $B$ such that $\alpha_i = \alpha|_{A_i}$, that is,

$$

\alpha(x) = \alpha_i(x) \mbox{ for all } x \in A_i \mbox{ for all } i \in I.

$$

## The Lemma of Zorn

We will prove the Lemma of Zorn as a consequence of the axiom of choice. The axiom of choice is explained in Unit *Families and the Axiom of Choice*. We recall the following consequence of the axiom of choice which will be used in the proof of the Lemma of Zorn:

**Theorem. ** Let $S$ be a non-empty set, and let ${\cal P}(S)$ be its power set, that is, the set of the subsets of the set $S$. Then there exists a function

$$

f : {\cal P}(S) \setminus \{ \emptyset \} \rightarrow S

$$

from the set of the non-empty subsets of the set $S$ into the set $S$ such that the element $f(X)$ is contained in the set $X$ for all non-empty subsets $X$ of the set $S$.

**Theorem. (Lemma of Zorn – Special Case)** Let $S$ be a non-empty set, and consider the ordered set ${\cal P}(S) = \big( {\cal P}(S), \subseteq \big)$ where ${\cal P}(S)$ denotes the power set of the set $S$. Let

$$

\emptyset \neq {\cal D} \subseteq {\cal P}(S)

$$

be a non-empty set of subsets of the set $S$ such that for each chain ${\cal C}$ in the set ${\cal D}$ the set

$$

Z := \bigcup_{X \in {\cal C}} X

$$

is also an element of the set ${\cal D}$.

Then the set ${\cal D} = \big( {\cal D}, \subseteq \big)$ contains a maximal element.

**Theorem. (Lemma of Zorn – General Case)** Let $A = (A, \leq)$ be an ordered set such that every chain $C$ of the set $A$ has an upper bound in the set $A$.

Then the set $A$ contains a maximal element.

**Remark. ** The axiom of choice and the Lemma of Zorn are equivalent in the following sense: The set theoretical axiomatic of Zermelo and Fraenkel consists of the following axioms:

ZFC-0: | Basic Axiom |

ZFC-1: | Axiom of Extension |

ZFC-2: | Axiom of Existence |

ZFC-3: | Axiom of Specification |

ZFC-4: | Axiom of Foundation |

ZFC-5: | Axiom of Pairing |

ZFC-6: | Axiom of Unions |

ZFC-7: | Axiom of Powers |

ZFC-8: | Axiom of Substitution |

ZFC-9: | Axiom of Choice |

ZFC-10: | Axiom of Infinity |

These axioms are explained in the units *The Mathematical Universe* (ZFC-0 to ZFC-4), *Unions and Intersections of Sets* (ZFC-5 to ZFC-7), *Families and the Axiom of Choice* (ZFC-8 and ZFC-9) and [*Successor Sets and the Axioms of Peano* – in preparation] (ZFC-10).

In Theorem [#nst-th-lemma-of-zorn-general] we have deduced the Lemma of Zorn from Axioms ZFC-0 to ZFC-9 (in fact, we did not make use of the axiom of substitution (Axiom ZFC-8)). Alternatively, we could have chosen the Lemma of Zorn as Axiom ZFC-9, and we could have deduced the axiom of choice from the Lemma of Zorn and the preceding axioms.

In Unit [*Well Ordered Sets* – in preparation] we will show that every set can be endowed with a well ordering. This theorem is again equivalent to the axiom of choice. In Unit [*Well Ordered Sets* – in preparation] we will prove the theorem about well orderings using the Lemma of Zorn, and we will show that the axiom of choice can be deduced from the theorem about well orderings. So, finally, we will obtain the following chain of conclusions:

Axiom of Choice $\Rightarrow$ Lemma of Zorn $\Rightarrow$ Theorem about Well Orderings $\Rightarrow$ Axiom of Choice.

### Historical Notes:

The Lemma of Zorn has been formulated by Max Zorn in 1935 as follows:

**Definition 1.** A set $\mathfrak{B} = \{ B\}$ of sets $B$ is called a **chain** if for every two sets $B_1, B_2$ either $B_1 \supset B_2$ or $B_2 \supset B_1$.

**Definition 2.** A set $\mathfrak{A}$ of sets $A$ is said to be **closed (right-closed)** if it contains the union $\bigcup_{B \in \mathfrak{B}} B$ of every chain $\mathfrak{B}$ contained in $\mathfrak{A}$.

*Then our maximum principle is expressible in the following form.*

**(MP)** In a closed set $\mathfrak{A}$ of sets $A$ there exists at least one, $A^*$, not contained as a proper subset in any other $ A \in \mathfrak{A}$.

See [Zorn-1935], p. 667.

Curiously, the article [Zorn-1935] does not contain a proof of Zorn’s lemma, but Zorn announced its proof in a later publication:

*In another paper I shall discuss the relations between MP, the axiom of choice, and the well-ordering theorem. I shall show that they are equivalent if the axiom yielding the set of all subsets of a set is available.*

See [Zorn-1935], p.669.

However, this paper has never been written. Instead, the article [Zorn-1935] contains some applications of the Lemma of Zorn such as the existence of maximal ideals in a unitary ring.

Since the ideas for a proof of the Lemma of Zorn are already contained in the two papers of Ernst Zermelo about the well-ordering theorem ([Zermelo-1904] and [Zermelo-1908a]), Oliver Deiser [Deiser-2020], p. 267, suggests to call the Lemma of Zorn the Lemma of Zermelo-Zorn.

Sometimes the Lemma of Zorn is also called the Lemma of Kuratowski-Zorn (see for example [Wikipedia (Lemma of Zorn)] (Version from 28. April 2020) due to the article [Kuratowski-1922] of Casimir Kuratowski. Kuratowski’s result is related to the Lemma of Zorn, but, in fact, it is not exactly the maximum principle of Zorn explained above. Nevertheless, it is a general method to avoid transfinite numbers in the proof of theorems like the well-ordering theorem.

The result close to the Lemma of Zorn is Theorem II’ of [Kuratowski-1922]. Theorem II’ reads as follows:

**Théorème II’.** Si la fonction $G(X)$ satisfait aux conditions (5) et (21), l’ensemble $S(A)$ (c’est à dire, le plus grand ensemble de la classe $N(A)$) est le plus petit sous-ensemble $Z$ de $E$ qui, tout en contenant $A$, satisfait à l’égalité (15).

See [Kuratowski-1922], p. 83.

**Theorem II’.** If the function $G(X)$ satisfies conditions (5) et (21), the set $S(A)$ (that is, the biggest set of class $N(A)$) is the smallest subset $Z$ of $E$ which, containing $A$, satisfies inequality (15).

(Translation by the author.)

The details of Theorem II’ are spread throughout the article. For the reader’s convenience we reformulate Theorem II’ as follows:

**Theorem. (Theorem of Kuratowski)**

*Let $E$ be a non-empty set, and let*

$$

G : {\cal P}(E) \rightarrow {\cal P}(E)

$$

*be a function from the power set of the set $E$ into itself with the following additional properties:*

$$

X \subseteq G(X) \mbox{ for all } X \in {\cal P}(E) \mbox{ and }

$$

$$

X \subseteq Y \mbox{ implies } G(X) \subseteq G(Y) \mbox{ for all } X, Y \in {\cal P}(E).

$$

*If $A$ is a subset of the set $E$, then there exists a smallest set $S(A)$ of the power set ${\cal P}(E)$ containing the set $A$ as a subset such that*

$$

G \big( S(A) \big) = S(A).

$$

Smallest means that if $Z$ is a further element of the power set ${\cal P}(E)$ such that

$$

A \subseteq Z \mbox{ and } G(Z) = Z,

$$

then the set $S(A)$ is a subset of the set $Z$.

Conditions (5), (21) and (15) are the conditions $X \subseteq G(X)$, $X \subseteq Y \Rightarrow G(X) \subseteq G(Y)$ and $G \big( S(A) \big) = S(A)$, respectively. The class $N(A)$ is an auxiliary set in the proof of Kuratowski. In Theorem III Kuratowski shows that this set $N(A)$ is a chain. Kuratowski applies his method for an alternative proof of the well-ordering theorem and some other results.

## Notes and References

We want to mention that there exists a film with the title Zorn’s lemma from 1970 directed by Hollis Frampton. Fore more details see [Wikipedia – Zorn’s Lemma].

In addition to the articles cited below you will find *textbooks* with respect to this unit in a separate literature list.

[Cantor-1895] Cantor, Georg (1895). “Beiträge zur Begründung der transfiniten Mengenlehre”. In: Mathematische Annalen 46, pp. 481–512.

[Deiser-2020] Deiser, Oliver (2020). Einführung in die Mengenlehre. Die Mengenlehre Cantors und ihre Axiomatisierung durch Ernst Zermelo. URL visited on 03/14/2020.

Earlier versions of this book have been published at Springer Verlag, Berlin, Heidelberg, New York.

[Hausdorff-1914] Hausdorff, Felix (1914). Grundzüge der Mengenlehre. Leipzig: Veit and Comp. For a new edition see [Hausdorff-2002].

[Hausdorf-CW-2] — (2002). Gesammelte Werke. Vol. 2: Grundzüge der Mengenlehre. Ed. by Brieskorn E. et al. Berlin, Heidelberg, and New York: Springer Verlag. For the first edition see [Hausdorff-1914].

[Kuratowski-1922] Kuratowski, Casimir (1922). “Une Méthode d’Elimination des Nombres Transfinis des Raisonnements Mathématiques”. In: Fundamenta Mathematicae 3.1, pp. 76–108.

[Zermelo-1904] Zermelo, Ernst (1904). “Beweis, dass jede Menge wohlgeordnet werden kann”. In: Mathematische Annalen 59, pp. 514–516.

[Zermelo-1908a] — (1908). “Neuer Beweis für die Möglichkeit einer Wohlordnung”. In: Mathematische Annalen 65, pp. 107–128.

[Zorn-1935] Zorn, Max (1935). “A remark on Method in Transfinite Algebra”. In: Bulletin of the American Mathematical Society 41.10, pp. 667–670.

## Download

### Ordered Sets and the Lemma of Zorn:

The pdf document is the full text including the proofs.

### Change History

Version | Date | Changes |

1.0.0 | May 2020 | Creation |

1.0.1 | June 2020 | Minor corrections |