Counting the infinite

Asking how many real numbers there are invites the answer "infinitely many", and that answer says nothing until "how many" has a meaning that works for infinite sets.

The previous lesson ranked the elements of a set by order, ended on Zorn's lemma, a principle about infinite sets, and left a prior question: how large is an infinite set, and how many reals are there? This lesson answers it with functions alone, assuming from the lesson on functions injective, surjective and bijective maps, inverses, and the facts that a composite of injections is an injection and a composite of bijections is a bijection. It also uses the well-ordering principle: every non-empty set of natural numbers has a least element. As throughout the course, $\mathbb{N}=\{1,2,3,\dots \}$ starts at $1$, and $P(A)$ is the power set of $A$.

Same size without counting

Someone who cannot count can still tell whether there are as many cups as saucers: put one cup on each saucer and see whether anything is left over. That pairing is a bijection, and it is the definition. Sets $A$ and $B$ are equinumerous, or have the same size, written $|A|=|B|$, when there is a bijection $A\to B$. And $|A|\le |B|$ means there is an injection $A\to B$, which seats every element of $A$ in its own place in $B$, perhaps with places to spare. Finally $|A|<|B|$ means that $|A|\le |B|$ and not $|A|=|B|$: an injection exists and a bijection does not.

Proposition. For all sets $A$, $B$ and $C$: (i) $|A|=|A|$; (ii) if $|A|=|B|$ then $|B|=|A|$; (iii) if $|A|=|B|$ and $|B|=|C|$ then $|A|=|C|$; (iv) $|A|\le |A|$, and if $|A|\le |B|$ and $|B|\le |C|$ then $|A|\le |C|$; (v) if $A\subseteq B$ then $|A|\le |B|$.

Proof. (i) The identity ${\mathrm{id}}_A$ is a bijection. (ii) A bijection has an inverse, which is a bijection $B\to A$. (iii) If $f:A\to B$ and $g:B\to C$ are bijections, so is $g\circ f:A\to C$. (iv) The identity is an injection, and a composite of injections is an injection. (v) The inclusion map $a\mapsto a$ from $A$ to $B$ is an injection. $\square$

The notation is suggestive, and it is worth being clear about what it does not yet say. No object called $|A|$ has been defined; "$|A|=|B|$" is a statement about the two sets, and so is "$|A|\le |B|$". In particular, nothing so far says that $|A|\le |B|$ and $|B|\le |A|$ together give $|A|=|B|$. For numbers that is antisymmetry, and it is free. For sets it says that injections both ways produce a bijection, which is a real theorem, proved later in this lesson. In the language of the lesson on order, "$|A|\le |B|$" is a preorder on sets, and the theorem says its ties are exactly the equinumerous pairs.

Nor is "smaller" the same as "subset". The natural numbers are a proper subset of the integers, and the next sections show $|\mathbb{N}|=|\mathbb{Z}|$. For finite sets a proper subset is always smaller, and that is the first thing to prove.

Finite sets and the pigeonhole principle

For $n\ge 1$ write $[n]=\{1,2,\dots ,n\}$, and let $[0]=\varnothing$. A set $A$ is finite, with $n$ elements, when $|A|=|[n]|$ for some $n\ge 0$; a bijection $[n]\to A$ is a way of counting $A$, naming its elements first, second, and so on up to $n$th. A set that is not finite is infinite.

For the definition to make sense, a set must not have both $m$ and $n$ elements for different $m$ and $n$. That is the pigeonhole principle, from the lesson on contradiction, in its sharpest form.

Lemma (pigeonhole). If $m>n\ge 0$, there is no injection $[m]\to [n]$.

Proof. By induction on $n$. For $n=0$: $[m]$ is not empty, since $m\ge 1$, and there is no function at all from a non-empty set to $\varnothing$.

Suppose the claim holds for $n$, and suppose for a contradiction that $f:[m]\to [n+1]$ is an injection with $m>n+1$. We build an injection $[m-1]\to [n]$. If no element of $[m-1]$ is sent to $n+1$, then $f$ restricted to $[m-1]$ is already an injection into $[n]$. Otherwise $f(k)=n+1$ for some $k\le m-1$, and by injectivity $k$ is the only such element, so $f(m)\ne n+1$. Define $g$ on $[m-1]$ by $g(k)=f(m)$ and $g(i)=f(i)$ for $i\ne k$. The values of $g$ are values of $f$ at the distinct points of $[m]\setminus \{k\}$, so they are distinct and none is $n+1$; $g$ is an injection $[m-1]\to [n]$. Either way, since $m-1>n$, this contradicts the claim for $n$. $\square$

