Course 2 Book 2A: Numbers, Limits and the IntegralChapter 8

Infinite Sets

Countable and uncountable sets, the diagonal argument, and where the axiom of choice will be needed.

18 min read · Updated Oct 2, 2026

Read with Tao, Analysis I, chapter "Infinite sets" (countability, summation on infinite sets, uncountable sets, the axiom of choice, ordered sets), together with the last section of "Set theory" (cardinality of sets).

In this chapter · 5 sections

8.1Same size means a bijection
8.1.1Infinite sets are different
8.2Countable sets
8.2.1Summing over a countable set
8.3Uncountable sets
8.4The axiom of choice
8.5Exercises

The last two chapters measured infinity in one way: how big an infinite sum is. This chapter measures it in another: how many elements an infinite set has. The answer, found by Georg Cantor in the 1870s and 1880s, is that there are different sizes of infinity. The rationals and the natural numbers have the same size, even though the rationals seem far more numerous. The real numbers have strictly more.

This is the lightest chapter of Book 2A in terms of what later courses use directly, and it is honest to say so. Three things from it do matter. Countability is what makes the measure theory of 3A.1 The Problem of Measure work: countably many small sets can be ignored, uncountably many can't. Uncountability of $\mathbb{R}$ explains why almost every real number can't be computed. And the axiom of choice is the silent assumption behind several theorems of functional analysis and topology, so it is worth knowing where it enters.

By the end of this chapter you will be able to:

compare the sizes of sets with bijections, and use the pigeonhole principle;
prove that $\mathbb{Z}$ , $\mathbb{N} \times \mathbb{N}$ and $\mathbb{Q}$ are countable;
prove, by Cantor's diagonal argument, that $\mathbb{R}$ is uncountable;
explain what the axiom of choice says, and recognise where later theorems depend on it.

Same size means a bijection

How do you know two collections have the same size without counting them? Match them up. If every seat in a theatre is taken and nobody is standing, there are as many people as seats, and no number needs to be known. Cantor took this as the definition of equal size, and applied it to infinite sets as well.

Definition 8.1 Equal cardinality

Two sets $X$ and $Y$ have equal cardinality if there is a bijection $f : X \to Y$ (2A.2 Sets, Functions and Equivalence). A set has cardinality $n$ , for a natural number $n$ , if it has equal cardinality with $\{1, 2, \dots, n\}$ . It is finite if it has cardinality $n$ for some $n$ , and infinite otherwise.

For finite sets this agrees with counting, and Tao proves carefully that a finite set has exactly one cardinality. The proof rests on a principle so obvious it is easy to overlook.

Proposition 8.2 Pigeonhole principle

If $m > n$ , there is no injective function from a set of cardinality $m$ to a set of cardinality $n$ . Equivalently, if $m$ objects are placed in $n$ boxes with $m > n$ , some box contains at least two.

The proof is an induction on $n$ (Exercise 8.11).

In the world In use No compressor shrinks every file

A lossless compression program, such as the one inside every ZIP file, must be injective: two different files must compress to different outputs, or decompression couldn't tell them apart. The pigeonhole principle shows that no such program can make every file smaller. There are $2^n$ different files of exactly $n$ bits, but only $2^0 + 2^1 + \cdots + 2^{n-1} = 2^n - 1$ files shorter than $n$ bits. So at least one file of length $n$ cannot be shortened, and if some files get shorter, others must get longer. Compressors work in practice because real data (text, images, audio) is highly non-random, and they are designed to shrink the files people actually have, at the cost of slightly enlarging random-looking ones.

Figure 8.1. Eight files of three bits, and only seven shorter files to compress them into. Some file can't get shorter: the pigeonhole principle, applied to compression.

Infinite sets are different

For infinite sets the matching definition produces results that defy intuition. Galileo noticed one in 1638, in his Two New Sciences: the squares $1, 4, 9, 16, \dots$ can be matched one-to-one with the natural numbers $1, 2, 3, 4, \dots$ ( $n \leftrightarrow n^2$ ), although most natural numbers are not squares. Galileo concluded that "equal", "greater" and "less" do not apply to infinite collections. Cantor concluded instead that an infinite set can have the same size as a proper part of itself, and that this is what being infinite means.

