7.4 Arithmetic of Cardinals

Cardinal arithmetic studies how the sizes of sets behave under natural set theoretic operations. Addition corresponds to disjoint union, multiplication corresponds to Cartesian product, and exponentiation corresponds to sets of functions. For finite sets these operations agree with ordinary arithmetic, but for infinite sets they have behavior that is at first surprising and later becomes one of the central tools of set theory.

Cardinal Numbers

A cardinal number is a measure of the size of a set. Two sets have the same cardinality when there exists a bijection between them. In informal notation, the cardinality of a set $A$ is written:

|A|

Thus:

|A|=|B|

means that there exists a bijection:

f:A\to B

The notation does not require that $A$ and $B$ have the same elements. It only requires that their elements can be paired exactly, with no element omitted and no element repeated.

For example:

|\mathbb{N}|=|\{0,2,4,6,\dots\}|

because the map:

n\mapsto 2n

is a bijection from $\mathbb{N}$ to the set of even natural numbers.

Definition 7.72 (Cardinal Addition)

Let $A$ and $B$ be sets. To define the sum of their cardinalities, first replace them by disjoint copies:

A\times\{0\}

and:

B\times\{1\}

The cardinal sum is defined by:

|A|+|B|=|(A\times\{0\})\cup(B\times\{1\})|

The use of disjoint copies is important because $A$ and $B$ may overlap. Cardinal addition counts the elements of $A$ and the elements of $B$ as separate contributions, even if the original sets have common elements.

When $A$ and $B$ are already disjoint, this agrees with:

|A|+|B|=|A\cup B|

Example 7.73

Let:

A=\{a,b\}

and:

B=\{b,c,d\}

The ordinary union is:

A\cup B=\{a,b,c,d\}

which has $4$ elements. But cardinal addition should count $A$ and $B$ separately, so:

|A|+|B|=2+3=5

Using disjoint copies gives:

(A\times\{0\})\cup(B\times\{1\}) = \{(a,0),(b,0),(b,1),(c,1),(d,1)\}

This set has $5$ elements, as desired.

Definition 7.74 (Cardinal Multiplication)

Let $A$ and $B$ be sets. The product of their cardinalities is defined by:

|A|\cdot |B|=|A\times B|

Thus cardinal multiplication measures the size of the Cartesian product.

An element of $A\times B$ is an ordered pair:

(a,b)

where:

a\in A

and:

b\in B

Example 7.75

Let:

A=\{1,2\}

and:

B=\{x,y,z\}

Then:

A\times B = \{(1,x),(1,y),(1,z),(2,x),(2,y),(2,z)\}

Thus:

|A\times B|=6

and:

|A|\cdot |B|=2\cdot 3=6

Definition 7.76 (Cardinal Exponentiation)

Let $A$ and $B$ be sets. The cardinal exponent:

|B|^{|A|}

is defined as the cardinality of the set of all functions from $A$ to $B$ :

|B|^{|A|}=|B^A|

where:

B^A=\{f:f:A\to B\}

The notation is chosen because, when $A$ and $B$ are finite, the number of functions from $A$ to $B$ is:

|B|^{|A|}

For each element of $A$ , one must choose one output in $B$ , and these choices are independent.

Example 7.77

Let:

A=\{1,2,3\}

and:

B=\{0,1\}

A function:

f:A\to B

chooses either $0$ or $1$ for each of the three elements of $A$ . Therefore there are:

2^3=8

such functions.

Thus:

|B^A|=8

Lemma 7.78 (Well Definedness of Cardinal Addition)

If:

|A|=|A'|

and:

|B|=|B'|

then:

|A|+|B|=|A'|+|B'|

Proof

Assume:

|A|=|A'|

and:

|B|=|B'|

Then there exist bijections:

f:A\to A'

and:

g:B\to B'

Define:

h:(A\times\{0\})\cup(B\times\{1\})\to(A'\times\{0\})\cup(B'\times\{1\})

by:

h(a,0)=(f(a),0)

and:

h(b,1)=(g(b),1)

This function is well defined because the two parts of the domain are disjoint. It is injective because $f$ and $g$ are injective, and because elements tagged with $0$ cannot map to elements tagged with $1$ . It is surjective because $f$ and $g$ are surjective. Hence $h$ is a bijection, and therefore:

|A|+|B|=|A'|+|B'|

Lemma 7.79 (Well Definedness of Cardinal Multiplication)