Corollary. (a) If $|[m]|=|[n]|$ then $m=n$, so the number of elements of a finite set is well defined. (b) $\mathbb{N}$ is infinite. (c) A finite set is not equinumerous with any proper subset of itself.

Proof. (a) A bijection $[m]\to [n]$ is an injection, so $m\le n$ by the lemma; its inverse gives $n\le m$.

(b) Suppose $h:\mathbb{N}\to [n]$ were a bijection. Restricted to $[n+1]\subseteq \mathbb{N}$ it is an injection $[n+1]\to [n]$, which the lemma forbids.

(c) Let $A$ have $n$ elements, with $\phi :[n]\to A$ a bijection, and suppose $h:A\to S$ is a bijection onto a proper subset $S$ of $A$. Then $g={\phi }^{-1}\circ h\circ \phi$ is an injection $[n]\to [n]$ whose image misses some $k$, namely ${\phi }^{-1}(a)$ for any $a\in A\setminus S$. So $n\ge 1$. The map $s:[n]\setminus \{k\}\to [n-1]$ that fixes numbers below $k$ and lowers numbers above $k$ by one is injective, and $s\circ g$ is an injection $[n]\to [n-1]$, which the lemma forbids. $\square$

Part (c) is what fails for infinite sets. Richard Dedekind turned it round in 1888 and defined a set to be infinite when it is equinumerous with a proper subset of itself, a definition the next section shows $\mathbb{N}$ meets. The same lemma, restated, is the everyday pigeonhole principle: if more than $n$ objects are put into $n$ boxes, some box receives two, because the assignment of boxes cannot be an injection.

Hilbert's hotel and countable sets

David Hilbert gave the infinite case its best known picture in a Göttingen lecture of 1924, and George Gamow made it famous in his 1947 book One Two Three... Infinity. A hotel has a room for every natural number, all taken, when a new guest arrives. The manager asks the guest in room $n$ to move to room $n+1$. Everyone still has a room, nobody shares, and room $1$ is free.

The move is $s:\mathbb{N}\to \mathbb{N}\setminus \{1\}$, $s(n)=n+1$, and it is a bijection. It is injective, since $m+1=n+1$ gives $m=n$. It is surjective, since each $k$ in $\mathbb{N}\setminus \{1\}$ has $k\ge 2$, so $k-1\in \mathbb{N}$ and $s(k-1)=k$. So $|\mathbb{N}\setminus \{1\}|=|\mathbb{N}|$, and $\mathbb{N}$ is infinite in Dedekind's sense. When a coach brings a guest for every natural number, moving each guest from room $n$ to room $2n$ frees the odd rooms for them, so $\mathbb{N}$ is the same size as two copies of itself. "The whole is greater than the part" is Euclid's fifth common notion, true for finite collections by part (c) of the corollary and false for infinite ones.

A set is countably infinite when it is equinumerous with $\mathbb{N}$, countable when it is finite or countably infinite, and uncountable otherwise. A bijection $g:\mathbb{N}\to A$ is a list of $A$, $g(1)$ first, $g(2)$ second, in which every element appears exactly once and is reached after finitely many steps. Cantor wrote ${\aleph }_0$ (aleph null) for the size of $\mathbb{N}$. Starting $\mathbb{N}$ at $0$ instead changes nothing, since the hotel's shift $n\mapsto n+1$ is a bijection from $\{0,1,2,\dots \}$ to $\mathbb{N}$.

The integers run off in both directions, so listing them in their usual order has no first term. Alternating works: $0,1,-1,2,-2,\dots$

Example. Prove that $f:\mathbb{N}\to \mathbb{Z}$, given by $f(n)=\frac{n}{2}$ for even $n$ and $f(n)=\frac{1-n}{2}$ for odd $n$, is a bijection, so that $\mathbb{Z}$ is countable.

The values are integers ($1-n$ is even when $n$ is odd), beginning $f(1)=0$, $f(2)=1$, $f(3)=-1$, $f(4)=2$. Injective: for even $n$, $f(n)=\frac{n}{2}\ge 1$, while for odd $n$, $f(n)=\frac{1-n}{2}\le 0$ because $n\ge 1$. So if $f(m)=f(n)$, then $m$ and $n$ have the same parity, and either $\frac{m}{2}=\frac{n}{2}$ or $\frac{1-m}{2}=\frac{1-n}{2}$; both give $m=n$. Surjective: let $k\in \mathbb{Z}$. If $k\ge 1$, put $n=2k$, an even natural number, and $f(n)=k$. If $k\le 0$, put $n=1-2k$, which is odd and at least $1$, so $n\in \mathbb{N}$, and $f(n)=\frac{1-(1-2k)}{2}=k$. Hence $f$ is a bijection and $|\mathbb{Z}|=|\mathbb{N}|$.

