Cardinal 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 Cardinal 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 4th 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 Theorem of Cantor and Bernstein

Definition. Two sets $A$ and $B$ are called equivalent if there exists a bijective function $\alpha : A \rightarrow B$ from the set $A$ onto the set $B$. If $A$ and $B$ are two equivalent sets, we write $A \sim B$.

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

(a) We say that the set $B$ dominates the set $A$ if there exists a subset $B’$ of the set $B$ equivalent to the set $A$, that is, there exists a bijective function $\alpha : A \rightarrow B’$ from the set $A$ onto a subset $B’$ of the set $B$.

(b) If the set $B$ dominates the set $A$, then we write $A \preceq B$.

(c) If the set $B$ dominates the set $A$ and if the sets $A$ and $B$ are not equivalent, then we say that the set $B$ strictly dominates the set $A$. In this case, we write $A \prec B$.

Theorem. Let $A$ and $B$ be two non-empty sets. Then the following conditions are equivalent:

(i) The set $B$ dominates the set $A$, that is, $A \preceq B$.

(ii) There exists an injective function $\alpha : A \rightarrow B$ from the set $A$ into the set $B$.

(iii) There exists a surjective function $\beta : B \rightarrow A$ from the set $B$ onto the set $A$.

Theorem. (Cantor and Bernstein) Let $A$ and $B$ be two sets.

If $A \preceq B$ and $B \preceq A$, then we have $A \sim B$.

Corollary. Let $A$, $B$ and $C$ be three sets.

(a) We have $A \preceq A$ (reflexivity).

(b) We have $A \preceq B$ and $B \preceq A$ if and only if $A \sim B$ (symmetry).

(c) If $A \preceq B$ and $B \preceq C$, then we have $A \preceq C$ (transitivity).

Theorem. Let $A$ and $B$ be two sets, and suppose that there exist two injective functions $\alpha : A \rightarrow B$ and $\beta : B \rightarrow A$. Then there exists a bijective function $\gamma : A \rightarrow B$.

Further Proofs of the Theorem of Cantor and Bernstein

The proof of Dedekind and Zermelo is based on the following theorem:

Theorem. (Dedekind and Zermelo) Let $A$ be a set which is equivalent to a subset $B$ of the set $A$. If $C$ is subset of the set $A$ with

$$
B \subseteq C \subseteq A,
$$

then the set $C$ is equivalent to the sets $A$ and $B$.

The Comparability Theorem

Theorem. (Comparability Theorem) Let $A$ and $B$ be two sets. Then we have $A \preceq B$ or $B \preceq A$.

Theorem. Let $A$ and $B$ be two sets. Then exactly one of the following cases occurs:

(i) We have $A \sim B$.

(ii) We have $A \prec B$.

(iii) We have $B \prec A$.

A Second Proof of the Comparability Theorem

The second proof of the comparability theorem is based on the Lemma of Zorn:

Theorem. (Lemma of Zorn) Let $A = (A, \leq)$ be a partially ordered set such that every chain $C$ of the set $A$ has an upper bound in the set $A$. (A chain of the set $A$ is a totally ordered subset of the set $A$.)

Then the set $A$ contains a maximal element.

Cardinal Numbers

Definition. Let $A = (A, \leq)$ be an ordered set. The set $A$ is called an ordinal number if the pair $A = (A, \leq)$ is well-ordered and if we have

$$
a = A_a = \{ x \in A \mid x < a \} \mbox{ for all } a \in A.
$$

In other words each element $a$ of the set $A$ equals the initial segment with respect to the element $a$.

Definition. Let $A$ be an ordinal number. The ordinal number $A$ is called a cardinal number if it fulfills the following condition: For each ordinal number $B$ satisfying

$$
B \subseteq A \mbox{ and } B \sim A
$$

we have $B = A$.

Theorem. Let $A$ be a set. Then there exists exactly one cardinal number $a$ such that $A \sim a$.

