24 Cardinal Arithmetic

One result of our study of the comparative sizes ot sets will be to define a new concept, called cardinal number, and to associate with each set $X$ a cardinal number, denoted by $\text{card } X$. The definitions are such that for each cardinal number $a$ there exist sets $A$ with $\text{card } A = a$. We shall also define an ordering for cardinal numbers, denoted as usual by $\le$. The connection between these new concepts and the ones already at our disposal is easy to describe: it will turn out that $\text{card } X = \text{card } Y$ if and only if $X \sim Y$, and $\text{card } X < \text{card } Y$ if and only if $X \prec Y$. (If $a$ and $b$ are cardinal numbers, $a < b$ means, of course, that $a \le b$ but $a \neq b$.)

The definition of cardinal numbers can be approached in several different ways, each of which has its strong advocates. To keep the peace as long as possible, and to demonstrate that the essential properties of the concept are independent of the approach, we shall postpone the basic construction. We proceed, instead, to study the arithmetic of cardinal numbers. In the course of that study we shall make use of the connection, described above, between cardinal inequality and set domination; that much of a loan from the future will be enough for the purpose.

If $a$ and $b$ are cardinal numbers, and if $A$ and $B$ are disjoint sets with $\text{card } A = a$ and $\text{card } B = b$, we write, by definition, $a + b = \text{card }(A \cup B)$. If $C$ and $D$ are disjoint sets with $\text{card } C = a$ and $\text{card } D = b$, then $A \sim C$ and $B \sim D$; it follows that $A \cup B \sim C \cup D$, and hence that $a + b$ is unambiguously defined, independently of the arbitrary choice of $A$ and $B$. Cardinal addition, thus defined, is commutative $(a + b = b + a)$, and associative $(a + (b + c) = (a + b) + c)$; these identities are immediate consequences of the corresponding facts about the formation of unions.

Exercise 24.1 Prove that if $a, b, c$ and $d$ are cardinal numbers such that $a \le b$ and $c \le d$, then $a + c \le b + d$.

There is no difficulty about defining addition for infinitely many summands. If $\{ a_{i} \}$ is a family of cardinal numbers, and if $\{ A_{i} \}$ is a correspondingly indexed family of pairwise disjoint sets such that $\text{card } A_{i} = a_{i}$ for each $i$, then we write, by definition,

\[ \sum_{i} a_{i} = \text{card } (\bigcup_{i} A_{i} ). \]

As before, the definition is unambiguous.

To define the product $ab$ of two cardinal numbers $a$ and $b$, we find sets $A$ and $B$ with $\text{card } A = a$ and $\text{card } B = b$, and we write $ab = \text{card } (A \times B)$. The replacement of $A$ and $B$ by equivalent sets yields the same value of the product. Alternatively, we could have defined $ab$ by “adding $a$ to itself $b$ times”; this refers to the formation of the infinite sum $\sum_{i \in I} a_{i}$, where the indexed set $I$ has cardinal number $b$, and where $a_{i} = a$ for each $i$ in $I$. The reader should have no difficulty in verifying that this proposed alternative definition is indeed equivalent to the one that uses Cartesian products. Cardinal multiplication is commutative $(ab = ba)$ and associative $(a(bc) = (ab)c)$, and multiplication distributes over addition $(a(b + c) = ab + ac)$; the proofs are elementary.

Exercise 24.2 Prove that if $a, b, c$, and $d$ are cardinal numbes such that $a \le b$ and $c \le d$, then $ac \le bd$.

There is no difficulty about defining multiplication for infinitely many factors. If $\{ a_{i} \}$ is a family of cardinal numbers, and if $\{ A_{i} \}$ is a correspondingly indexed family of sets such that $\text{card } A_{i} = a_{i}$ for each $i$, then we write, by definition,

\[ \prod_{i} a_{i} = \text{card } ( \bigtimes_{i} A_{i} ). \]

The definition is unambiguous.

Exercise 24.3 If $\{ a_{i} \}$ ($i \in I$) and $\{ b_{i} \}$ ($i \in I$) are families of cardinal numbers such that $a_{i} < b_{i}$ for each $i$ in $I$, then $\sum_{i}a_{i} < \prod_{i}b_{i}$.

We can go from products to exponents the same way as we went from sums to products. The definition of $a^{b}$, for cardinal numbers $a$ and $b$, is most profitably given directly, but an alternative approach goes via repeated multiplication. For the direct definition, find sets $A$ and $B$ with $\text{card } A = a$ and $\text{card } B = b$, and write $a^{b} = \text{card } A^{B}$. Alternatively, to define $a^{b}$ “multiply $a$ by itself $b$ times.” More precisely: form $\prod_{i \in I} a_{i}$, where the index set $I$ has cardinal number $b$, and where $a_{i} = a$ for each $i$ in $I$. The familiar laws of exponents hold. That is, if $a, b$, and $c$ are cardinal numbers, then

\[ \begin{aligned} a^{b+c} &= a^{b}a^{c}, \\ (ab)^{c} &= a^{c}b^{c}, \\ a^{bc} &= (a^{b})^{c}. \end{aligned} \]

Exercise 24.4 Prove that if $a, b$, and $c$ are cardinal numbers such that $a \le b$, then $a^{c} \le b^{c}$. Prove that if $a$ and $b$ are finite, greater than $1$, and if $c$ is infinite, then $a^{c} = b^{c}$.