The surjectivity step also found the inverse: $f^{-1}(k)=2k$ for $k\ge 1$ and $f^{-1}(k)=1-2k$ for $k\le 0$. So $-3$ sits at position $7$ in the list.

Now you. Prove that $g:\mathbb{N}\to \mathbb{Z}\setminus \{0\}$, given by $g(n)=\frac{n}{2}$ for even $n$ and $g(n)=-\frac{n+1}{2}$ for odd $n$, is a bijection.

Finding an explicit bijection can be fiddly, and the next theorem often removes the need: to show a set is countable, it is enough to inject it into $\mathbb{N}$.

Theorem. Every subset of $\mathbb{N}$ is countable. Consequently, a set $A$ is countable if and only if there is an injection $A\to \mathbb{N}$, and a non-empty set $A$ is countable if and only if there is a surjection $\mathbb{N}\to A$.

Proof. Let $S\subseteq \mathbb{N}$ be infinite; we list it in increasing order. Let $s_1=\min S$, and for $k\ge 1$ let $s_{k+1}=\min (S\setminus \{s_1,\dots ,s_k\})$. The set on the right is never empty, since otherwise $S=\{s_1,\dots ,s_k\}$ would be finite, so by well-ordering each $s_k$ is defined. The sequence is strictly increasing: $s_{k+1}$ lies in $S\setminus \{s_1,\dots ,s_{k-1}\}$, whose least element is $s_k$, and $s_{k+1}\ne s_k$. So $k\mapsto s_k$ is injective, and, by induction, $s_k\ge k$ for every $k$. It is also surjective. Let $t\in S$, and suppose $t$ is not among $s_1,\dots ,s_t$. Then $t\in S\setminus \{s_1,\dots ,s_{t-1}\}$, so its least element $s_t$ satisfies $s_t\le t$; with $s_t\ge t$ this gives $s_t=t$, a contradiction. So $k\mapsto s_k$ is a bijection $\mathbb{N}\to S$.

For the first consequence: a countable set injects into $\mathbb{N}$, through a bijection with $\mathbb{N}$ or with some $[n]\subseteq \mathbb{N}$. Conversely, an injection $h:A\to \mathbb{N}$ is a bijection from $A$ onto its image $h(A)\subseteq \mathbb{N}$, which is countable, so $A$ is countable.

For the second: if $A$ is countable and non-empty, a bijection $\mathbb{N}\to A$ is a surjection, and if $A$ has $n\ge 1$ elements, the bijection $[n]\to A$ extended by sending every $k>n$ to the image of $1$ is a surjection. Conversely, given a surjection $q:\mathbb{N}\to A$, send each $a\in A$ to the least element of $\{n:q(n)=a\}$, which exists by well-ordering. This map is injective, since different elements $a$ have disjoint sets of such $n$, so $A$ is countable by the first consequence. $\square$

So subsets and surjective images of countable sets are countable. A countable set is the smallest kind of infinite set, in a sense made precise in the following question.

Pairs and the rationals

The set $\mathbb{N}\times \mathbb{N}$ is an infinite grid, with $(m,n)$ in row $m$ and column $n$. Listing row $1$ first never reaches row $2$. The way out is to list by diagonals. There are exactly $s-1$ pairs with $m+n=s$, from $(1,s-1)$ to $(s-1,1)$, so list the diagonal with sum $2$, then sum $3$, and so on, each by increasing first coordinate:

The position of $(m,n)$ in this list is a formula. Write $T(k)=\frac{k(k+1)}{2}=1+2+\cdots +k$, with $T(0)=0$. With $s=m+n$, the earlier diagonals hold $1+2+\cdots +(s-2)=T(s-2)$ pairs, and $(m,n)$ is in place $m$ on its own, so its position is

This is the Cantor pairing function, shifted so that $\mathbb{N}$ starts at $1$. It gives $p(1,1)=1$, $p(1,2)=2$, $p(2,1)=3$ and $p(3,5)=T(6)+3=24$.

Theorem. The function $p$ is a bijection $\mathbb{N}\times \mathbb{N}\to \mathbb{N}$. In particular $\mathbb{N}\times \mathbb{N}$ is countable.

Proof. Fix $s\ge 2$. The pairs with $m+n=s$ are those with $1\le m\le s-1$, and $p$ sends them to $T(s-2)+1,T(s-2)+2,\dots ,T(s-2)+(s-1)=T(s-1)$. So $p$ maps diagonal $s$ injectively onto the block $B_s=\{N\in \mathbb{N}:T(s-2)<N\le T(s-1)\}$.