Figure 8.2.

n \mapsto 2n

is a bijection from

\mathbb{N}

to the even numbers. So the even numbers, a proper subset of

\mathbb{N}

, have the same cardinality as

\mathbb{N}

, which is impossible for a finite set.

Countable sets

Definition 8.3 Countable

A set is countably infinite if it has the same cardinality as $\mathbb{N}$ , and countable if it is finite or countably infinite. Otherwise it is uncountable.

A set is countable exactly when its elements can be listed as a sequence $x_0, x_1, x_2, \dots$ (possibly with repeats, if the set is finite) that eventually reaches every element. That reformulation makes the next results easy to see.

Proposition 8.4 Countable sets

Every subset of a countable set is countable.
$\mathbb{Z}$ is countable.
$\mathbb{N} \times \mathbb{N}$ is countable.
$\mathbb{Q}$ is countable.

Proof. (1) List the elements of the big set and keep only those in the subset. (2) List $0, 1, -1, 2, -2, 3, -3, \dots$ . (3) List the pairs $(a, b)$ by increasing $a + b$ , and within each diagonal by increasing $a$ : $(0,0)$ ; $(0,1), (1,0)$ ; $(0,2), (1,1), (2,0)$ ; … (Figure 8.3). Each pair is reached after finitely many steps. An explicit formula is Cantor's pairing $(a, b) \mapsto \tfrac{(a+b)(a+b+1)}{2} + a$ , a bijection from $\mathbb{N} \times \mathbb{N}$ to $\mathbb{N}$ . (4) Every rational is $p/q$ for some integers $p$ and $q > 0$ , so $\mathbb{Q}$ is the image of a subset of $\mathbb{Z} \times \mathbb{N}$ , which is countable by (2) and (3). An image of a countable set is countable (list the images, skip repeats).

Figure 8.3. Listing the positive rationals: walk the grid of fractions

p/q

diagonal by diagonal, skipping fractions not in lowest terms (grey). Every positive rational is reached after finitely many steps, so the positive rationals are countable. Adding

0

and the negatives keeps them countable.

That $\mathbb{Q}$ is countable is the most surprising statement here. The rationals are dense (2A.3 Integers and Rationals): between any two there are infinitely many more, yet they can all be put in a single list.

Summing over a countable set

2A.7 Series showed that the value of an infinite sum can depend on the order of its terms, unless the sum converges absolutely. That makes it possible to sum over a countable set with no given order.

Proposition 8.5 Sums over countable sets

Let $X$ be countably infinite and $f : X \to \mathbb{R}$ . If for some (equivalently, every) bijection $g : \mathbb{N} \to X$ the series $\sum_n f(g(n))$ converges absolutely, then the sum doesn't depend on $g$ . It is written $\sum_{x \in X} f(x)$ .

This is the rearrangement theorem of 2A.7 Series in different words. It gives meaning to sums like $\sum_{(m,n) \in \mathbb{N}^2} \frac{1}{2^m 3^n}$ , with no preferred order of the pairs. For absolutely summable double sums, adding by rows, by columns, or along any listing gives the same answer, the infinite version of the double-sum swap (Exercise 8.16).

Uncountable sets

Is every infinite set countable? Cantor's answer, first published in 1874 and in its best-known form in 1891, was no. The 1891 argument is short enough to give in full.

Theorem 8.6 The real numbers are uncountable

The interval $[0, 1)$ , and hence $\mathbb{R}$ , is uncountable.

