Cardinal Numbers

Home → Cardinal Numbers

Definitions

In this section we consider another type of numbers, called cardinal numbers, which can also be seen as an extension of the natural numbers. Cardinal numbers are used to measure the cardinality of sets.

The cardinality or cardinal number of a finite set \(A\) is equal to the number of elements in the set: \(\left| A \right| = n.\) So finite cardinals are defined as natural numbers \(n \in \mathbb{N}.\) The cardinal number of the empty set is supposed to be equal to zero: \({\left| \varnothing \right| = 0.}\)

To apply the concept of cardinality to both finite and infinite sets, it is defined in terms of functional mapping. Two infinite sets \(A\) and \(B\) have the same cardinality if there is a bijection \(A \to B.\) Sets with the same cardinality are called equinumerous and denoted as \(A \sim B.\) Hence,

\[A \sim B\; \text{ iff }\;\left| A \right| = \left| B \right|.\]

The relation of "being equinumerous" is an equivalence relation. The equivalence class of a set \(A\) under this relation contains all sets which have the same cardinality as \(A.\)

A cardinal number can be defined as a class of all equinumerous sets. This definition, however, contradicts axiomatic set theories (ZF, ZFC, and others), since equivalence classes do not form a set.

Another approach known as the von Neumann cardinal assignment works in both naive and axiomatic set theory. This definition uses ordinal numbers. The cardinal number of a well-ordered set \(A\) is defined to be the least ordinal number equinumerous to \(A.\) Recall that, according to the axiom of choice, any set can be well-ordered. Therefore, assuming the axiom of choice, any set has a cardinal number.

More formally, an ordinal \(\alpha\) is called a cardinal number if

\[\left| \alpha \right| \ne \left| \beta \right| \text{ for all } \beta \lt \alpha.\]

By this definition, all natural numbers are cardinals. The ordinal \(\omega\) is the least infinite cardinal number. However, the successor of \(\omega,\) the ordinal \(\omega + 1,\) is not a cardinal (because there is a bijection between \(\omega\) and \(\omega + 1\)). A theorem in set theory states that every infinite cardinal is always a limit ordinal.

Alephs

Aleph \(\aleph\) is the first letter of the Hebrew alphabet. Cantor proposed to use alephs to denote the cardinal numbers of infinite sets.

The cardinal number of the set \(\mathbb{N}\) is the least infinite cardinal. It is denoted by \(\aleph_0.\) Hence,

\[\omega = \left| \mathbb{N} \right| = \aleph_0.\]

All other countably infinite sets, such as \(\mathbb{Z}\) and \(\mathbb{Q},\) are described by the same cardinal number \(\aleph_0.\)

The cardinality of the set of real numbers \(\mathbb{R}\) is denoted by \(\mathfrak{c}.\) According to the continuum hypothesis,

\[\mathfrak{c} = {2^{\left| \mathbb{N} \right|}} = {2^{{\aleph_0}}} = {\aleph_1},\]

which means that there is no set with an intermediate cardinality lying between \(\aleph_0\) and \(\mathfrak{c},\) so the number \(\mathfrak{c} = \aleph_1\) is the successor of \(\aleph_0.\)

The cardinal number \(\aleph_{\alpha+1}\) is the smallest cardinal number that follows \(\aleph_{\alpha}.\)

Thus, finite and infinite cardinal numbers form the following sequence:

\[0,1,2, \ldots ,n, \ldots {\aleph_0},{\aleph_1},{\aleph_2}, \ldots \]

Cardinal Arithmetic

For cardinals, we can define the operations of addition, multiplication, and exponentiation. The axiom of choice is assumed to be true.

Cardinal Addition

Let \(A\) and \(B\) be any two disjoint sets. If the sets are not disjoint, we can replace them by disjoint sets with the same cardinality:

\[A \to A \times \left\{ 0 \right\},\;\;B \to B \times \left\{ 1 \right\}.\]

Let \(\mathfrak{a}\) and \(\mathfrak{b}\) be cardinal numbers of the sets \(A\) and \(B:\)

\[\mathfrak{a} = \left| A \right|,\;\;\mathfrak{b} = \left| B \right|.\]

The addition of \(\mathfrak{a}\) and \(\mathfrak{b}\) is defined in terms of the union of sets \(A\) and \(B:\)

\[\mathfrak{a} + \mathfrak{b} = \left| A \right| + \left| B \right| = \left| {A \cup B} \right|,\]

assuming \(\left| {A \cap B} \right| = \varnothing.\)

