Cardinal Arithmetic

The present unit is part of the following walks

Introduction

lease note that the text on this web page only gives a short summary of the Unit Cardinal Arithmetic. 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 5th unit of the walk The Cardinality of Sets.

You will learn the meaning of the following terms:

The main results of this unit are:

Addition of Cardinal Numbers

The unit contains the two additional sections Elementary Properties of Cardinal Numbers and Extensions of Functions where basic properties of cardinal numbers and of functions are recalled.

Definition. Let $a$ and $b$ be two cardinal numbers, and let $A$ and $B$ be two sets such that $|A| = a$, $|B| = b$ and $A \cap B = \emptyset$. Then the cardinal number $|A \mathbin{\dot{\cup}} B|$ is called the sum of the cardinal numbers $a$ and $b$. It is denoted by $a + b$.

French / German. Sum of cardinal numbers = Somme de nombres cardinaux = Summe von Kardinalzahlen.

Theorem. Let $a$, $b$ and $c$ be three cardinal numbers.

(a) We have $(a + b) + c = a + (b + c)$ (addition is associative).

(b) We have $a + b = b + a$ (addition is commutative).

Theorem. Let $a$, $b$, $c$ and $d$ be four cardinal numbers such that $a \leq b$ and $c \leq d$. Then we have $a + c \leq b + d$.

Definition. Let $I$ be an index set, let $(a_i)_{i \in I}$ be a family of cardinal numbers, and let $(A_i)_{i \in I}$ be a family of pairwise disjoint sets such that $|A_i| = a_i$ for all elements $i$ of the set $I$.

Then the cardinal number $|\bigcup_{i \in I} A_i|$ is called the sum of the cardinal numbers $a_i$. It is denoted by

$$
\sum_{i \in I} a_i := \big| \bigcup_{i \in I} A_i \big|.
$$

Theorem. Let $A$ and $B$ be two sets. Then we have $|A| + |B| = |A \cup B| + |A \cap B|$.

Multiplication of Cardinal Numbers

Definition. (a) Let $a$ and $b$ be two cardinal numbers, and let $A$ and $B$ be two sets such that $|A| = a$ and $|B| = b$. Then the cardinal number $|A \times B|$ is called the product of the cardinal numbers $a$ and $b$. It is denoted by

$$
a \cdot b := |A \times B|.
$$

Alternatively, we also write $ab$ instead of $a \cdot b$.

(b) Let $I$ be an index set, let $(a_i)_{i \in I}$ be a family of cardinal numbers, and let $(A_i)_{i \in I}$ be a family of sets such that $|A_i| = a_i$ for all elements $i$ of the set $I$.

Then the cardinal number $|\prod_{i \in I} A_i|$ is called the product of the cardinal numbers $a_i$. It is denoted by

$$
\prod_{i \in I} a_i := |\prod_{i \in I} A_i|.
$$

French / German. Product of cardinal numbers = Produit des nombres cardinaux = Produkt von Kardinalzahlen.

Theorem. Let $a$, $b$ and $c$ be three cardinal numbers.

(a) We have $(a \cdot b) \cdot c = a \cdot (b \cdot c)$ (multiplication is associative).

(b) We have $a \cdot b = b \cdot a$ (multiplication is commutative).

Theorem. (Distributive Laws) Let $a$, $b$ and $c$ be three cardinal numbers.

(a) We have $a (b + c ) = ab + ac$.

(b) We have $(a + b) c = ac + bc$.

Theorem. Let $a$, $b$, $c$ and $d$ be four cardinal numbers such that $a \leq b$ and $c \leq d$. Then we have $a \cdot c \leq b \cdot d$.

Power of Cardinal Numbers

Definition. Let $a$ and $b$ be two cardinal numbers, and let $A$ and $B$ be two sets such that $|A| = a$ and $|B| = b$. Let ${\cal F}(B, A)$ be the set of the functions $\alpha : B \rightarrow A$ from the set $B$ into the set $A$. Then the cardinal number $|{\cal F}(B, A)|$ is called the $b^{th}$ power of $a$.

It is denoted by $a^b$.

French / German. Power of a cardinal number = Puissance d’un nombre cardinal = Potenz einer Kardinalzahl.

Theorem. Let $a$, $b$ and $c$ be three cardinal numbers.

(a) We have $a^{b + c} = a^b \cdot a^c$.

(b) We have $(a \cdot b)^c = a^c \cdot b^c$.

(c) We have $\big( a^b \big) ^c = a^{bc}$.

Theorem. Let $a$, $b$ and $c$ be three cardinal numbers. If $a \leq b$, then we have $a^c \leq b^c$.