Definition. Let $A$ be a set, and let $a$ be the unique cardinal number with $A \sim a$ (Theorem [#card-th-cardinality]). The cardinal number $a$ is called the cardinality of the set $A$. It is denoted by $|A| := a$.

French / German. Cardinality of a set = Cardinalité = Kardinalität or Mächtigkeit.

Theorem. Let $A$ and $B$ be two sets. Then the following conditions are equivalent:

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

(ii) We have $|A| = |B|$.

Theorem. Let $A$ be a non-empty set. There does not exist a set ${\cal A}$ such that

$$
X \in {\cal A} \mbox{ if and only if } X \sim A.
$$

In other words, the sets equivalent to the set $A$ do not form a set.

The Order of the Cardinal Numbers

Definition. Let $a$ and $b$ be two cardinal numbers. We set

(a) $a \leq b$ if and only if $a \subseteq b$.

(b) $a < b$ if and only if $a \subset b$.

(c) $a \geq b$ if and only if $b \subseteq a$.

(d) $a > b$ if and only if $b \subset a$.

The so-defined relation $\leq$ on each set of cardinal numbers is called the standard order on the cardinal numbers.

French / German. Standard order on the cardinal numbers = Ordre standard sur le nombres ordineaux = Standardordnung auf den Kardinalzahlen.

Theorem. Let $A$, $B$ and $C$ be three sets, and let $\leq$ be the standard order of the cardinal numbers.

(a) We have $|A| \leq |A|$.

(b) If $|A| \leq |B|$ and $|B| \leq |A|$, then we have $|A| = |B|$.

(c) If $|A| \leq |B|$ and $|B| \leq |C|$, then we have $|A| \leq |C|$.

(d) Let $A$ and $B$ be two sets. Then we either have $|A| = |B|$ or $|A| < |B|$ or $|A| > |B|$.

Theorem. Let $A$ and $B$ be two sets.

(a) The following conditions are equivalent:

(i) We have $A \preceq B$.

(ii) We have $|A| \leq |B|$.

(iii) We have $|A| \subseteq |B|$.

(b) The following conditions are equivalent:

(i) We have $A \prec B$.

(ii) We have $|A| < |B|$.

(iii) We have $|A| \subset |B|$.

(iv) We have $|A| \in |B|$.

Corollary. Let $A$ and $B$ be two sets. The following conditions are equivalent:

(i) We have $|A| \leq |B|$.

(ii) There exists an injective mapping $\alpha : A \rightarrow B$ from the set $A$ into the set $B$.

(iii) There exists a surjective mapping $\beta : B \rightarrow A$ from the set $B$ onto the set $A$.

Corollary. (a) Let $A$ and $B$ be two sets. If the set $A$ is a subset of the set $B$, then we have $|A| \leq |B|$.

(b) Let $a$ and $b$ be two cardinal numbers with $a \leq b$. Then there exist two sets $A$ and $B$ such that

$$
|A| = a, \: |B| = b \mbox{ and } A \subseteq B.
$$

The Theorem of Cantor

Theorem. (Cantor) Let $A$ be an arbitrary set. Then we have

$$
|A| < |{\cal P}(A)|
$$

where ${\cal P}(A)$ denotes the power set of the set $A$.

Theorem. Let $A$ be a set. Then the following set exists:

$$
{\cal A} := \{ X \mbox{ ordinal number } \mid X \sim A \}.
$$

Theorem. Let $A$ be a set. Then we have

$$
|A| = \mbox{min} \: \{ X \mbox{ ordinal number } \mid X \sim A \}.
$$

Theorem. (a) There does not exist a set ${\cal C}$ with the following property:

$$
X \in {\cal C} \mbox{ if and only if } X \mbox{ is a cardinal number}
$$

in other words, the cardinal numbers do not form a set.

(b) There does not exist a set ${\cal C}$ with the following property:

$$
X \in {\cal C} \mbox{ if and only if } X \mbox{ is a ordinal number}
$$

in other words, the ordinal numbers do not form a set.

Finite Sets

Definition. (a) A set $A$ is called {\bf finite} if it is equivalent to a natural number $n$, that is, if there exists a natural number $n$ such that $A \sim n$.

In this case we say that {\bf the set $A$ has $n$ elements}, and we write $|A| = n$.

(b) If a set $A$ is not finite, then it is called {\bf infinite}. In this case we write $|A| = \infty$.

Theorem. Every natural number is a cardinal number.

Theorem. The set $\mathbb{N}_0$ of the natural numbers is a cardinal number.

Definition. The cardinal number $\mathbb{N}_0$ is denoted by $\aleph_0$ (speak: Alef zero). ($\aleph$ is the first letter of the hebrew alphabet.)

Infinite Sets

Theorem. For each set $A$, the following conditions are equivalent:

(i) The set $A$ is infinite.

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

(iii) We have $\mathbb{N}_0 = | \mathbb{N}_0 | \leq |A|$.

Theorem. Let $A$ be a set. Then the following two conditions are equivalent:

(i) The set $A$ is infinite.

(ii) There exists a proper subset $B$ of the set $A$ and a bijective function $\alpha : A \rightarrow B$ from the set $A$ onto the set $B$.

Definition. A set $A$ is called countable if we have $A \preceq \mathbb{N}_0$, and it is called countably infinite if we have $A \sim \mathbb{N}_0$.

Proposition. (a) Every subset of the set $\mathbb{N}_0$ is countable.

(b) Every subset of a countable set is countable.

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 [Cardinal Arithmetic – in preparation] we will extend the elementary operations $m + n$, $m \cdot n$ and $m^n$ from the natural numbers to general cardinal numbers. We will explain equations and inequalities like

$$
a + a = a, \: a \cdot a = a \mbox{ and } 2^a > a \mbox{ for all infinite cardinal numbers } a.
$$

Download

Cardinal Numbers

math_garden_card_cardinal_numbersDownload

The pdf document is the full text including the proofs.

Current Version: 1.0.0 from January 2021