The blocks $B_2,B_3,B_4,\dots$ are disjoint and cover $\mathbb{N}$. They are disjoint because $T$ is increasing, so the ranges $(T(s-2),T(s-1)]$ do not overlap. They cover $\mathbb{N}$ because, given $N\in \mathbb{N}$, the set of $s\ge 2$ with $T(s-1)\ge N$ is not empty ($T(N)\ge N$), so it has a least element $s$; then $T(s-1)\ge N$, and $T(s-2)<N$, either because $s=2$ and $T(0)=0$ or by the minimality of $s$. So $N\in B_s$.

Now $p$ is injective: two pairs on the same diagonal have different images, and two pairs on different diagonals land in different blocks. And $p$ is surjective: each $N$ lies in some block $B_s$, which is the image of diagonal $s$. $\square$

As a check, the $1770$ pairs with $m+n\le 60$ (diagonals $2$ to $60$, holding $1+2+\cdots +59=1770$ pairs) are sent to exactly $1$ to $1770$, since the last block ends at $T(59)=1770$. A second, shorter bijection, $(m,n)\mapsto 2^{m-1}(2n-1)$, is Problem 5.

Since $\mathbb{N}\times \mathbb{N}$ is countable, so is $A\times B$ for any countable sets $A$ and $B$: injections $a:A\to \mathbb{N}$ and $b:B\to \mathbb{N}$ give the injection $(x,y)\mapsto p(a(x),b(y))$ from $A\times B$ to $\mathbb{N}$. By induction on $k$, then, ${\mathbb{Z}}^k={\mathbb{Z}}^{k-1}\times \mathbb{Z}$ is countable for every $k\ge 1$.

Between two rationals lies their average, so $\mathbb{Q}$ cannot be listed in increasing order. It can be listed in another.

Example. Prove that $\mathbb{Q}$ is countable.

Every rational has exactly one form $\frac{a}{b}$ in lowest terms with $a\in \mathbb{Z}$ and $b\in \mathbb{N}$. With $f$ the bijection $\mathbb{N}\to \mathbb{Z}$ above, define $h:\mathbb{Q}\to \mathbb{N}\times \mathbb{N}$ by $h(\frac{a}{b})=(f^{-1}(a),b)$, using that form; its uniqueness is what makes $h$ a function. If $h(\frac{a}{b})=h(\frac{c}{d})$, then $f^{-1}(a)=f^{-1}(c)$, so $a=c$ on applying $f$, and $b=d$; so the rationals are equal, and $h$ is injective. Then $p\circ h:\mathbb{Q}\to \mathbb{N}$ is a composite of injections, hence an injection, and by the theorem of the previous section $\mathbb{Q}$ is countable. It is infinite, since it contains $\mathbb{N}$, so $|\mathbb{Q}|=|\mathbb{N}|$.

For instance $-\frac{3}{4}$ goes to $(7,4)$ and then to $p(7,4)=T(9)+7=52$. Position $p(4,2)=14$ is not used, since $(4,2)$ would stand for $\frac{2}{2}$, which is not in lowest terms. The injection is not a bijection, and the theorem on subsets of $\mathbb{N}$ closes the gap: listing the image of $p\circ h$ in increasing order and sending each rational to the rank of its code in that list is an explicit bijection $\mathbb{Q}\to \mathbb{N}$. Problem 12 gives a more elegant list of the positive rationals, in which each appears exactly once and no gaps need closing.

Now you. Prove that $F(a,b)=p(f^{-1}(a),f^{-1}(b))$ is a bijection $\mathbb{Z}\times \mathbb{Z}\to \mathbb{N}$, and compute $F(-1,2)$.

Countable unions

A countable set of countable sets has a countable union. This is the most used closure property of countable sets, and it follows from the pairing function.

Theorem. Let $A_1,A_2,A_3,\dots$ be countable sets. Then $A_1\cup A_2\cup A_3\cup \cdots$ is countable. The same holds for finitely many countable sets.

Proof. Let $U$ be the union. If every $A_n$ is empty, so is $U$. Otherwise, discard the empty sets; what remains is a finite or infinite sequence of non-empty countable sets with the same union, and repeating one of them if necessary makes it an infinite sequence $A_1,A_2,\dots$ of non-empty countable sets. By the theorem on countable sets, for each $n$ there is a surjection $g_n:\mathbb{N}\to A_n$; choose one for each $n$. Define $G:\mathbb{N}\times \mathbb{N}\to U$ by $G(n,k)=g_n(k)$. It is surjective: an element of $U$ lies in some $A_n$, and is $g_n(k)$ for some $k$. Then $G\circ p^{-1}:\mathbb{N}\to U$ is a surjection, and $U$ is countable. $\square$

