Uncountable sets - Why is the following proof false?

248 Views Asked by At

Let $S$ be any subset of the natural numbers. Then the sum

$$ \sum_{n \in S} \frac{1}{2^n} $$

converges against a unique value for each subset $S$. This sum yields a computable number because it is possible to compute it digit by digit. Therefore, these sums map every subset of $\mathbb{N}$ to a unique computable number.

This is a contradiction because the set of all subsets of $\mathbb{N}$ is uncountable but the computable numbers are countable.

Where is the error here?

1

There are 1 best solutions below

2
On BEST ANSWER

Given a subset $S \subseteq \mathbb{N}$, there may not be an algorithm to compute whether an arbitrary $n \in \mathbb{N}$ is in $S$. Therefore, you can't actually compute it digit by digit. In fact, your argument shows that there can't always be an algorithm for deciding this problem.

Edit:

Say that a function $f : \mathbb{N} \to \mathbb{N}$ is "computable"' iff there is a Turing machine which takes as input a binary number and always halts with a binary number on the tape. Note that this is equivalent to many other definitions of "computable" - for example, that $f$ is general recursive, computable in $\lambda$-calculus, that $f$ can be coded in Haskell (or most any programming language), etc. In some literature, the term used is "recursive".

Consider some $S \subseteq \mathbb{N}$. $S$ is said to be "decidable" if there is a computable function $f$ such that for all $n$, $f(n) = 0$ if $n \notin S$ and $f(n) = 1$ if $n \in S$. We say that such an $f$ is the "characteristic function" of $S$. In some literature, the term used is "recursive set".

There are some sets $S \subseteq \mathbb{N}$ which are not decidable. This doesn't mean that some particular human can't decide whether some $n$ is in $S$ or not; it means that no "algorithm" (Turing machine) can take as input a number $n$ and output whether or not $n \in S$.

We say that a function $f : \mathbb{N} \to \mathbb{Z}$ is computable if there are computable functions $g, h : \mathbb{N} \to \mathbb{N}$ such that for all $n$, $f(n) = g(n) - h(n)$.

Similarly, we say that a function $f : \mathbb{N} \to \mathbb{Q}$ is computable if there are computable functions $g, h : \mathbb{N} \to \mathbb{Z}$ such that for all $n$, $f(n) = g(n) / h(n)$.

Finally, we say that a real number $x$ is computable if there is some computable $f : \mathbb{N} \to \mathbb{Q}$ such that for every $n$, $|f(n) - x| \leq 1/(n + 1)$. We say $f$ computes $x$ in this case.

Not every real number is computable. In particular, it can be shown that $x_S = \sum\limits_{n \in S} \frac{1}{3^n}$ is computable iff $S$ is decidable. For if $S$ is decidable, let $g$ be its characteristic function and define $f(n) = \sum\limits_{i = 0}^n \frac{g(n)}{3^n}$; then $f$ computes $x$. And if $x_S$ is computable, let $g$ be a function that computes $x$. Then by computing $g(3^{n + 2})$, we get close enough to $x_S$ to determine its base-3 expansion up to the $n$th place after the "decimal" point, so we can compute whether this place has a zero (in which case $n \notin S$) or a 1 (in which case $n \in S$).

Since the set of all Turing machines is countably infinite, so too is the set of decidable subsets of $\mathbb{N}$. But the collection of all subsets of $\mathbb{N}$ (that is, the power set of $\mathbb{N}$) is well known not to be countable. Therefore, there must exist some $S$ which is not decidable. In this case, $x_S$ is not a computable number. There is no algorithm at all that can list its digits one at a time. It's not a matter of humans being too stupid to come up with one; it's simply impossible to do so.

A specific example of such an $S$ can be given as follows: suppose given an enumeration of all Turing machines. Let $S = \{n \in \mathbb{N}: $ the $n$th Turing machine halts on the input of $0\}$. The fact that $S$ cannot be dedicable is a corollary of (and equivalent to) the famous "Halting Problem".