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 sets of numbers by order, closed on the least upper bound, and left a prior question: how many reals are there? This lesson answers it with functions alone, assuming injective, surjective and bijective maps, inverses, and the fact that composites of injections (or bijections) are injections (or bijections). As throughout the course, $ℕ = {1, 2, 3, \dots}$ starts at $1$ .

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$ have the same size, written $| A | = | B |$ , when there is a bijection $A \to B$ . And $| A | \leq | 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 an injection exists and a bijection does not. Identities, inverses and composites make "same size" reflexive, symmetric and transitive.

For finite sets the definition agrees with counting. A set has $n$ elements when it is in bijection with ${1, 2, \dots, n}$ . The lesson on functions counted the injections from an $m$ -element set to an $n$ -element set as $n (n - 1) \dots (n - m + 1)$ , which is $0$ when $m > n$ . That is the pigeonhole principle: more than $n$ pigeons in $n$ holes put two in some hole. So no set has both $m$ and $n$ elements with $m < n$ , since one bijection followed by the inverse of the other would inject ${1, \dots, n}$ into ${1, \dots, m}$ . Two finite sets have the same size exactly when they have the same number of elements.

It also shows that a finite set is never the same size as a proper subset of itself, which has at most $n - 1$ elements when the set has $n$ . Richard Dedekind turned this round in 1888 and defined an infinite set as one that is the same size as a proper subset of itself.

Hilbert's hotel

David Hilbert gave the idea 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 : ℕ \to ℕ ∖ {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 $ℕ ∖ {1}$ has $k \geq 2$ , so $k - 1 \in ℕ$ and $s (k - 1) = k$ . So $| ℕ ∖ {1} | = | ℕ |$ , and by Dedekind's definition $ℕ$ is infinite.

When a coach brings a guest for every natural number, moving each guest from room $n$ to room $2 n$ frees the odd rooms for them, so $ℕ$ 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 the pigeonhole principle and false for infinite ones.

Countable sets

A set is countable when it is finite or the same size as $ℕ$ , and uncountable otherwise. A bijection $g : ℕ \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 $ℵ_{0}$ for the size of $ℕ$ . Starting $ℕ$ at $0$ instead changes nothing, since the hotel's shift is a bijection between the two versions.

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 : ℕ \to ℤ$ , 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 $ℤ$ 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} \geq 1$ , while for odd $n$ , $f (n) = \frac{1 - n}{2} \leq 0$ because $n \geq 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 ℤ$ . If $k \geq 1$ , put $n = 2 k$ , an even natural number, and $f (n) = k$ . If $k \leq 0$ , put $n = 1 - 2 k$ , which is odd and at least $1$ , so $n \in ℕ$ , and $f (n) = \frac{1 - (1 - 2 k)}{2} = k$ . Hence $f$ is a bijection and $| ℤ | = | ℕ |$ .

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

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

Answer

For even $n$ , $g (n) = \frac{n}{2} \geq 1$ , and for odd $n$ , $g (n) = - \frac{n + 1}{2} \leq - 1$ , a nonzero integer. Injective: $g (m) = g (n)$ forces equal parity, since only even inputs give positive values, and then $\frac{m}{2} = \frac{n}{2}$ or $- \frac{m + 1}{2} = - \frac{n + 1}{2}$ gives $m = n$ . Surjective: let $k \neq 0$ . If $k \geq 1$ , then $n = 2 k$ is even and $g (n) = k$ . If $k \leq - 1$ , then $n = - 2 k - 1$ is odd and at least $1$ , and $g (n) = - \frac{- 2 k - 1 + 1}{2} = k$ . So $g$ is a bijection, listing $- 1, 1, - 2, 2, \dots$

Pairs of natural numbers

The set $ℕ \times ℕ$ 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:

(1, 1), (1, 2), (2, 1), (1, 3), (2, 2), (3, 1), (1, 4), \dots

Each pair lies on exactly one diagonal, and each diagonal is finite, so every pair appears once and is reached after finitely many steps.

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

p (m, n) = \frac{(m + n - 2) (m + n - 1)}{2} + m

This is the Cantor pairing function, shifted so that $ℕ$ starts at $1$ : a polynomial that is a bijection $ℕ \times ℕ \to ℕ$ , because the list visits every pair once and fills every position. It gives $p (1, 1) = 1$ , $p (1, 2) = 2$ , $p (2, 1) = 3$ and $p (3, 5) = \frac{6 \cdot 7}{2} + 3 = 24$ , and on the $1770$ pairs with $m + n \leq 60$ it returns $1$ to $1770$ , each once. So $ℕ \times ℕ$ is countable.

The rationals

Between two rationals lies their average, so $ℚ$ cannot be listed in increasing order. It can be listed in another, and the quickest proof uses a theorem that turns two injections into a bijection.

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

