# A hardly convincing proof in Petzold's “The Annotated Turing”

There's one thing in Chapter 2 I can't follow.

Petzold is talking about the Continuum Hypothesis. Before that, he proves that $|\mathbb{R}| = 2^{\aleph_0}$.

I'm now going to summarize the proof (but there must be something I didn't catch - I didn't understand it - so perhaps I'll miss something).

The general rule is that:

$\textrm{cardinality of a power set} = 2^{\textrm{cardinality of the original set}}$

Here what happens if we construct the power set of the natural numbers.

We must find some order in our operations. The infinite sequence of natural numbers is set as a header. Then, for each row, we put 0s or 1s depending on whether the corresponding number is in the current element of the power set.

0 1 2 3 4 5 ... Subset
0 0 0 0 0 0 ... {}
1 0 0 0 0 0 ... {0}
0 1 0 0 0 0 ... {1}
1 1 0 0 0 0 ... {0,1}


And so on. Proceeding like that we construct every possible infinite sequence of 0s and 1s, each one corresponding to one element of the powerset of $\mathbb{N}$.

If these sequences of symbols are interpreted as binary encodings of real numbers (like $100000… \rightarrow .100000…$), then they are all the real numbers between 0 and 1.

Since this set can be put in correspondence with the entire set of real numbers, it follows that the cardinality of $\mathbb{R}$ and the cardinality of the powerset of $\mathbb{N}$ are the same.

In a footnote, Petzold says that one must not believe that we found a way to enumerate all reals, because there are no transcendental numbers in the set. That is true, Petzold says, because "each number has a finite number of 1s after the period".

I'm sure that is true, but didn't we just say that we listed all real numbers? Isn't "all real numbers between 0 and 1 except for the transcendental numbers" a different set?

This is what I find not very convincing.

• Are you sure he is referring to the power set of the naturals in the footnote and not just the set of finite subsets? Perhaps he is referring to only those numbers with a finite number of 1s in the footnote because he is giving a very brief counter example. – Dan Robertson Sep 26 '16 at 20:58
• I would say he is referring to the entire list I described: "It may also seem as if we've stumbled on a method to enumerate all the real numbers between 0 and 1. The pattern is already evident - the first digit after the period alternates between 0 and 1, the second digit alternates at half the speed, and so on - and we could easily continue the list as long as we want. The fallacy, however, is that the list will never contain a transcendental number. Every number in the list has a finite number of non-zero digits after the period" – larsen Sep 26 '16 at 21:05
• I disagree, where he writes "Every number in the list has a finite number of non-zero digits after the period" I think the list he refers to is the list one would get by continuing the pattern and not the hypothetical list (as it isn't really a list) of all the real-number representations of subsets of the naturals. In particular if you follow the interpretation I have given then the footnote is a correct sketched proof the fact that this isn't an enumeration of the naturals. – Dan Robertson Sep 26 '16 at 21:11

## 1 Answer

What he was trying to get at is that for a real number like $\pi -3$ (or for that matter even for a number like $\frac13$), no particular index (row of that table) gives you the real number $\frac13$ because every row has a "last" $1$. So we have not enumerated the reals.

But we have placed the reals into a one to many relationship with the power set of the integers, because for any real (or at least any real $x$ on $[0,1)$), you can form the set that includes $n$ if and only if the binary representation of $x$ has a $1$ in the $n$-th bit. It is one to many because some real numbers have two different binary representations; for instance, $\frac12 = 0.0111111\ldots = 0.1000000\ldots$.

What I don't like is him saying that "it follows that" the cardinality of the reals is the same as that of the power set of the integers. Of course that does not follow; it follows that the cardinality of the reals is no greater than that of the power set of the integers. But it is easy to fix that flaw and demonstrate the that equality statement, since there are but a countable set of reals with multiple binary representations.

• Thank you. This answer and Dan's comments help a lot. – larsen Sep 26 '16 at 21:13
• You could also ask where the binary representation of 1/3 appears on the list. – DanielWainfleet Oct 18 '16 at 19:33