If either \(\mathfrak{a}\) or \(\mathfrak{b}\) is infinite, then the sum rule is given by

\[\mathfrak{a} + \mathfrak{b} = \max \left\{ {\mathfrak{a},\mathfrak{b}} \right\}.\]

Examples

\[\left| {\left\{ {a,b,c} \right\}} \right| + \left| {\left\{ {1,2,3} \right\}} \right| = 3 + 3 = 6 = \left| {\left\{ {a,b,c,1,2,3} \right\}} \right|\]

\[{\aleph_0} + {\aleph_0} = \max \left\{ {{\aleph_0},{\aleph_0}} \right\} = {\aleph_0}\]

\[{\aleph_0} + \mathfrak{c} = \max \left\{ {{\aleph_0},\mathfrak{c}} \right\} = \mathfrak{c} = {\aleph_1}\]

Cardinal addition is commutative and associative:

\(\mathfrak{a} + \mathfrak{b} = \mathfrak{b} + \mathfrak{a}\)
\(\left( {\mathfrak{a} + \mathfrak{b}} \right) + \mathfrak{d} = \mathfrak{a} + \left( {\mathfrak{b} + \mathfrak{d}} \right)\)

The addition operation also obeys the following properties:

\(\mathfrak{a} + 0 = 0 + \mathfrak{a} = \mathfrak{a}\)
If \({\mathfrak{a}_1},{\mathfrak{a}_2},{\mathfrak{b}_1},{\mathfrak{b}_2}\) are cardinal numbers such that \({\mathfrak{a}_1} \le {\mathfrak{a}_2}\) and \({\mathfrak{b}_1} \le {\mathfrak{b}_2},\) then \({\mathfrak{a}_1} + {\mathfrak{b}_1} \le {\mathfrak{a}_2} + {\mathfrak{b}_2}.\)

We could also consider cardinal subtraction, but this operation is not uniquely defined for infinite cardinal numbers. Indeed, when \(\mathfrak{a}\) is infinite and \(\mathfrak{a} \ge \mathfrak{b}\), then

\[\mathfrak{a} + \mathfrak{b} = \max \left\{ {\mathfrak{a},\mathfrak{b}} \right\} = \mathfrak{a}.\]

In this case, the number \(\mathfrak{b}\) can take any value from \(0\) to \(\mathfrak{a},\) that is, the subtraction operation \(\mathfrak{b} = \mathfrak{a} - \mathfrak{a}\) is not defined.

Cardinal Multiplication

Let \(A\) and \(B\) be two arbitrary sets with cardinal numbers \(\mathfrak{a}\) and \(\mathfrak{b},\) respectively. The product of cardinals \(\mathfrak{a}\) and \(\mathfrak{b},\) is defined in terms of the Cartesian product of sets \(A\) and \(B:\)

\[\mathfrak{a} \cdot \mathfrak{b} = \left| A \right| \cdot \left| B \right| = \left| {A \times B} \right|.\]

Similarly to addition, if either \(\mathfrak{a}\) or \(\mathfrak{b}\) is infinite and both are not equal to zero, then the product rule is given by

\[\mathfrak{a} \cdot \mathfrak{b} = \max \left\{ {\mathfrak{a},\mathfrak{b}} \right\}.\]

Examples

\[\left| {{{\left\{ {a,b} \right\}}^2}} \right| = {\left| {\left\{ {a,b} \right\}} \right|^2} = {2^2} = 4 = \left| {\left\{ {\left( {a,a} \right),\left( {a,b} \right),\left( {b,a} \right),\left( {b,b} \right)} \right\}} \right|.\]

\[{\aleph_0} \cdot {\aleph_0} = \max \left\{ {{\aleph_0},{\aleph_0}} \right\} = {\aleph_0}\]

\[{\aleph_0} \cdot \mathfrak{c} = \max \left\{ {{\aleph_0},\mathfrak{c}} \right\} = \mathfrak{c} = {\aleph_1}\]

Like addition, cardinal multiplication is commutative and associative:

\(\mathfrak{a} \cdot \mathfrak{b} = \mathfrak{b} \cdot \mathfrak{a}\)
\(\left( {\mathfrak{a} \cdot \mathfrak{b}} \right) \cdot \mathfrak{d} = \mathfrak{a} \cdot \left( {\mathfrak{b} \cdot \mathfrak{d}} \right)\)

Some other properties of cardinal multiplication:

