2  Cardinality and countability

Cardinality compares sets through bijections. The exercises cover countable sets, Cantor’s diagonal argument, and the cardinality of the continuum.

Recall that the cardinality \(|S|\) of a set \(S\) is the number of elements in \(S\). For finite sets, this is intuitive, but what about infinite sets?

One says that \(A\) and \(B\) have the same cardinality if there exists a bijection \(f : A \to B\), i.e., \(f\) is one-to-one and onto. (Intuitively, you can draw lines between individual elements of \(A\) and \(B\), only one line to/from each element. Precisely: Onto means, to every \(b \in B\) there exists a \(a \in A\) such that \(f(a) = b\). One-to-one: \(f(a)=f(a')\) implies \(a=a'\).) One can think of the bijection as labelling each \(b\in B\) by exactly one element \(a\in A\), and that all labels from \(A\) are used up.

Let \(\mathbb{N}_n = \{1, 2, \cdots, n\}\). This set has cardinality \(n\).

The set \(\mathbb{N}\) has an infinite number of elements. By definition, \(|\mathbb{N}|= \aleph_0\) (“aleph-nought”).

Exercises

Exercise 2.1 (Countability of the integers) Show that \(|\mathbb{Z}|=\aleph_0\) by explicitly constructing a bijection \(f : \mathbb{N}\to \mathbb{Z}\).

Exercise 2.2 (Countability of the natural number plane) Show that \(|\mathbb{N}\times \mathbb{N}| = \aleph_0\). Hint: Draw a picture of \(\mathbb{N}\times \mathbb{N}\), and try to draw a line through all the points in this set. How does this show the existence of a bijection between \(\mathbb{N}\) and \(\mathbb{N}\times\mathbb{N}\)?

Exercise 2.3 (Countability of the rational numbers) Show that \(|\mathbb{Q}|= \aleph_0\).

Exercise 2.4 (Interval vs. real numbers) Show that the interval \(I = (-1,1)\) has the same cardinality as \(\mathbb{R}\). You must construct a function \(f : (-1,1)\to\mathbb{R}\) that is a bijection.

Exercise 2.5 (Uncountability of the real numbers) In this exercise, we show that \(|\mathbb{R}| > \aleph_0\). The cardinality would be \(\aleph_0\) if we could write a list of the real numbers. It suffices to find a list of the numbers in \(I = [0,1[\), i.e., infinite decimal expansions \(0.d_1d_2d_3\cdots\), with \(d_i\in \{0,1,2,3,4,5,6,7,8,9\}\).

We will look for a contradiction. Consider a list \(x_1,x_2,x_3,\ldots\) of all real numbers in \([0,1[\). This is essentially an infinite matrix of digits. Can you find a real number \(x \in [0,1]\) which is not in this list, i.e., \(x \neq x_j\) for all \(j\)? Hint: consider the diagonal of the matrix.

The cardinality of \(\mathbb{R}\), “the continuum”, is written \(2^{\aleph_0}\).

Exercise 2.6 (Constructing a one-to-one map) Show that \(|[0,1[\times [0,1[| = |[0,1[|\), by constructing a one-to-one map. Hint: Use decimal expansions. Conclude that also \(|\mathbb{R}^2| = |\mathbb{C}| = |\mathbb{R}|\).