Proof (Cantor's diagonal argument). Suppose, for contradiction, that the numbers in $[0, 1)$ could be listed as $x_1, x_2, x_3, \dots$ . Write each in decimal, choosing the expansion that doesn't end in an infinite string of $9$s:

x_1 = 0.d_{11}d_{12}d_{13}\ldots,\qquad x_2 = 0.d_{21}d_{22}d_{23}\ldots,\qquad x_3 = 0.d_{31}d_{32}d_{33}\ldots,\quad \dots

Now build a new number $y = 0.e_1e_2e_3\ldots$ digit by digit, changing the diagonal: let $e_k = 5$ if $d_{kk} \neq 5$ , and $e_k = 4$ if $d_{kk} = 5$ . Then $y \in [0, 1)$ , its expansion has no $9$s, and it differs from each $x_k$ in the $k$ -th decimal place. So $y$ is not on the list, contradicting the assumption that the list contained every number in $[0, 1)$ .

The careful choice of digits ( $4$ and $5$ , never $0$ or $9$ ) avoids the one subtlety of decimals, that $0.0999\ldots = 0.1$ (2A.4 The Real Numbers), so that "different digits" really does mean "different numbers".

Figure 8.4. Cantor's diagonal argument. Whatever list of numbers you write down, change the

k

-th digit of the

k

-th number to build a number that differs from every row in at least one place. It isn't on the list, so no list contains them all.

The same idea proves a much more general theorem, with no decimals in sight.

Theorem 8.7 Cantor's theorem

For every set $X$ , there is no surjection from $X$ onto its power set $2^X$ , the set of all subsets of $X$ . So $2^X$ is strictly larger than $X$ .

Proof. Let $f : X \to 2^X$ be any function. Consider $D = \{x \in X : x \notin f(x)\}$ . If $D = f(a)$ for some $a$ , then $a \in D$ exactly when $a \notin f(a) = D$ , a contradiction. So $D$ is not in the image of $f$ .

This is the diagonal argument with the table hidden. Row $x$ is the set $f(x)$ , and $D$ is built to disagree with row $x$ about the element $x$ . It also echoes Russell's paradox from 2A.2 Sets, Functions and Equivalence, which has the same self-referential shape. Applying the theorem repeatedly gives an unending ladder of infinite sizes: $\mathbb{N}$ , $2^{\mathbb{N}}$ , $2^{2^{\mathbb{N}}}$ , …, each strictly bigger than the last. The set $2^{\mathbb{N}}$ has the same cardinality as $\mathbb{R}$ (Exercise 8.14).

Theorem 8.8 Schröder–Bernstein

If there are injections $X \to Y$ and $Y \to X$ , then $X$ and $Y$ have equal cardinality.

The theorem is intuitively obvious ("each is at most as big as the other"), but its proof requires a genuine construction, building a bijection out of pieces of the two injections; Tao gives it as an exercise with hints. It is the practical tool for comparing cardinalities: to show $\mathbb{R}$ and $\mathbb{R}^2$ have the same size, for instance, it is enough to inject each into the other (Exercise 8.15).

In the world In use Most numbers can't be computed

In 1936 Alan Turing defined a real number to be computable if some machine following a finite program can print its decimal expansion, digit after digit, forever. Every computer program is a finite string of symbols from a finite alphabet, and the set of all finite strings is countable (list them by length, and alphabetically within each length). So there are only countably many programs, and hence only countably many computable numbers. Turing observed exactly this in his paper. Since $\mathbb{R}$ is uncountable, almost all real numbers, in the sense of cardinality and, as 3A.2 Lebesgue Measure will show, also in the sense of measure, are not computable. Every number you will ever compute with, including $\pi$ , $e$ , $\sqrt 2$ and the outputs of every simulation of Ricci flow, belongs to a countable set.

Figure 8.5. Sizes of infinity.

\mathbb{N}

\mathbb{Z}

\mathbb{Q}

and the computable reals all have the same cardinality.

\mathbb{R}

is strictly larger and has the same size as

2^{\mathbb{N}}

. By Cantor's theorem,

2^{\mathbb{R}}

is larger still.

The axiom of choice

Many arguments involve making choices: "pick an element $x_n$ from each nonempty set $A_n$ ". Finitely many choices are justified by induction. For infinitely many, the other axioms of set theory don't suffice, and an extra axiom is needed.

Axiom 8.1 The axiom of choice

For every family $(A_\alpha)_{\alpha \in I}$ of nonempty sets, there is a function $f$ that assigns to each index $\alpha$ an element $f(\alpha) \in A_\alpha$ (a choice function).

It sounds harmless, and for most purposes it is. But its consequences include some genuinely strange results, which is why mathematicians keep track of where it is used.

History A controversial axiom

Ernst Zermelo formulated the axiom explicitly in 1904, to prove that every set can be well-ordered, that is, given an ordering in which every nonempty subset has a least element, like $\mathbb{N}$ (2A.1 The Natural Numbers). Nobody can write down such an ordering of $\mathbb{R}$ , and the proof didn't provide one, which many mathematicians found unacceptable. The axiom also implies the Banach–Tarski paradox (1924): a solid ball in space can be cut into finitely many pieces that can be moved rigidly and reassembled into two balls of the same size as the first. The pieces are so irregular that they have no volume at all (no well-defined measure), which is how volume fails to be conserved. Kurt Gödel (1938) and Paul Cohen (1963) showed that the axiom can neither be proved nor disproved from the other axioms of set theory. Most of mathematics, including all of this guidebook, assumes it.

A form of the axiom that is easier to apply in practice concerns partially ordered sets.

Definition 8.9 Partial orders and chains

A partial order on a set $X$ is a relation $\leq$ that is reflexive, antisymmetric and transitive. A chain is a subset in which any two elements are comparable. An upper bound of a subset $Y$ is an $x \in X$ with $y \leq x$ for every $y \in Y$ . A maximal element is an $m$ with no $x > m$ .

Theorem 8.10 Zorn's lemma

If $X$ is a nonempty partially ordered set in which every chain has an upper bound, then $X$ has a maximal element.

Zorn's lemma is equivalent to the axiom of choice. A typical use is to prove that every vector space has a basis: order the linearly independent subsets by inclusion; a chain has its union as an upper bound; a maximal independent set is a basis. For $\mathbb{R}$ regarded as a vector space over $\mathbb{Q}$ , such a basis exists but cannot be written down.

Where this goes Where choice and countability return

3A.1 The Problem of Measure: with the axiom of choice one can build a subset of $\mathbb{R}$ , Vitali's set, that has no reasonable length. This is why measure theory must restrict which sets are measured. Countability is also built into the axioms of measure: lengths add over countably many disjoint pieces, never uncountably many (a line segment is an uncountable union of points of length zero).
3A.2 Lebesgue Measure: every countable set has length zero, so $\mathbb{Q}$ is "negligible" inside $\mathbb{R}$ , even though it is dense.
4A.3 Hahn–Banach and Duality: the Hahn–Banach theorem, which supplies the linear functionals of functional analysis, uses Zorn's lemma.
4A.6 Weak Convergence and the Direct Method, 7A.2 Compactness and Compactification: the general Banach–Alaoglu and Tychonoff theorems use choice. In the separable spaces used for PDE, the guidebook proves the needed cases with a diagonal argument instead, which needs only countable choices.
2B.5 Uniform Convergence and Arzelà–Ascoli: the diagonal argument itself returns, in the proof of Arzelà–Ascoli, to extract a subsequence that converges at countably many points at once.

Recall Where we stand

Size is measured by bijections. $\mathbb{N}$ , $\mathbb{Z}$ , $\mathbb{N} \times \mathbb{N}$ and $\mathbb{Q}$ are countable; $\mathbb{R}$ is not; and every set is strictly smaller than its power set. The axiom of choice allows infinitely many arbitrary choices and is equivalent to Zorn's lemma. The next chapter, 2A.9 Continuous Functions, returns to the real line and to functions on it: continuity, and the first maximum principle.

Exercises

Exercise 8.11 The pigeonhole principle

Prove Proposition 8.2 by induction on $n$ . Then use it to show that among any $367$ people, two share a birthday. (Unlike the "birthday paradox", which says that $23$ people have a better than even chance of a shared birthday, this is a certainty.)

Exercise 8.12 Countable unions

Show that a union of countably many countable sets is countable. Where does your proof make infinitely many choices? (You must pick a listing of each set.)

Hint

Choose a listing $a_{n,0}, a_{n,1}, \dots$ of the $n$ -th set. Then $(n, k) \mapsto a_{n,k}$ maps $\mathbb{N} \times \mathbb{N}$ onto the union. The listings are the infinitely many choices: this is a use of the (countable) axiom of choice.

Exercise 8.13 Algebraic numbers

A real number is algebraic if it is a root of a nonzero polynomial with integer coefficients ( $\sqrt 2$ is a root of $x^2 - 2$ ). Show that the algebraic numbers are countable, and deduce that transcendental (non-algebraic) numbers exist. This was Cantor's own application in 1874.

Solution

For each $d$ and each bound $H$ , there are finitely many integer polynomials of degree $\leq d$ with coefficients bounded by $H$ in absolute value, and each has at most $d$ roots. So the algebraic numbers are a countable union of finite sets, hence countable. Since $\mathbb{R}$ is uncountable, some real numbers are not algebraic.

Exercise 8.14

2^{\mathbb{N}}

and the reals

Show that $2^{\mathbb{N}}$ and $[0, 1]$ have the same cardinality, using Schröder–Bernstein: send a subset $S \subseteq \mathbb{N}$ to $\sum_{n \in S} 3^{-(n+1)}$ (injective, because base-3 digits $0$ and $1$ only, with no ambiguity), and send $x \in [0, 1]$ to a set built from its binary expansion.

Exercise 8.15 The plane is no bigger than the line

Show that $[0,1)$ and $[0,1) \times [0,1)$ have the same cardinality, by interleaving decimal digits: $(0.a_1a_2\ldots, 0.b_1b_2\ldots) \mapsto 0.a_1b_1a_2b_2\ldots$ . Explain why this map is injective but not surjective, and how Schröder–Bernstein finishes the proof. (Cantor was astonished by this result.)

Exercise 8.16 Double sums revisited

Compute $\sum_{(m, n) \in \mathbb{N}^2} \frac{1}{2^m 3^n}$ , justifying any reordering. Compare with the double sum in 2A.7 Series, where the two orders disagreed, and say which hypothesis holds here and failed there.

Solution

The terms are positive, so the sum is absolutely convergent and may be computed in any order: $\sum_m 2^{-m} \sum_n 3^{-n} = 2 \cdot \tfrac32 = 3$ . In 2A.7 Series's example the terms were $\pm 1$ and the sum of absolute values was infinite.

Exercise 8.17 Rehearsal: diagonal extraction

Let $(a_{k}(n))$ be a sequence of sequences, all bounded: $|a_k(n)| \leq 1$ for all $k, n$ . Show that there is a subsequence $k_1 < k_2 < \cdots$ such that $a_{k_j}(n)$ converges as $j \to \infty$ for every $n$ . (Use Bolzano–Weierstrass (2A.6 Sequences) for $n = 0$ , then on that subsequence for $n = 1$ , and so on; then take the "diagonal" subsequence: the $j$ -th term of the $j$ -th subsequence.) This is the same diagonal idea as Cantor's, put to constructive use. It is the key step of the Arzelà–Ascoli theorem (2B.5 Uniform Convergence and Arzelà–Ascoli), and through it of every compactness theorem for spaces of functions, metrics and Ricci flows later in the route.

© 2026 NeckPinch (www.neckpinch.com). All content in the guidebook (text, mathematics, figures and exercises) is protected by copyright. All rights reserved. No part may be copied, republished or redistributed without written permission.

8.1Same size means a bijection

8.1.1Infinite sets are different

8.2Countable sets

8.2.1Summing over a countable set

8.3Uncountable sets

8.4The axiom of choice

8.5Exercises