Cardinal Numbers

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:

• A set $B$ (strictly) dominates a set $A$
• Cardinal Number
• Cardinality of a Set
• Standard Order on the Cardinal Numbers
• The Cardinal Number $\aleph_0$
• Countable Set

---

The main results of this unit are:

• The Theorem of Cantor and Bernstein (see Theorem [#card-th-cantor-bernstein])
• The Theorem of Dedekind and Zermelo (see Theorem [#card-th-cardinality-between])
• The Comparability Theorem (see Theorem [#card-th-comparability-theorem])
• Existence of a unique cardinal number $a$ such that $|A| = a$ (see Theorem [#card-th-cardinality])
• The sets equivalent to a set $A \neq \emptyset$ do not form a set (see Theorem [#card-th-sim-n-no-set])
• The Theorem of Cantor (see Theorem [#card-th-cantor-x-smaller-p-x])
• We have $|A| = \mbox{min} : \{ X \mbox{ ordinal number } \mid X \sim A \}$ (see Theorem [#card-th-definition-cardinality])
• The cardinal numbers do not form a set (see Theorem [#card-th-cardinal-numbers-no-set])
• The ordinal numbers do not form a set (see Theorem [#card-th-cardinal-numbers-no-set])
• Every natural number is a cardinal number (see Theorem [#card-th-natural-number-cardinal-number])
• The set $\mathbb{N}_0$ of the natural numbers is a cardinal number (see Theorem [#card-th-nz0-cardinal-number])
• A set $A$ is infinite if and only if $\mathbb{N}_0 \leq |A|$ (see Theorem [#card-th-nz0-smaller-a-infinite])
• A set $A$ is infinite if and only if there exists a bijective mapping $\alpha : A \rightarrow B$ from the set $A$ onto a proper subset $B$ of the set $A$ (see Theorem [#card-th-infinite-subset-bijective])

---

---

The Theorem of Cantor and Bernstein

---

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

---

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

---

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

---

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

---

---

---

Further Proofs of the Theorem of Cantor and Bernstein

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

---

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

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

---

---

The Comparability Theorem

---

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

---

Then the set $A$ contains a maximal element.

---

---

Cardinal Numbers

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

---

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

we have $B = A$.

---

---

---

---

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

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

---

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

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

---

---

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

---

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

---

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

---

(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

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

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

---

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

---

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

---

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

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

---

---

---

---

---

Infinite Sets

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

---

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

---

---

(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

The pdf document is the full text including the proofs.

Current Version: 1.0.0 from January 2021