# Cardinal Numbers

- Introduction
- The Theorem of Cantor and Bernstein
- Further Proofs of the Theorem of Cantor and Bernstein
- The Comparability Theorem
- A Second Proof of the Comparability Theorem
- Cardinal Numbers
- The Order of the Cardinal Numbers
- The Theorem of Cantor
- Finite Sets
- Infinite Sets
- Notes and References
- Download

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

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

The pdf document is the full text including the proofs.

Current Version: 1.0.0 from January 2021