Countability and Cardinal Numbers

Part 10, Chapter 10: Foundations, Cardinality, Choice, and Incompleteness

Learning objectives

Define countable and uncountable via bijections with $\mathbb{N}$
Construct explicit bijections $\mathbb{N} \leftrightarrow \mathbb{Z}$ and $\mathbb{N} \leftrightarrow \mathbb{Q}$
Apply Cantor's diagonal argument to show $\mathbb{R}$ is uncountable
State Cantor's theorem ( $|A| < |\mathcal{P}(A)|$ ) and its consequences for cardinal arithmetic

There is more than one size of infinity. This single, counterintuitive fact, established by Cantor in 1874, is the gateway to all of modern set theory. The integers and the rationals are countable; despite being densely packed in the real line, they can be listed in a single infinite sequence. The reals are not countable: no enumeration can hit them all. The gap between these two infinities is the source of an entire mathematical universe, and its precise quantification (the continuum hypothesis) is famously independent of the standard axioms.

Bijections measure size

Two sets $A$ and $B$ have the same cardinality, written $|A| = |B|$ , when there exists a bijection (one-to-one correspondence) $f: A \to B$ . For finite sets this matches the everyday notion of size. For infinite sets it is the definition: two infinite sets are "the same size" iff their elements can be paired off perfectly.

A set $A$ is countable if $|A| \leq |\mathbb{N}|$ , i.e. there exists an injection $A \to \mathbb{N}$ , equivalently, $A$ is finite or there is a bijection $\mathbb{N} \to A$ (one can list its elements as $a_1, a_2, a_3, \ldots$ ). Otherwise $A$ is uncountable.

The widget above lets you explore explicit bijections between standard sets. Try $\mathbb{N} \leftrightarrow \mathbb{Z}$ : list $\mathbb{Z}$ as $0, 1, -1, 2, -2, 3, -3, \ldots$ , this is the bijection $f(0) = 0, f(2k - 1) = k, f(2k) = -k$ for $k \geq 1$ . Then try the Cantor pairing $\mathbb{N} \times \mathbb{N} \leftrightarrow \mathbb{N}$ : enumerate the lattice diagonals $(0, 0), (0, 1), (1, 0), (0, 2), (1, 1), (2, 0), \ldots$ . The formula $\pi(m, n) = (m + n)(m + n + 1)/2 + m$ gives an explicit invertible coding.

The rationals are countable

Even though $\mathbb{Q}$ is dense in $\mathbb{R}$ (every interval contains rationals), there are no more rationals than natural numbers. Proof sketch: arrange positive rationals $p/q$ in a 2D grid with $p$ along rows and $q$ along columns. Traverse the grid diagonally, skipping fractions that are not in lowest terms: $1/1, 1/2, 2/1, 1/3, 3/1, 1/4, 2/3, 3/2, 4/1, \ldots$ . This is a bijection between $\mathbb{N}$ and $\mathbb{Q}^+$ . Combine with the zero and negatives by interleaving: $0, 1/1, -1/1, 1/2, -1/2, 2/1, -2/1, \ldots$ . Hence $|\mathbb{Q}| = \aleph_0$ , the smallest infinite cardinal.

The reals are uncountable: Cantor's diagonal argument

Suppose for contradiction that the reals in $[0, 1)$ can be listed as $r_1, r_2, r_3, \ldots$ . Write each in decimal: $r_k = 0.d_{k1} d_{k2} d_{k3} \ldots$ k3ldots. Define a new number $s = 0.s_1 s_2 s_3 \ldots$ by choosing each $s_n$ n to differ from $d_{nn}$ nn (and to avoid the digits $0$ and $9$ to dodge the ambiguity $0.999\ldots = 1.000\ldots$ ). Then $s$ differs from every $r_n$ n at the $n$ -th decimal place, so $s$ is not in the list. Contradiction. Hence $\mathbb{R}$ is uncountable.

The cardinality of $\mathbb{R}$ is denoted $\mathfrak{c} = 2^{\aleph_0}$ (the "cardinality of the continuum"). Whether there is a cardinal strictly between $\aleph_0$ and $\mathfrak{c}$ is the continuum hypothesis, which Godel and Cohen proved is independent of ZFC.

Cantor's theorem: there is no largest cardinal