So $| A | \leq | B |$ and $| B | \leq | A |$ give $| A | = | B |$ . Cantor stated the theorem in 1887 and Felix Bernstein, a student in his seminar, proved it in 1897. The proof is left to a later course.

Example. Prove that $ℚ$ is countable.

Every rational has exactly one form $\frac{a}{b}$ in lowest terms with $a \in ℤ$ and $b \in ℕ$ . With $f$ the bijection $ℕ \to ℤ$ above, define $h : ℚ \to ℕ \times ℕ$ 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 : ℚ \to ℕ$ is a composite of injections, hence an injection, and $n \mapsto n$ injects $ℕ$ into $ℚ$ . By Schröder and Bernstein, $| ℚ | = | ℕ |$ .

For instance $- \frac{3}{4}$ goes to $(7, 4)$ and then to $p (7, 4) = \frac{9 \cdot 10}{2} + 7 = 52$ . Position $p (4, 2) = 14$ is skipped, since $(4, 2)$ would stand for $\frac{2}{2}$ , which is not in lowest terms; that is why the theorem is needed.

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

Answer

Let $G (a, b) = (f^{- 1} (a), f^{- 1} (b))$ from $ℤ \times ℤ$ to $ℕ \times ℕ$ , and $H (m, n) = (f (m), f (n))$ . Since $f$ and $f^{- 1}$ undo each other in each coordinate, $H \circ G$ and $G \circ H$ are identities, so $G$ has an inverse and is a bijection. Then $F = p \circ G$ is a composite of bijections, hence a bijection, and $ℤ \times ℤ$ is countable. With $f^{- 1} (- 1) = 3$ and $f^{- 1} (2) = 4$ , $F (- 1, 2) = p (3, 4) = \frac{5 \cdot 6}{2} + 3 = 18$ .

Cantor's diagonal argument

Georg Cantor showed 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.

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:

$n$	$x_{n}$	expansion	$n$ th digit	new digit
1	$π - 3$	0.1415926...	1	5
2	$e - 2$	0.7182818...	1	5
3	$\sqrt{2} - 1$	0.4142135...	4	5
4	$\frac{1}{2}$	0.5000000...	0	5
5	$\sqrt{3} - 1$	0.7320508...	5	4
6	$\ln 2$	0.6931471...	7	5

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 $ℕ \to (0, 1)$ .

Let $g : ℕ \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 \leq y \leq 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)$ , which is plainly not finite, is uncountable. So is $ℝ$ : a bijection $ℝ \to ℕ$ would inject $(0, 1)$ into $ℕ$ , while $n \mapsto \frac{1}{n + 1}$ injects $ℕ$ into $(0, 1)$ , and Schröder and Bernstein would make $(0, 1)$ countable. 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.

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 $ℕ \to S$ .

Answer

Let $g : ℕ \to S$ be any function, with $g (n) = (t_{n, 1}, t_{n, 2}, \dots)$ . Define $u$ by $u_{n} = 1 - t_{n, n}$ , so each $u_{n}$ is $0$ or $1$ and $u \in S$ . For every $n$ , $u_{n} \neq t_{n, n}$ , so $u$ and $g (n)$ differ in term $n$ and $u \neq g (n)$ . Hence $u$ is not a value of $g$ , and $g$ is not surjective. No trap arises here, because two sequences are equal only when every term agrees.

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 $P (A)$ , the set of all subsets of $A$ .

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

The map $a \mapsto {a}$ is an injection $A \to P (A)$ , since ${a} = {a^{'}}$ forces $a = a^{'}$ . It remains to show that no $F : A \to P (A)$ is surjective. Each $F (a)$ is a subset of $A$ , which may or may not contain $a$ . Collect the elements not in their own image:

D = {a \in A : a \notin F (a)}

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 $F$ is not surjective, there is no bijection, and $| A | < | P (A) |$ .

For a finite set this is $n < 2^{n}$ . For $ℕ$ the diagonal is visible: with $F (n)$ as row $n$ , the question "is $n \in F (n)$ ?" reads down the diagonal, and $D$ answers each one the other way. Applied repeatedly, the theorem gives an unending ladder, so there is no largest infinity:

| ℕ | < | P (ℕ) | < | P (P (ℕ)) | < \dots

The set $D$ should look familiar. Russell's paradox, from the lesson on sets, is 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 continuum hypothesis

Two infinite sizes are now in hand: that of $ℕ$ , shared by $ℤ$ , $ℕ \times ℕ$ and $ℚ$ , and the strictly larger size of $ℝ$ . In 1878 Cantor asked whether anything lies between: is every infinite set of reals either countable or the same size as $ℝ$ ? He believed so, and the claim is the continuum hypothesis, first on Hilbert's list of problems in 1900. Kurt Gödel showed in 1940 that it cannot be disproved from the usual axioms of set theory, and Paul Cohen showed in 1963 that it cannot be proved from them either. The axioms the rest of mathematics runs on do not decide it.

The count does settle 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.