Cardinality

The cardinality of a set is a measure of a set's size, meaning the number of elements in the set. For instance, the set \(A = \{1,2,4\} \) has a cardinality of \(3\) for the three elements that are in it. The cardinality of a set is denoted by vertical bars, like absolute value signs; for instance, for a set \(A\) its cardinality is denoted \(|A|\). When \(A\) is finite, \(|A|\) is simply the number of elements in \(A\). When \(A\) is infinite, \(|A|\) is represented by a cardinal number.

Two finite sets are considered to be of the same size if they have equal numbers of elements. To formulate this notion of size without reference to the natural numbers, one might declare two finite sets \(A\) and \(B\) to have the same cardinality if and only if there exists a bijection \(A \to B \). For finite sets, these two definitions are equivalent. A bijection will exist between \(A\) and \(B\) only when elements of \(A\) can be paired in one-to-one correspondence with elements of \(B\), which necessarily requires \(A\) and \(B\) have the same number of elements.

There is nothing preventing one from making a similar definition for infinite sets:

Two sets \(A\) and \(B\) are said to have the same cardinality if there exists a bijection \(A \to B\).

This seemingly straightforward definition creates some initially counterintuitive results. For example, note that there is a simple bijection from the set of all integers to the set of even integers, via doubling each integer. More formally, this is the bijection \(f:\{\text{integers}\}\rightarrow \{\text{even integers}\}\) where \(f(n) = 2n.\) This means that, in terms of cardinality, the size of the set of all integers is exactly the same as the size of the set of even integers.

Let \(\mathbb{N} = \{1, 2, 3, \cdots\}\) denote the set of natural numbers.

An infinite set \(A\) is called countably infinite (or countable) if it has the same cardinality as \(\mathbb{N}\). In other words, there is a bijection \(A \to \mathbb{N}\).

An infinite set \(A\) is called uncountably infinite (or uncountable) if it is not countable. In other words, there exists no bijection \(A \to \mathbb{N}\).

These definitions suggest that even among the class of infinite sets, there are different "sizes of infinity." In the sense of cardinality, countably infinite sets are "smaller" than uncountably infinite sets. Of course, finite sets are "smaller" than any infinite sets, but the distinction between countable and uncountable gives a way of comparing sizes of infinite sets as well. Below are some examples of countable and uncountable sets.

Let \(\mathbb{Z} = \{\ldots, -2, -1, 0, 1, 2, \ldots\}\) denote the set of integers. Is \(\mathbb{Z}\) countable or uncountable?

---

Consider the following map from \(\mathbb{N} \to \mathbb{Z}:\)

\[\{1, 2, 3, 4, 5, 6, 7, 8,9, \ldots\} \mapsto \{0,1,-1,2,-2,3,-3,4,-4,\ldots\}.\]

Each integer is mapped to by some natural number, and no integer is mapped to twice. Thus, this is a bijection. We conclude \(\mathbb{Z}\) is countable. \(_\square\)

Let \(\mathbb{Q} \) denote the set of rational numbers. Is \(\mathbb{Q}\) countable or uncountable?

---

A map from \(\mathbb{N} \to \mathbb{Q}\) can be described simply by a list of rational numbers. If this list contains each rational number at least once, we can remove repeats to obtain a bijection \(\mathbb{N} \to \mathbb{Q}\).

For a rational number \(\frac ab\) (in lowest terms), call \(|a| + |b|\) its height. There are finitely many rational numbers of each height. Hence, if we list all the rationals of height 1, then the rationals of height 2, then the rationals of height 3, etc., we will obtain the desired list of rationals.

Thus, we conclude \(\mathbb{Q}\) is countable. \(_\square\)

Consider the interval \([0,1]\). As a set, is \([0,1]\) countable or uncountable?

---

By Cantor's famous diagonal argument, it turns out \([0,1]\) is uncountable. His argument is a clever proof by contradiction.

Suppose \([0,1]\) is countable, so that we may write \([0,1] = \{a_1, a_2, a_3, \ldots\}\), where each \(a_i \in [0,1]\). For each \(a_i\), write (one of) its binary representation(s):

\[a_i = {0.d_{i1} d_{i2} d_{i3} \ldots}_{2}, \] where each \(d_i \in \{0,1\}\).

For each \(i\), let \(e_i = 1-d_{ii}\), so that \(e_i = 0\) if \(d_{ii} = 1\) and \(e_i = 1\) if \(d_{ii} = 0\). Now, construct a number \(x \in [0,1]\) by writing down its binary representation:

\[x = {0. e_1 e_2 e_3 \ldots}_{2}.\]

Since \(x\) differs from \(a_i\) in the \(i^\text{th}\) binary digit, we know \(x \neq a_i\) for all \(i\in \mathbb{N}\).

But this means \(x\) is not in the list \(\{a_1, a_2, a_3, \ldots\}\), even though \(x\in [0,1]\). Thus, the list does not include every element of the set \([0,1]\), contradicting our assumption of countability! \(_\square\)

Cardinality places an equivalence relation on sets, which declares two sets \(A\) and \(B\) are equivalent when there exists a bijection \(A \to B\). The equivalence classes thus obtained are called cardinal numbers. For a set \(S\), let \(|S|\) denote its cardinal number.

There is an ordering on the cardinal numbers which declares \(|A| \le |B|\) when there exists an injection \(A \to B\). This is actually the Cantor-Bernstein-Schroeder theorem stated as follows:

If \(|A| \le |B|\) and \(|B| \le |A|\), then \(|A| = |B|\).

For finite sets, cardinal numbers may be identified with positive integers. The smallest infinite cardinal is \(\aleph_0\), which represents the equivalence class of \(\mathbb{N}\). This means that for any infinite set \(S\), one has \(\aleph_0 \le |S|\); that is, for any infinite set, there is an injection \(\mathbb{N} \to S\).

Cardinal arithmetic is defined as follows:

For two sets \(A\) and \(B\), one has \[\begin{align} |A|+|B| &:= |A \cup B|\\ |A| \cdot |B| &= |A \times B|,\end{align}\] where \(\cup\) denotes union and \(\times\) denotes Cartesian product.

Assuming the axiom of choice, the formulas for infinite cardinal arithmetic are even simpler, since the axiom of choice implies \(|A \cup B| = |A \times B| = \max\big(|A|, |B|\big)\).