For example, $\mathbb{Q}$ is the union over $b\in \mathbb{N}$ of the sets $\{\frac{a}{b}:a\in \mathbb{Z}\}$, each countable as the image of $\mathbb{Z}$, which gives a second proof that $\mathbb{Q}$ is countable.

Example. Prove that the set $\mathbb{Z}[x]$ of polynomials with integer coefficients is countable.

For $n\ge 0$, let $P_n$ be the set of polynomials $c_0+c_{1}x+\cdots +c_n{x}^n$ with every $c_i\in \mathbb{Z}$, that is, the polynomials of degree at most $n$ (together with the zero polynomial). Such a polynomial is determined by its list of coefficients, and every list gives a polynomial, so $(c_0,\dots ,c_n)\mapsto c_0+c_{1}x+\cdots +c_n{x}^n$ is a bijection ${\mathbb{Z}}^{n+1}\to P_n$. Since ${\mathbb{Z}}^{n+1}$ is countable, so is $P_n$, and this bijection is an explicit list of it (composed with a list of ${\mathbb{Z}}^{n+1}$), so no choice is involved. Every polynomial has some degree $n$, so $\mathbb{Z}[x]=P_0\cup P_1\cup P_2\cup \cdots$, a countable union of countable sets, and $\mathbb{Z}[x]$ is countable.

Now you. Prove that the set of all finite subsets of $\mathbb{N}$ is countable.

The same pattern shows that the set of all finite sequences of natural numbers is countable (the union over $k$ of the countable sets ${\mathbb{N}}^k$), and so is the set of all finite strings over a finite or countable alphabet. Every book, proof or computer program is such a string, so there are only countably many of each.

Intervals and the real line

Before asking whether $ℝ$ is countable, it helps to see that its size does not depend on which piece of the line is taken. The lesson on functions proved that $x\mapsto \frac{x}{1+|x|}$ is a bijection $ℝ\to (-1,1)$, and $x\mapsto \frac{x+1}{2}$ is a bijection $(-1,1)\to (0,1)$, with inverse $y\mapsto 2y-1$. Composing, $|ℝ|=|(0,1)|$: the whole line has as many points as a short open piece of it. The same stretching shows that any two open intervals $(a,b)$ and $(c,d)$ with $a<b$ and $c<d$ are equinumerous, through $x\mapsto c+\frac{(x-a)(d-c)}{b-a}$.

Endpoints look harder, since no continuous bijection turns $[0,1)$ into $(0,1)$. But bijections need not be continuous, and the hotel's trick absorbs a point.

Example. Give an explicit bijection $h:[0,1)\to (0,1)$.

The point $0$ needs a room in $(0,1)$. Pick a sequence of distinct points inside $(0,1)$, say $\frac{1}{2},\frac{1}{3},\frac{1}{4},\dots$, and shift along it, as the hotel shifts its guests: send $0$ to $\frac{1}{2}$, each $\frac{1}{n}$ with $n\ge 2$ to $\frac{1}{n+1}$, and every other point to itself.

Let $Q=\{\frac{1}{n}:n\ge 2\}$. Then $h$ maps $\{0\}\cup Q$ into $Q$, and $[0,1)\setminus (\{0\}\cup Q)$ into itself by the identity, so its values lie in $(0,1)$. Injective: two points in the third case have different images since $h$ is the identity there, and their images are not in $Q$, while images in the first two cases are in $Q$; within $\{0\}\cup Q$, the images $\frac{1}{2}$ (of $0$) and $\frac{1}{n+1}$ (of $\frac{1}{n}$) are all different, since $n\mapsto n+1$ is injective and $n+1\ge 3$. Surjective: let $y\in (0,1)$. If $y\notin Q$, then $h(y)=y$. If $y=\frac{1}{2}$, then $h(0)=y$. If $y=\frac{1}{m}$ with $m\ge 3$, then $h(\frac{1}{m-1})=y$, as $m-1\ge 2$. So $h$ is a bijection.

Now you. Give an explicit bijection $[0,1]\to (0,1)$.

So every interval with more than one point, open, closed or half open, bounded or not, has the same size as $ℝ$. The Schröder and Bernstein theorem, later in the lesson, will make results like this one line long, at the price of not exhibiting the bijection.

Cantor's diagonal argument

Georg Cantor proved in 1874 that the reals are not countable, and in 1891 gave the proof now called the diagonal argument. It uses decimal expansions of numbers in $(0,1)$, and has one trap.