If:

|A|=|A'|

and:

|B|=|B'|

then:

|A|\cdot |B|=|A'|\cdot |B'|

Proof

Let:

f:A\to A'

and:

g:B\to B'

be bijections. Define:

h:A\times B\to A'\times B'

by:

h(a,b)=(f(a),g(b))

If:

h(a,b)=h(a_1,b_1)

then:

(f(a),g(b))=(f(a_1),g(b_1))

so:

f(a)=f(a_1)

and:

g(b)=g(b_1)

Since $f$ and $g$ are injective:

a=a_1

and:

b=b_1

Thus $h$ is injective.

To prove surjectivity, let:

(a',b')\in A'\times B'

Since $f$ and $g$ are surjective, there exist:

a\in A

and:

b\in B

such that:

f(a)=a'

and:

g(b)=b'

Then:

h(a,b)=(a',b')

Therefore $h$ is bijective, and:

|A\times B|=|A'\times B'|

Lemma 7.80 (Well Definedness of Cardinal Exponentiation)

If:

|A|=|A'|

and:

|B|=|B'|

then:

|B|^{|A|}=|B'|^{|A'|}

Proof

Let:

u:A'\to A

and:

v:B\to B'

be bijections. We construct a bijection:

\Phi:B^A\to (B')^{A'}

For a function:

f:A\to B

define:

\Phi(f):A'\to B'

by:

\Phi(f)(a')=v(f(u(a')))

This means that an input $a'\in A'$ is first moved to $A$ by $u$ , then evaluated by $f$ , and then moved to $B'$ by $v$ .

Since $u$ and $v$ are bijections, this construction is reversible. The inverse sends a function:

F:A'\to B'

to the function:

A\to B

defined by:

a\mapsto v^{-1}(F(u^{-1}(a)))

Thus $\Phi$ is a bijection, so the cardinality of the function set depends only on the cardinalities of the domain and codomain.

Basic Laws of Cardinal Addition

Cardinal addition satisfies the familiar commutative and associative laws.

Lemma 7.81 (Commutativity of Cardinal Addition)

For all sets $A$ and $B$ :

|A|+|B|=|B|+|A|

Proof

By definition:

|A|+|B|=|(A\times\{0\})\cup(B\times\{1\})|

and:

|B|+|A|=|(B\times\{0\})\cup(A\times\{1\})|

Define a function from the first disjoint union to the second by:

(a,0)\mapsto(a,1)

for $a\in A$ , and:

(b,1)\mapsto(b,0)

for $b\in B$ .

This map simply switches the tags. It is clearly injective and surjective, so it is a bijection. Therefore:

|A|+|B|=|B|+|A|

Lemma 7.82 (Associativity of Cardinal Addition)

For all sets $A$ , $B$ , and $C$ :

(|A|+|B|)+|C|=|A|+(|B|+|C|)

Proof

Both sides count the size of a disjoint union of three copies:

A,\quad B,\quad C

More explicitly, both sides are represented by a set in bijection with:

(A\times\{0\})\cup(B\times\{1\})\cup(C\times\{2\})

The difference between the two expressions is only the placement of parentheses in the construction, not the final tagged collection of elements. The evident reassociation map is a bijection, so the cardinalities are equal.

Basic Laws of Cardinal Multiplication

Cardinal multiplication also satisfies familiar commutative and associative laws.

Lemma 7.83 (Commutativity of Cardinal Multiplication)

For all sets $A$ and $B$ :

|A|\cdot |B|=|B|\cdot |A|

Proof

By definition:

|A|\cdot |B|=|A\times B|

and:

|B|\cdot |A|=|B\times A|

The map:

A\times B\to B\times A

defined by:

(a,b)\mapsto(b,a)

is a bijection. Its inverse is itself. Therefore:

|A\times B|=|B\times A|

and hence:

|A|\cdot |B|=|B|\cdot |A|

Lemma 7.84 (Associativity of Cardinal Multiplication)

For all sets $A$ , $B$ , and $C$ :

(|A|\cdot |B|)\cdot |C|=|A|\cdot(|B|\cdot |C|)

Proof

The left side is represented by:

(A\times B)\times C

and the right side is represented by:

A\times(B\times C)

Define:

((a,b),c)\mapsto(a,(b,c))

This map is a bijection, with inverse:

(a,(b,c))\mapsto((a,b),c)