Theorem. Let $A$ be a set, let ${\cal P}(A)$ be the power set of the set $A$, and let ${\cal F} \big(A, \{0, 1\} \big)$ be the set of the functions from the set $A$ into the set $\{0, 1\}$.

Then the set ${\cal P}(A)$ and the set ${\cal F} \big(A, \{0, 1\} \big)$ have the same cardinality.

Theorem. Let $A$ be a set of cardinality $a$.

(a) We have $| {\cal P}(A) | = 2^a$.

(b) We have $a < 2^a$ for all cardinal numbers $a$.

Countable Sets

Definition. (a) A set $A$ is called a countable set if we have $|A| \leq \mathbb{N}_0$.

(b) A set $A$ is called countably infinite if we have $|A| = \mathbb{N}_0$.

Theorem. Let $A$ be an infinite set. Then the set $A$ has a countably infinite subset.

Theorem. Let $a$ be an infinite cardinal number and let $n$ be a natural number. Then we have $a + n = a$.

Theorem. (Cantor) Let the mapping $\alpha : \mathbb{N}_0 \times \mathbb{N}_0 \rightarrow \mathbb{N}_0$ be defined by

$$
\alpha(m, n) := m + \sum_{j = 0}^{m + n} j.
$$

The mapping $\alpha : \mathbb{N}_0 \times \mathbb{N}_0 \rightarrow \mathbb{N}_0$ is bijective.

Theorem. (a) We have $|\mathbb{N}_0 \times \mathbb{N}_0| = |\mathbb{N}_0| \cdot |\mathbb{N}_0| = |\mathbb{N}_0|$.

(b) Let $A$ and $B$ be two countable sets. Then the direct product $A \times B$ is also countable. If the sets $A$ and $B$ are countably infinite, we have $|A \times B| = |A| = |B|$.

(c) Let $A$ be a countably infinite set, and let $a := |A|$. Then we have $a \cdot a = a$.

Theorem. (a) Let $A$ and $B$ be two countable sets. Then the set $A \cup B$ is also countable.

(b) Let $A$ be a countably infinite set, and let $a := |A|$. Then we have $a + a = a$.

Theorem. Let $A_1, \ldots, A_n$ be a finite family of countable sets for some natural number $n$. Then the set $\bigcup_{i = 1}^n A_i$ is also countable.

Theorem. Let $(A_i)_{i \in I}$ be a countable family of countable sets (that is, the set $I$ is countable). Then the set $\bigcup_{i \in I} A_i$ is also countable.

Theorem. Let $A$ be a countably infinite set. Then the set

$$
{\cal C} := \{ X \subseteq A \mid X \mbox{ is finite} \}
$$

of the finite subsets of the set $A$ is countably infinite.

Arithmetic of Infinite Cardinal Numbers

Theorem. Let $a$ be an infinite cardinal number. Then we have $a + a = a$.

Theorem. Let $a$ and $b$ be two cardinal numbers such that at least one of them is infinite. Then we have $a + b = \max \{a, b \}$.

Corollary. Let $A$ and $B$ be two sets. If at least one of the two sets $A$ and $B$ is infinite, then we have

$$
|A \cup B| = |A| + |B| = \max \{ |A|, |B| \}.
$$

Theorem. Let $a$ be an infinite cardinal number. Then we have $a \cdot a = a$.

Corollary. Let $a$ be an infinite cardinal number. Then we have $a^n = a$.

Theorem. (a) Let $a$ and $b$ be two cardinal numbers such that at least one of them is infinite, and suppose that $a \neq 0$ and $b \neq 0$. Then we have $a \cdot b = \max \{a, b \}$.

(b) Let $A$ and $B$ be two non-empty sets, and suppose that at least one of them is of infinite cardinality. Then we have

$$
| A \times B | = \max \{ |A|, |B| \}.
$$

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

(a) We have

$$
| A \cap B | \leq \min \{ |A|, |B| \} \mbox{ and } | A \setminus B | \leq |A|.
$$

(b) Let $A$ be a set. For each two cardinal numbers $r \leq |A|$ and $s \leq |A|$ there exist a set $B$ and a set $C$ such that

$$
r = |A \cap B | \mbox{ and } s = | A \setminus C |.
$$

Theorem. Let $A$ be an infinite set. Then we have

$$
|A| = \big| \{ X \subseteq A \mid X \mbox{ is finite} \} \big|.
$$

Theorem. (König and Zermelo) Let $\big( a_i \big)_{i \in I}$ and $\big( b_i \big)_{i \in I}$ be two families of cardinal numbers, and suppose that we have