This lesson takes two facts about decimals from school, and the lesson on the real numbers proves them from its definitions: every real number in $(0,1)$ has a decimal expansion $0.d_1{d}_2{d}_3\dots$, and every such expansion names a real number in $[0,1]$. Some numbers have two expansions: $0.4999\dots =0.5$, since the tail $0.0999\dots$ is a geometric series with sum $\frac{9}{100}\cdot \frac{10}{9}=\frac{1}{10}$. This is the only way it happens. Two different expansions first disagree at some place $k$, and the later digits can make up at most one unit in place $k$, which they do only when one tail is all $9$s and the other all $0$s. So an expansion with no $0$ and no $9$ is the only expansion of its number. For numbers with two, use the one that does not end in $9$s.

Here is the start of a list of numbers in $(0,1)$, with the $n$th digit of the $n$th number in bold:

The new digit is $5$, unless the diagonal digit is $5$, when it is $4$. The number $0.555545\dots$ built from them differs from every $x_n$ in place $n$.

Example. Prove that there is no surjection $\mathbb{N}\to (0,1)$.

Let $g:\mathbb{N}\to (0,1)$ be any function, and let $d_{n,k}$ be the $k$th digit of $g(n)$, using the expansion chosen above. Put $c_n=4$ if $d_{n,n}=5$ and $c_n=5$ otherwise, and let $y=0.c_1{c}_2{c}_3\dots$. Every digit of $y$ is $4$ or $5$, so $\frac{4}{9}=0.444\dots \le y\le 0.555\dots =\frac{5}{9}$, and $y\in (0,1)$. Suppose $y=g(n)$ for some $n$. The expansion of $y$ has no $0$ or $9$, so it is the only one $y$ has, and the chosen expansion of $g(n)$ must be it. Then $d_{n,n}=c_n$, contradicting the choice of $c_n$. So $y$ is not a value of $g$, and $g$ is not surjective.

So $(0,1)$ is uncountable: it is not empty, and no surjection from $\mathbb{N}$ reaches all of it. Hence $ℝ$ is uncountable too, since $|ℝ|=|(0,1)|$, and so is every interval with more than one point. The care over $0$s and $9$s is needed. With the rule "replace each diagonal digit $d$ by $9-d$", a list that starts with $0.5000\dots$ and has every later diagonal digit $0$ produces $0.4999\dots$, which is the first number again.

Two consequences follow at once. The irrational numbers are uncountable, since otherwise $ℝ=\mathbb{Q}\cup (ℝ\setminus \mathbb{Q})$ would be a union of two countable sets. And $|\mathbb{N}|<|ℝ|$: the inclusion is an injection, and no bijection exists. So there are at least two infinite sizes.

Now you. Let $S$ be the set of infinite sequences $(t_1,t_2,\dots )$ with every term $0$ or $1$. Prove that there is no surjection $\mathbb{N}\to S$.

Algebraic and transcendental numbers

A real number is algebraic when it is a root of some non-zero polynomial with integer coefficients, and transcendental otherwise. Every rational $\frac{a}{b}$ is algebraic, as a root of $bx-a$. So is $\sqrt{2}$, a root of $x^2-2$, and so is $\sqrt{2}+\sqrt{3}$: if $x=\sqrt{2}+\sqrt{3}$ then $x^2=5+2\sqrt{6}$, so $(x^2-5{)}^2=24$, and $x$ is a root of $x^4-10x^2+1$. Sums and products of algebraic numbers are again algebraic (a theorem of algebra, not needed here), and for a long time nobody knew whether any real number is not.

Theorem (Cantor, 1874). The set of real algebraic numbers is countable. Consequently transcendental numbers exist, and the set of them is uncountable.

Proof. A non-zero polynomial of degree $n$ has at most $n$ real roots, as Mathematical Foundations shows (each root contributes a linear factor). So for each non-zero $q\in \mathbb{Z}[x]$, the set $Z(q)$ of its real roots is finite. The algebraic numbers are the union of the sets $Z(q)$ over all non-zero $q\in \mathbb{Z}[x]$, and $\mathbb{Z}[x]$ is countable by the Example of the previous section, so this is a countable union of finite sets, which is countable by the theorem on countable unions. No choice is involved: each $Z(q)$ is listed in increasing order, and $\mathbb{Z}[x]$ has the explicit list built above.

If the transcendental numbers formed a countable set, then $ℝ$, the union of the algebraic and the transcendental numbers, would be a union of two countable sets, and countable. It is not, so the transcendental numbers are uncountable, and in particular there is at least one. $\square$

The proof is a strange one. It shows that almost every real number is transcendental, in the sense that the transcendental ones are uncountable and the algebraic ones only countable, without identifying a single one. Joseph Liouville had exhibited the first explicit transcendental numbers in 1844, by a quite different argument about how closely algebraic numbers can be approximated by rationals. Charles Hermite proved that $e$ is transcendental in 1873, and Ferdinand von Lindemann did the same for $\pi$ in 1882, which settled the ancient problem of squaring the circle with ruler and compasses: it cannot be done. Cantor's argument, published in 1874, gave existence with no example at all, a non-constructive proof in the sense of the lesson on direct proof.