For any set $A$ , the power set $\mathcal{P}(A) = \{S : S \subseteq A\}$ has strictly larger cardinality than $A$ . Proof: suppose $f: A \to \mathcal{P}(A)$ is any function. Define $D = \{a \in A : a \notin f(a)\} \in \mathcal{P}(A)$ . Then no $a \in A$ satisfies $f(a) = D$ : if $a \in D$ then by definition $a \notin f(a) = D$ (contradiction); if $a \notin D$ then $a \in f(a) = D$ (contradiction). So $f$ is not surjective, hence not a bijection. There are infinitely many infinite cardinals: $|\mathbb{N}| < |\mathcal{P}(\mathbb{N})| < |\mathcal{P}(\mathcal{P}(\mathbb{N}))| < \ldots$ .

Where this shows up

Computer science (computable functions): The set of Turing machines is countable (each one is a finite description), but the set of all functions $\mathbb{N} \to \{0, 1\}$ is uncountable (in bijection with $\mathcal{P}(\mathbb{N})$ ). Therefore most functions are uncomputable, this is the foundational reason there is no universal algorithm.

Number theory (algebraic vs transcendental): The algebraic numbers form a countable set (each is a root of a polynomial with rational coefficients, and there are countably many such polynomials). Since $\mathbb{R}$ is uncountable, most reals are transcendental. Cantor used this counting argument to prove transcendentals exist before Hermite's explicit proof for $e$ in 1873.

Measure theory: Countable sets in $\mathbb{R}$ have Lebesgue measure zero, so $\mathbb{Q} \subset \mathbb{R}$ has measure zero. "Almost every real is irrational" is a precise probabilistic statement coming directly out of countability.

Statistical mechanics: The state space of a finite-dimensional quantum system is countable when truncated to a basis, but the continuous Hilbert space of operators on an infinite-dimensional separable Hilbert space has cardinality $\mathfrak{c}$ . The gap matters for entropy and microstate counting.

Pause and think: Use the cardinality widget to find a bijection between $(0, 1)$ and $\mathbb{R}$ . (Hint: the map $x \mapsto \tan(\pi(x - 1/2))$ is one explicit example. There are uncountably many.) Why does this prove $|(0, 1)| = |\mathbb{R}| = \mathfrak{c}$ ?

Try it

Use the cardinality widget to verify the $\mathbb{N} \leftrightarrow \mathbb{Z}$ bijection. List the first ten values of the inverse map and check no integer is missed.

Apply the diagonal argument to the list $r_1 = 0.1357\ldots, r_2 = 0.2468\ldots, r_3 = 0.9090\ldots, r_4 = 0.1234\ldots$ . Construct a real number not in the list.

Predict first: is the set of finite subsets of $\mathbb{N}$ countable or uncountable? (Hint: a finite subset of $\mathbb{N}$ can be encoded as a finite binary string, and the set of finite binary strings is countable.)

True or false: the set of all sequences of zeros and ones (functions $\mathbb{N} \to \{0, 1\}$ ) is countable. (Hint: this set is in bijection with $\mathcal{P}(\mathbb{N})$ .)

A trap to watch for

"Countable" does NOT mean "you can finish counting it." A countable set may be infinite, the integers are countable, but the counting process $0, 1, -1, 2, -2, \ldots$ never ends. The technical definition is: there exists an injection into $\mathbb{N}$ , equivalently a listing as $a_1, a_2, a_3, \ldots$ . Some authors use "countable" to mean "denumerable / countably infinite" only (excluding finite sets); others use it to include finite. Velleman and Garrity use the inclusive convention, finite sets are countable too, which is the more common modern usage. Always check the convention before drawing conclusions about "the smallest uncountable set."

What you now know

You can distinguish countable and uncountable sets via bijections with $\mathbb{N}$ , prove $\mathbb{Q}$ is countable and $\mathbb{R}$ is not, and recognize that cardinal arithmetic produces an infinite ladder of larger and larger infinities via the power-set operation. The next section confronts the paradoxes that lurked in 19th-century "naive" set theory, where unrestricted set comprehension led to outright contradictions.

Mark section complete →

References

Garrity, T. (2002). All the Mathematics You Missed: But Need to Know for Graduate School. Cambridge University Press, §10.1-10.2.

Halmos, P. R. (1960). Naive Set Theory. Springer, §22-24 (Cardinal Numbers).

Enderton, H. B. (1977). Elements of Set Theory. Academic Press, ch. 6.

Hrbacek, K., Jech, T. (1999). Introduction to Set Theory (3rd ed.). CRC Press, ch. 4.

Cantor, G. (1874). "Uber eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen." Crelle's Journal, 77, 258-262 (original diagonal-argument paper).

This page is prerendered for SEO and accessibility. The interactive widgets above hydrate on JavaScript load.