$$
a_i < b_i \mbox{ for all } i \in I.
$$

Then we have

$$
\sum_{i \in I} a_i < \prod_{i \in I} b_i.
$$

Summary of the Unit Cardinal Arithmetic

Theorem. Let $a$, $b$ and $c$ be three cardinal numbers.

(a) We have $(a + b) + c = a + (b + c)$.

(b) We have $a + 0 = 0 + a = a$.

(c) We have $a + b = b + a$.

(d) We have $(a \cdot b) \cdot c = a \cdot (b \cdot c)$.

(e) We have $a \cdot 0 = 0 \cdot a =0$ and $a \cdot 1 = 1 \cdot a =a$.

(f) We have $a \cdot b = 0$ if and only if $a = 0$ or $b = 0$.

(g) We have $a \cdot b = b \cdot a$.

(h) We have $a \cdot (b + c) = a \cdot b + a \cdot c$ and $(a + b) \cdot c = a \cdot c + b \cdot c$.

Theorem. Let $a$, $b$, $c$ and $d$ be four cardinal numbers.

(a) If $a \leq c$ and $b \leq d$, then we have $a + b \leq c + d$.

(b) If $a \leq c$ and $b \leq d$, then we have $a \cdot b \leq c \cdot d$.

Theorem. Let $a$, $b$ and $c$ be three cardinal numbers.

(a) We have $a^0 = 1$ and $a^1 = a$.

(b) We have $a^{b + c} = a^b \cdot a^c$.

(c) We have $(a \cdot b)^c = a^c \cdot b^c$.

(d) We have $\big( a^b \big) ^c = a^{bc}$.

(e) If $a \leq b$, then we have $a^c \leq b^c$.

Theorem. Let $a$ and $b$ be two cardinal numbers, and suppose that $a$ is infinite.

(a) We have $a + a = a$.

(b) We have $a + b = \max \{ a, b \}$.

(c) We have $a \cdot a = a$.

(d) If $a \neq 0$ and $b \neq 0$, then we have $a \cdot b = \max \{ a, b \}$.

(e) We have $a < 2^a$.

Theorem. Let $A$ and $B$ be two sets, and let $\big( A_i \big)_{i \in I}$ be a family of sets over an index set $I$.

(a) We have $|A| = | A \setminus B| + | A \cap B |$.

(b) We have $|A| + |B| = | A \cup B | + | A \cap B |$.

(c) We have $|A| + |B| = | A \cup B | = \max \{ |A|, |B| \}$ if it at least one of the two sets $A$ or $B$ is infinite.

(d) We have $| A \cup B | \leq |A| + |B|$.

(e) We have $\Big| \bigcup_{i \in I} A_i \Big| \leq \sum_{i \in I} |A_i|$.

(f) We have $|A \cap B| \leq \min \{ |A|, |B| \}$ for all sets $A$ and $B$, and for each cardinal number $0 \leq c \leq |A|$ there exists a set $C$ such that $| A \cap C | = c$.

(g) We have $|A \setminus B| \leq |A|$ for all sets $A$ and $B$, and for each cardinal number $0 \leq c \leq |A|$ there exists a set $C$ such that $| A \setminus C | = c$.

Theorem. Let $A$ be a set, and let ${\cal P}(A)$ be its power set. Then we have $| {\cal P}(A) | = 2^a$.

Theorem. (a) Let $(A_i)_{i \in I}$ be a countable family of countable sets (that is, the set $I$ is countable). Then the set $\bigcup_{i \in I} A_i$ is also countable.

(b) Let $A$ be an infinite set. Then we have

$$
|A| = \big| \{ X \subseteq A \mid X \mbox{ is finite} \} \big|.
$$

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 main subject of the walk The Cardinality of Sets is to explain the definition of the cardinality of sets and to explain the arithmetic of cardinal numbers. This has been explained in the present and the former units.

However, there is one more unit in this walk, namely the Unit The Axiomatics of von Neumann, Bernays and Gödel. The axiomatics of Zermelo and Fraenkel only knows one type of mathematical objects, namely the sets. This approach has the little disadvantage that there is no term for the collection of all sets since there is no set of all sets. The Axiomatics of von Neumann, Bernays and Gödel defines two types of mathematical objects, namely sets and classes. This allows us to speak of the class of all set or the class of all cardinal numbers. The details will be explained in Unit [The Axiomatics of von Neumann, Bernays and Gödel – in preparation].

Download

Cardinal Arithmetic

math_garden_card_cardinal_arithmeticDownload

The pdf document is the full text including the proofs.

Current Version: 1.0.0 from January 2021