The count also puts a limit on description. Every number that can be defined by a finite text, in any fixed language, corresponds to at least one finite string of symbols, and there are only countably many such strings. So only countably many real numbers can be defined at all, and almost all real numbers can never be individually named.

Cantor's theorem

The diagonal idea, build an object that disagrees with the $n$th item at the $n$th place, is not about decimals. It works for any set $A$ and its power set.

Theorem (Cantor). For every set $A$, $|A|<|P(A)|$.

Proof. The map $a\mapsto \{a\}$ is an injection $A\to P(A)$, since $\{a\}=\{a\prime \}$ forces $a=a\prime$. So $|A|\le |P(A)|$. It remains to show that no $F:A\to P(A)$ is surjective, and then in particular none is a bijection. Each $F(a)$ is a subset of $A$, which may or may not contain $a$. Collect the elements not in their own image:

This is a subset of $A$. Suppose $D=F(d)$ for some $d\in A$. If $d\in D$, the definition of $D$ gives $d\notin F(d)=D$. If $d\notin D$, then $d\notin F(d)$, which is exactly the condition for $d\in D$. Either way there is a contradiction, so $D$ is not a value of $F$, and $F$ is not surjective. $\square$

For a finite set with $n$ elements this is $n<2^n$. For $\mathbb{N}$ the diagonal is visible: with $F(n)$ as row $n$ of a table whose columns are $1,2,3,\dots$ and whose entries say whether each number is in $F(n)$, the question "is $n\in F(n)$?" reads down the diagonal, and $D$ answers each one the other way. The subsets of $\mathbb{N}$ correspond exactly to the $0$ and $1$ sequences of the last Now you (a set $S$ corresponds to the sequence with $1$ in the places belonging to $S$), and the two proofs are the same proof.

Applied repeatedly, the theorem gives an unending ladder, so there is no largest infinity:

The set $D$ should look familiar. Russell's paradox, from the lesson on sets, concerns the set of all sets that are not members of themselves, and Russell reached it in 1901 by studying this proof: run it on a supposed set of all sets with $F(x)=x$, and $D$ becomes $\{x:x\notin x\}$. Inside a genuine set $A$, the same self-reference yields a theorem rather than a paradox.

The Schröder and Bernstein theorem

For finite sets, injections both ways give equal numbers of elements by the pigeonhole lemma. For infinite sets the corresponding statement is a genuine theorem, and the most useful tool for proving that two sets have the same size.

Theorem (Cantor, Schröder, Bernstein). If there are injections $f:A\to B$ and $g:B\to A$, then there is a bijection $A\to B$.

The difficulty is that neither $f$ nor $g$ need be surjective, and no simple combination of them obviously is. The idea is to use $f$ on part of $A$ and the inverse of $g$ on the rest, and to find the right split. Elements of $A$ outside the image $g(B)$ cannot be handled by $g^{-1}$, so they must use $f$. Then so must anything of the form $g(f(x))$ for such $x$, because otherwise $g^{-1}$ would send it to $f(x)$, which $f$ already hits. Following this requirement round and round gives the set on which $f$ is used.

Proof. Define subsets of $A$ by

and let $C=C_0\cup C_1\cup C_2\cup \cdots$. If $x\in A\setminus C$, then $x\notin C_0$, so $x\in g(B)$, and since $g$ is injective there is exactly one $y\in B$ with $g(y)=x$; write it $g^{-1}(x)$. Define $h:A\to B$ by

$h$ is injective. Let $h(x)=h(x\prime )$ with $x\ne x\prime$. If both are in $C$, then $f(x)=f(x\prime )$, contradicting injectivity of $f$. If neither is, then $g^{-1}(x)=g^{-1}(x\prime )$, and applying $g$ gives $x=x\prime$. If $x\in C$ and $x\prime \notin C$, then $f(x)=g^{-1}(x\prime )$, so $x\prime =g(f(x))$. Now $x\in C_n$ for some $n$, so $x\prime \in g(f(C_n))=C_{n+1}\subseteq C$, a contradiction. The remaining case is the same with $x$ and $x\prime$ exchanged.

$h$ is surjective. Let $y\in B$. If $g(y)\notin C$, then $h(g(y))=g^{-1}(g(y))=y$. If $g(y)\in C$, then $g(y)\in C_n$ for some $n$, and $n\ne 0$ because $g(y)\in g(B)$. So $g(y)\in C_n=g(f(C_{n-1}))$, that is, $g(y)=g(f(x))$ for some $x\in C_{n-1}$. Since $g$ is injective, $y=f(x)$, and since $x\in C$, $h(x)=f(x)=y$. $\square$