\(\mathfrak{a} \cdot 1 = \mathfrak{a}\)
\(\mathfrak{a} \cdot \left( {\mathfrak{b} + \mathfrak{d}} \right) = \mathfrak{a} \cdot \mathfrak{b} + \mathfrak{a} \cdot \mathfrak{d}\)
\(\left( {\mathfrak{a} + \mathfrak{b}} \right) \cdot \mathfrak{d} = \mathfrak{a} \cdot \mathfrak{d} + \mathfrak{b} \cdot \mathfrak{d}\)
If \({\mathfrak{a}_1},{\mathfrak{a}_2},{\mathfrak{b}_1},{\mathfrak{b}_2}\) are cardinal numbers such that \({\mathfrak{a}_1} \le {\mathfrak{a}_2}\) and \({\mathfrak{b}_1} \le {\mathfrak{b}_2},\) then \({\mathfrak{a}_1} \cdot {\mathfrak{b}_1} \le {\mathfrak{a}_2} \cdot {\mathfrak{b}_2}.\)

The division operation is not defined for all infinite cardinals. Consider the expression \(\mathfrak{a} \cdot \mathfrak{b} = \mathfrak{d}.\) If \(\mathfrak{d}\) is infinite, then the number \(\mathfrak{a}\) is uniquely defined if only \(\mathfrak{b} \lt \mathfrak{d}.\) In this case, \(\mathfrak{a} = \mathfrak{d}.\)

Cardinal Exponentiation

If two sets \(A\) and \(B\) have cardinalities \(\mathfrak{a}\) and \(\mathfrak{b},\) then the exponentiation operation is given by

\[{\mathfrak{a}^\mathfrak{b}} = \left| {{A^B}} \right| = {\left| A \right|^{\left| B \right|}},\]

where

\[{A^B} = \underbrace {A \times A \times \cdots \times A}_{B\;\text{times}} = \prod\limits_B A \]

is the set of all functions from \(B\) to \(A.\)

Examples

\[\left| {{{\left\{ {a,b,c} \right\}}^{\left\{ {1,2} \right\}}}} \right| = {\left| {\left\{ {a,b,c} \right\}} \right|^{\left| {\left\{ {1,2} \right\}} \right|}} = {3^2} = 9.\]

\[\aleph_0^5 = \underbrace {{\aleph_0} \cdot {\aleph_0} \cdots {\aleph_0}}_{5\;\text{times}} = \max \left( {{\aleph_0}, {\aleph_0},\ldots, {\aleph_0}} \right) = {\aleph_0}.\]

The exponentiation operation satisfies the following properties:

\(0^\mathfrak{b} = 0, \text{ for } \mathfrak{b} \gt 0.\)
\(1^\mathfrak{b} = 1\)
\(\mathfrak{a}^0 = 1\)
\(\mathfrak{a}^1 = \mathfrak{a}\)
\({\mathfrak{a}^{\mathfrak{b} + \mathfrak{d}}} = {\mathfrak{a}^\mathfrak{b}} \cdot {\mathfrak{a}^\mathfrak{d}}\)
\({\left( {{\mathfrak{a}^\mathfrak{b}}} \right)^\mathfrak{d}} = {\mathfrak{a}^{\mathfrak{b} \cdot \mathfrak{d}}}\)
\({\left( {\mathfrak{a} \cdot \mathfrak{b}} \right)^\mathfrak{d}} = {\mathfrak{a}^\mathfrak{d}} \cdot {\mathfrak{b}^\mathfrak{d}}\)
If \({\mathfrak{a}_1},{\mathfrak{a}_2},{\mathfrak{b}_1},{\mathfrak{b}_2}\) are cardinal numbers such that \({\mathfrak{a}_1} \le {\mathfrak{a}_2}\) and \({\mathfrak{b}_1} \le {\mathfrak{b}_2},\) then \({\mathfrak{a}_1}^{\mathfrak{b}_1} \le {\mathfrak{a}_2}^{\mathfrak{b}_2}.\)

There are two inverse operations for exponentiation - extracting the root and taking the logarithm. However, these operations are not well-defined for cardinal numbers. Below, we give some special cases.

Let \({\mathfrak{a}^\mathfrak{b}} = \mathfrak{d}.\) If \(\mathfrak{d}\) is infinite and the exponent \(\mathfrak{b}\) is finite and not equal to zero, then \(\mathfrak{a} = \mathfrak{d}.\)

The logarithm of an infinite cardinal \(\mathfrak{a}\) is defined as the least cardinal number \(\mathfrak{b}\) such that \(\mathfrak{a} \le 2^{\mathfrak{b}}.\)