Some infinities are bigger
Tonight's idea
How do you compare the sizes of two sets without counting? Pair them off. If every seat has a person and nobody is standing, there are as many people as seats. Cantor, in the 1870s, took this seriously for infinite sets: two sets have the same size if their members can be matched one-to-one with nothing left over.
\(n \leftrightarrow 2n\) matches the whole numbers with the even numbers, nothing left out on either side. For infinite sets, a part can be as big as the whole. (That is the trick behind Hilbert's hotel.) A set that can be matched with \(\{1, 2, 3, \ldots\}\) is countable: you can list its members so every one eventually appears. The integers are countable: \(0, 1, -1, 2, -2, \ldots\). Even the fractions are countable: lay them out in a grid and walk the diagonals.
Cantor's shock: the real numbers between 0 and 1 are not. Suppose someone hands you a list claiming to contain them all:
\(r_1 = 0.\mathbf{3}1415\ldots\quad r_2 = 0.5\mathbf{0}000\ldots\quad r_3 = 0.12\mathbf{3}45\ldots\quad \cdots\)
Build \(d\) from the diagonal: if the \(n\)-th digit of \(r_n\) is 5, make the \(n\)-th digit of \(d\) a 6, otherwise a 5. Here \(d = 0.555\ldots\). Then \(d\) differs from every \(r_n\) in the \(n\)-th digit, so it is not on the list. No list can be complete. The reals are uncountable: a strictly bigger infinity. (Using only 5s and 6s avoids numbers like \(0.4999\ldots = 0.5\) that have two decimal forms.)
Watch one: numbering the fractions
Along each diagonal \(p + q = d\), read \(\tfrac{p}{q}\) with \(p = 1, 2, \ldots, d-1\), skipping anything not in lowest terms. \(d = 2\): \(\tfrac11\). \(d = 3\): \(\tfrac12, \tfrac21\). \(d = 4\): \(\tfrac13\), skip \(\tfrac22\), \(\tfrac31\). \(d = 5\): \(\tfrac14, \tfrac23, \tfrac32, \tfrac41\). \(d = 6\): \(\tfrac15, \tfrac51\). Every diagonal is finite, so every fraction gets a number: \(\tfrac23\) is number 7.
Your turn
- Write pairings showing that the multiples of 5 and the perfect squares are each the same size as \(\{1, 2, 3, \ldots\}\). Then say in one sentence why "a part can be as big as the whole" is not a contradiction.
- Continue the diagonal numbering. Which number does \(\tfrac25\) get?
- Here is a list that claims to contain every real number in \((0, 1)\): \[0.14159\ldots,\quad 0.50000\ldots,\quad 0.33333\ldots,\quad 0.75250\ldots,\quad 0.66666\ldots,\quad \ldots\] Write down the first five digits of a number guaranteed not to be on it, using the 5-or-6 rule.
- Consider every finite string of letters, digits and punctuation: every sentence, book and formula that could ever be written. Show this set is countable (order by length, then alphabetically). Combine with Cantor's result: what does this say about how many real numbers can ever be described by a sentence or formula?
Stretch: no biggest infinity
Let \(P(S)\) be the set of all subsets of \(S\). Suppose \(f\) pairs each \(x \in S\) with a subset \(f(x)\) and hits every subset. Let \(D = \{x : x \notin f(x)\}\), the set of those \(x\) that are not members of their own subset \(f(x)\) (\(\in\) means "is a member of"). Pick \(y\) with \(f(y) = D\). Is \(y \in D\)? Follow both possibilities. What does this say about \(P(S)\) versus \(S\)?
Answers
- \(n \leftrightarrow 5n\) and \(n \leftrightarrow n^2\). No contradiction: "same size" was defined as "can be paired off", and for infinite sets that does not imply "no proper part can be paired with the whole". That is a property of finite sets, not a law of logic.
- Numbers 1 to 6: \(\tfrac11, \tfrac12, \tfrac21, \tfrac13, \tfrac31, \tfrac14\); 7 to 11: \(\tfrac23, \tfrac32, \tfrac41, \tfrac15, \tfrac51\); 12 to 17: \(\tfrac16, \tfrac25, \tfrac34, \tfrac43, \tfrac52, \tfrac61\). So \(\tfrac25\) is number 13.
- Diagonal digits are \(1, 0, 3, 5, 6\), so the rule gives \(0.55565\ldots\) It differs from entry \(n\) in digit \(n\).
- With an alphabet of \(A\) symbols there are \(A^L\) strings of length \(L\), finitely many. List length 1, then 2, then 3, and so on; every string appears at a finite position. Each description pins down at most one real, so only countably many reals can ever be described, named or computed. The reals are uncountable, so almost every real number is one that no sentence, formula or program can ever single out.
Stretch. If \(y \in D\) then by definition \(y \notin f(y) = D\). If \(y \notin D\) then \(y\) passes the test, so \(y \in D\). Both fail, so no \(y\) has \(f(y) = D\): every pairing misses a subset, and \(P(S)\) is strictly bigger than \(S\). Apply it again to \(P(S)\), and again: there is no largest infinity.