Cantor stated the theorem without a proof he was satisfied with. Richard Dedekind proved it in 1887 but did not publish; Felix Bernstein, a nineteen-year-old in Cantor's seminar, proved it in 1897; and Ernst Schröder published a proof at about the same time that was later found to contain a gap. The proof uses no choice at all: every step is determined by $f$ and $g$. Problem 13 of the lesson on order gives a second proof, from a fixed point theorem for power sets.

With the theorem, a bijection no longer has to be built. For the Now you of the section on intervals, the inclusion $(0,1)\to [0,1]$ and the map $x\mapsto \frac{x+1}{3}$, which sends $[0,1]$ into $[\frac{1}{3},\frac{2}{3}]\subseteq (0,1)$, are injections both ways, so $|[0,1]|=|(0,1)|$ in one line.

Example. Prove that $|ℝ|=|P(\mathbb{N})|$.

An injection $P(\mathbb{N})\to ℝ$. Send a set $S\subseteq \mathbb{N}$ to the number $0.d_1{d}_2{d}_3\dots$ with $d_n=1$ if $n\in S$ and $d_n=0$ if $n\notin S$. Different sets give digit strings that differ in some place, and neither string contains a $9$. Two different expansions of the same number must have one ending in $9$s, so these strings name different numbers, and the map is injective.

An injection $ℝ\to P(\mathbb{N})$. Send $x\in ℝ$ to the set $L(x)=\{q\in \mathbb{Q}:q<x\}$. If $x<y$, there is a rational $q$ with $x<q<y$ (the rationals are dense, as the lesson on the real numbers proves), and $q\in L(y)$ while $q\notin L(x)$. So $x\mapsto L(x)$ is an injection $ℝ\to P(\mathbb{Q})$. Let $\phi :\mathbb{Q}\to \mathbb{N}$ be a bijection. Then $T\mapsto \phi (T)=\{\phi (q):q\in T\}$ is a bijection $P(\mathbb{Q})\to P(\mathbb{N})$, with inverse $U\mapsto {\phi }^{-1}(U)$. Composing gives an injection $ℝ\to P(\mathbb{N})$.

By the Schröder and Bernstein theorem, $|ℝ|=|P(\mathbb{N})|$. So the size of the real line is the second rung of Cantor's ladder, and $ℝ$ has the same size as the set of $0$ and $1$ sequences. This size is called the continuum. Since $|\mathbb{N}|<|P(\mathbb{N})|$ by Cantor's theorem, this gives a proof that $ℝ$ is uncountable which uses decimals only for the injection $P(\mathbb{N})\to ℝ$, where no digit $9$ ever appears.

Now you. Prove that $|ℝ\times ℝ|=|ℝ|$: the plane has no more points than the line.

The continuum hypothesis

Two infinite sizes are now in hand: that of $\mathbb{N}$, shared by $\mathbb{Z}$, $\mathbb{N}\times \mathbb{N}$, $\mathbb{Q}$ and the algebraic numbers, and the strictly larger size of $ℝ$, shared by every interval, by the plane and by $P(\mathbb{N})$. Every infinite set of reals met so far has one of these two sizes. In 1878 Cantor asked whether that is always so.

The continuum hypothesis. Every infinite subset of $ℝ$ is either countable or equinumerous with $ℝ$.

Equivalently, assuming the axiom of choice, there is no set $A$ with $|\mathbb{N}|<|A|<|ℝ|$. Cantor believed the hypothesis and spent years trying to prove it. It was the first of the twenty-three problems David Hilbert set out in Paris in 1900 as the challenges for the new century.

The count settles a difference between two number systems that look alike. The rationals and the reals are both ordered and closed under the four operations, and between any two rationals lies another. Yet the rationals can be listed and the reals cannot, so something about the reals is missing from the rationals. Nothing so far has said what: counting shows the difference exists without locating it. The next lesson names it, as a property of least upper bounds called completeness.

Problems

Work each problem on paper before opening anything; for Core and Challenge problems, try the hint before the solution.

Warm-up

1. Give an explicit bijection from $\mathbb{N}$ to each set, and prove that it is one: (a) the even natural numbers; (b) $\{n\in \mathbb{Z}:n\ge -5\}$; (c) $\mathbb{N}\times \{1,2\}$.

2. Using $p(m,n)=T(m+n-2)+m$ with $T(k)=\frac{k(k+1)}{2}$, and the bijection $f:\mathbb{N}\to \mathbb{Z}$ from the lesson: (a) compute $p(5,3)$; (b) find the pair $(m,n)$ with $p(m,n)=20$; (c) find $f^{-1}(-6)$ and $f(10)$.