The preceding definitions and their consequences are reasonably straight-forward and not at all surprising. If they are restricted to finite sets only, the result is the familiar finite arithmetic. The novelty of the subject arises in the formation of sums, products, and powers in which at least one term is infinite. The words “finite” and “infinite” are used here in a very natural sense: a cardinal number is finite if it is the cardinal number of a finite set, and infinite otherwise.

If $a$ and $b$ are cardinal numbers such that $a$ is finite and $b$ is infinite, then

\[ a + b = b. \]

For the proof, suppose that $A$ and $B$ are disjoint sets such that $A$ is equivalent to some natural number $k$ and $B$ is infinite; we are to prove that $A \cup B \sim B$. Since $\omega \precsim B$, we may and do assume that $\omega \subset B$. We define a mapping $f$ from $A \cup B$ to $B$ as follows: the restriction of $f$ to $A$ is a one-to-one correspondence between $A$ and $k$, the restriction of $f$ to $\omega$ given by $f(n) = n + k$ for all $n$, and the restriction of $f$ to $B - \omega$ is the identity mapping on $B - \omega$. Since the result is a one-to-one correspondence between $A \cup B$ and $B$, the proof is complete.

Next: if $a$ is an infinite cardinal number, then

\[ a + a = a. \]

For the proof, let $A$ be a set with $\text{card } A = a$. Since the set $A \times 2$ is the union of two disjoint sets equivalent to $A$ (namely, $A \times \{ 0 \}$ and $A \times \{ 1 \}$), it would be sufficient to prove that $A \times 2$ is equivalent to $A$. The approach we shall use will not quite prove that much, but it will come close enough. The idea is to approximate the construction of the desired one-to-one correspondence by using larger and larger subsets of $A$.

Precisely speaking, let $\mathcal{F}$ be the collection of all functions $f$ such that the domain of $f$ is of the form $X \times 2$, for some subset $X$ of $A$, and such that $f$ is a one-to-one correspondence between $X \times 2$ and $X$. If $X$ is a countably infinite subset of $A$, then $X \times 2 \sim X$. This implies that the collection $\mathcal{F}$ is not empty; at the very least it contains the one-to-one correspondences between $X \times 2$ and $X$ for the countably infinite subsets $X$ of $A$. The collection $\mathcal{F}$ is partially ordered by extension. Since a straightforward verification shows that the hypotheses of Zorn’s lemma are satisfied, it follows that $\mathcal{F}$ contains a maximal element $f$ with $\text{ran} f = X$, say.

Assertion: $A - X$ is finite. If $A - X$ were infinite, then it would include a countably infinite set, say $Y$. By combining $f$ with a one-to-one correspondence between $Y \times 2$ and $Y$ we could obtain a proper extension $f$, in contradiction to the assumed maximality.

Since $\text{card } X + \text{card } X = \text{card } X$, and since $\text{card } A = \text{card } X + \text{card } (A - X)$, the fact that $A - X$ is finite completes the proof that $\text{card } A + \text{card } A = \text{card } A$.

Here is one more result in additive cardinal arithmetic: if $a$ and $b$ are cardinal numbers at least one of which is infinite, and if $c$ is equal to the larger one of $a$ and $b$, then

\[ a + b = c. \]

Suppose that $b$ is infinite, and let $A$ and $B$ be disjoint sets with $\text{card } A = a$ and $\text{card } B = b$. Since $a \le c$ and $b \le c$, it follows that $a + b \le c + c$, and since $c \le \text{card } (A \cup B)$, it follows that $c \le a + b$. The result follows from the antisymmetry of the ordering of cardinal numbers.

The principal result in multiplicative cardinal arithmetic is that if $a$ is an infinite cardinal number, then

\[ a \cdot a = a. \]

The proof resembles the proof of the corresponding additive fact. Let $\mathcal{F}$ be the collection of all functions $f$ such that the domain of $f$ is of the form $X \times X$ for some subset $X$ of $A$, and such that $f$ is a one-to-one correspondence between $X \times X$ and $X$. If $X$ is a countably infinite subset of $A$, then $X \times X \sim X$ .This implies that the collection $\mathcal{F}$ is not empty; at the very least it contains the one-to-one correspondences between $X \times X$ and $X$ for the countably infinite subsets $X$ of $A$. The collection $\mathcal{F}$ is partially ordered by extension. The hypotheses of Zorn’s lemma are easily verified, and it follows that $\mathcal{F}$ contains a maximal element $f$ with $\text{ran } f = X$, say. Since $(\text{card } X)(\text{card } X) = \text{card } X$, the proof may be completed by showing that $\text{card } X = \text{card } A$.

Assume that $\text{card } X < \text{card } A$. Since $\text{card } A$ is equal to the larger one of $\text{card } X$ and $\text{card } (A - X)$, this implies that $\text{card } A = \text{card }(A - X)$, and hence that $\text{card } X < \text{card } ($A - X)$. From this it follows that $A - X$ has a subset $Y$ equivalent to $X$. Since each of the disjoint sets $X \times Y$, $Y \times X$, and $Y \times Y$ is infinite and equivalent to $X \times X$, hence to $X$, and hence to $Y$, it follows that their union is equivalent to $Y$. By combining $f$ with a one-to-one correspondence between that union and $Y$, we obtain a proper extension of $f$, in contradiction to the assumed maximality. This implies that our present hypothesis $(\text{card } X < \text{card } A)$ is untenable and hence completes the proof.

Exercise 24.5 Prove that if $a$ and $b$ are cardinal numbers at least one of which is infinite, then $a + b = ab$. Prove that if $a$ and $b$ are cardinal numbers such that $a$ is infinite and $b$ is finite, then $a^{b} = a$.