Therefore the two Cartesian products have the same cardinality.

Lemma 7.85 (Distributive Law)

For all sets $A$ , $B$ , and $C$ :

|A|\cdot(|B|+|C|)=|A|\cdot|B|+|A|\cdot|C|

Proof

The left side is represented by:

A\times((B\times\{0\})\cup(C\times\{1\}))

An element of this set is either of the form:

(a,(b,0))

with $a\in A$ and $b\in B$ , or of the form:

(a,(c,1))

with $a\in A$ and $c\in C$ .

The right side is represented by the disjoint union:

(A\times B)\times\{0\} \cup (A\times C)\times\{1\}

Define a map by:

(a,(b,0))\mapsto((a,b),0)

and:

(a,(c,1))\mapsto((a,c),1)

This map is a bijection, and therefore the cardinalities are equal.

Zero and One

The cardinal $0$ is the cardinality of the empty set:

0=|\varnothing|

The cardinal $1$ is the cardinality of any singleton:

1=|\{*\}|

These cardinals behave as expected.

Lemma 7.86 (Zero and One Laws)

For every set $A$ :

|A|+0=|A|

|A|\cdot 0=0

|A|\cdot 1=|A|

Proof

For addition, the disjoint union of $A$ with an empty set is naturally in bijection with $A$ , so:

|A|+0=|A|

For multiplication by $0$ , we have:

A\times\varnothing=\varnothing

because there is no ordered pair whose second coordinate lies in the empty set. Hence:

|A|\cdot 0=0

For multiplication by $1$ , let $\{*\}$ be a singleton. The map:

A\times\{*\}\to A

defined by:

(a,*)\mapsto a

is a bijection. Hence:

|A|\cdot 1=|A|

Cardinal Exponent Laws

Cardinal exponentiation satisfies laws corresponding to the usual laws of exponents, because functions into products and functions out of disjoint unions can be described componentwise.

Lemma 7.87 (Product in the Base)

For all sets $A$ , $B$ , and $C$ :

(|B|\cdot |C|)^{|A|}=|B|^{|A|}\cdot |C|^{|A|}

Proof

The left side is the cardinality of:

(B\times C)^A

whose elements are functions:

f:A\to B\times C

Each such function is equivalent to a pair of functions:

f_B:A\to B

and:

f_C:A\to C

defined by:

f_B(a)=\pi_1(f(a))

and:

f_C(a)=\pi_2(f(a))

Conversely, any pair of functions:

g:A\to B

and:

h:A\to C

defines a function:

a\mapsto(g(a),h(a))

from $A$ to $B\times C$ .

These constructions are inverse to each other, so:

(B\times C)^A

is in bijection with:

B^A\times C^A

Therefore:

(|B|\cdot |C|)^{|A|}=|B|^{|A|}\cdot |C|^{|A|}

Lemma 7.88 (Sum in the Exponent)

For all sets $A$ , $B$ , and $C$ :

|C|^{|A|+|B|}=|C|^{|A|}\cdot |C|^{|B|}

Proof

The left side is represented by functions:

(A\times\{0\})\cup(B\times\{1\})\to C

A function on this disjoint union is the same thing as a pair of functions:

A\to C

and:

B\to C

The first function is obtained by restricting to $A\times\{0\}$ , and the second is obtained by restricting to $B\times\{1\}$ . Conversely, any two such functions combine uniquely into one function on the disjoint union.

Thus:

C^{(A\times\{0\})\cup(B\times\{1\})}

is in bijection with:

C^A\times C^B

and therefore:

|C|^{|A|+|B|}=|C|^{|A|}\cdot |C|^{|B|}

Lemma 7.89 (Product in the Exponent)

For all sets $A$ , $B$ , and $C$ :

(|C|^{|B|})^{|A|}=|C|^{|A|\cdot |B|}

Proof

The left side is represented by functions:

A\to C^B

Such a function assigns to each $a\in A$ a function:

B\to C

Equivalently, it assigns to each pair $(a,b)\in A\times B$ an element of $C$ . Thus it is the same thing as a function:

A\times B\to C

The bijection is given by:

F\mapsto \widehat{F}

where:

\widehat{F}(a,b)=F(a)(b)

Conversely, a function:

h:A\times B\to C

defines:

F_h:A\to C^B

by:

F_h(a)(b)=h(a,b)

These constructions are inverse to each other. Hence:

(C^B)^A

is in bijection with:

C^{A\times B}

and the cardinal identity follows.

Finite Cardinal Arithmetic

For finite sets, cardinal arithmetic agrees with ordinary arithmetic on natural numbers.

Lemma 7.90 (Finite Addition and Multiplication)

If:

|A|=m

and:

|B|=n

where $m,n\in\mathbb{N}$ , then:

|A|+|B|=m+n

and:

|A|\cdot|B|=mn

Proof

Since:

|A|=m

there is a bijection:

[m]\to A

and since:

|B|=n

there is a bijection:

[n]\to B

By well definedness of cardinal addition and multiplication, it is enough to compute the cardinalities using $[m]$ and $[n]$ .

The disjoint union of $[m]$ and $[n]$ has $m+n$ elements, and the product:

[m]\times[n]

has $mn$ elements. Therefore the corresponding cardinal sum and product agree with ordinary finite arithmetic.

Infinite Cardinal Arithmetic

Infinite cardinals behave differently from finite cardinals. The first important fact is that adding or multiplying a countably infinite set by itself does not increase its cardinality.

Lemma 7.91

The following cardinal equalities hold:

|\mathbb{N}|+|\mathbb{N}|=|\mathbb{N}|

and:

|\mathbb{N}|\cdot|\mathbb{N}|=|\mathbb{N}|

Proof

For addition, the disjoint union:

(\mathbb{N}\times\{0\})\cup(\mathbb{N}\times\{1\})

is in bijection with $\mathbb{N}$ by the map:

(n,0)\mapsto 2n

and:

(n,1)\mapsto 2n+1

This lists the first copy of $\mathbb{N}$ using even numbers and the second copy using odd numbers.

For multiplication, the set:

\mathbb{N}\times\mathbb{N}

is countable, as proved by listing pairs by increasing value of the sum of their coordinates:

m+n

Since there is also an injection:

\mathbb{N}\to\mathbb{N}\times\mathbb{N}

given by:

n\mapsto(n,0)

we obtain:

|\mathbb{N}\times\mathbb{N}|=|\mathbb{N}|

Thus:

|\mathbb{N}|\cdot|\mathbb{N}|=|\mathbb{N}|

Countable Sums

A countable sum of countable sets is countable. This is the cardinal arithmetic form of the countable union theorem.

Lemma 7.92

Let:

A_0,A_1,A_2,\dots

be countable sets. Then:

\left|\bigcup_{n\in\mathbb{N}}(A_n\times\{n\})\right| \leq |\mathbb{N}|

provided each $A_n$ is countable.

Proof

Since each $A_n$ is countable, for each $n$ there exists a surjection:

f_n:\mathbb{N}\to A_n

Define:

F:\mathbb{N}\times\mathbb{N}\to \bigcup_{n\in\mathbb{N}}(A_n\times\{n\})

by:

F(n,m)=(f_n(m),n)

This map is surjective because every element of the tagged union has the form:

(a,n)

with:

a\in A_n

and since $f_n$ is surjective, there exists $m$ such that:

f_n(m)=a

Therefore:

F(n,m)=(a,n)

Since $\mathbb{N}\times\mathbb{N}$ is countable, the tagged union is countable.

Cardinal Exponentiation and Power Sets

The most important exponentiation identity connects power sets with functions into a two element set.

Lemma 7.93 (Power Set as a Function Set)

For every set $A$ :

|\mathcal{P}(A)|=2^{|A|}

where:

2=|\{0,1\}|

Proof

We construct a bijection between:

\mathcal{P}(A)

and:

\{0,1\}^A

Given a subset:

X\subseteq A

define its characteristic function:

\chi_X:A\to\{0,1\}

by:

\chi_X(a)= \begin{cases} 1 & \text{if } a\in X \\ 0 & \text{if } a\notin X \end{cases}

This assigns to each subset a function.

Conversely, given a function:

f:A\to\{0,1\}

define a subset:

X_f=\{a\in A:f(a)=1\}

These two constructions are inverse to each other. Starting from a subset $X$ , forming $\chi_X$ , and then taking the elements mapped to $1$ returns $X$ . Starting from a function $f$ , forming $X_f$ , and then taking its characteristic function returns $f$ .

Therefore:

\mathcal{P}(A)

is in bijection with:

\{0,1\}^A

and so:

|\mathcal{P}(A)|=2^{|A|}

Theorem 7.94 (Cantor Theorem in Cardinal Form)

For every set $A$ :

|A|<|\mathcal{P}(A)|

Equivalently:

|A|<2^{|A|}

Proof

There is an injection:

A\to\mathcal{P}(A)

given by:

a\mapsto\{a\}

so:

|A|\leq|\mathcal{P}(A)|

It remains to show that there is no bijection from $A$ to $\mathcal{P}(A)$ . In fact, there is no surjection:

f:A\to\mathcal{P}(A)

Suppose, for contradiction, that such a surjection exists. Define:

D=\{a\in A:a\notin f(a)\}

Then:

D\subseteq A

so:

D\in\mathcal{P}(A)

Since $f$ is surjective, there exists $d\in A$ such that:

f(d)=D

Now:

d\in D

if and only if:

d\notin f(d)

Since:

f(d)=D

this becomes:

d\in D \quad \text{if and only if} \quad d\notin D

This is impossible. Hence no surjection $A\to\mathcal{P}(A)$ exists, and therefore:

|A|<|\mathcal{P}(A)|

The Continuum

The cardinality of the real numbers is called the cardinality of the continuum. It is commonly denoted:

\mathfrak{c}

One has:

\mathfrak{c}=|\mathbb{R}|

A fundamental fact is:

|\mathbb{R}|=|\mathcal{P}(\mathbb{N})|

and hence:

\mathfrak{c}=2^{|\mathbb{N}|}

Lemma 7.95

The set of all infinite binary sequences has cardinality:

2^{|\mathbb{N}|}

Proof

An infinite binary sequence is a function:

s:\mathbb{N}\to\{0,1\}

Therefore the set of all infinite binary sequences is:

\{0,1\}^{\mathbb{N}}

By definition of cardinal exponentiation, its cardinality is:

2^{|\mathbb{N}|}

By Lemma 7.93, this is also:

|\mathcal{P}(\mathbb{N})|

because each binary sequence is the characteristic function of a subset of $\mathbb{N}$ .

Cardinal Arithmetic for Infinite Cardinals

For infinite cardinals, addition and multiplication often collapse. The exact theorem requires the axiom of choice in full generality, but the countable examples already show the main pattern.

Theorem 7.96 (Basic Infinite Cardinal Arithmetic, With Choice)

Let $\kappa$ be an infinite cardinal. Then:

\kappa+\kappa=\kappa

and:

\kappa\cdot\kappa=\kappa

More generally, if $\kappa$ and $\lambda$ are cardinals with at least one infinite and both nonzero, then:

\kappa+\lambda=\kappa\cdot\lambda=\max(\kappa,\lambda)

assuming the cardinals are comparable.

Proof

We give the idea. The theorem rests on the fact that an infinite set can be put in bijection with two disjoint copies of itself and also with its square, provided the usual comparison principles for cardinals are available.

For $\mathbb{N}$ , this was proved explicitly by even and odd coding for addition and by listing pairs for multiplication.

For a general infinite cardinal $\kappa$ , one uses a well ordering of a set of size $\kappa$ and constructs injections both ways between the relevant disjoint unions or products and the original set. The Cantor Schroeder Bernstein theorem then gives the required bijections.

The full proof depends on the general theory of well orderings and cardinal comparison, which uses the axiom of choice in its standard form.

Strict Growth by Exponentiation

Although addition and multiplication may collapse for infinite cardinals, exponentiation does not collapse in the same way. Cantor theorem shows that the power set operation always produces a strictly larger cardinal.

For every cardinal $\kappa$ :

\kappa<2^\kappa

This gives an infinite hierarchy:

|\mathbb{N}|<2^{|\mathbb{N}|}<2^{2^{|\mathbb{N}|}}<2^{2^{2^{|\mathbb{N}|}}}<\cdots

Each step is strictly larger than the previous one.

Example 7.97

Let:

\aleph_0=|\mathbb{N}|

Then:

\aleph_0+\aleph_0=\aleph_0

and:

\aleph_0\cdot\aleph_0=\aleph_0

but:

2^{\aleph_0}>\aleph_0

The cardinal:

2^{\aleph_0}

is the cardinality of:

\mathcal{P}(\mathbb{N})

and also the cardinality of:

\mathbb{R}

Thus countable infinity is stable under addition and multiplication by itself, but the set of all subsets of a countable set is uncountable.