# Uncountable sets - Why is the following proof false?

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?

• Not every real number is computable. Indeed, not every subset $S$ of $\mathbb{N}$ is recursive. – user10354138 Jul 28 at 2:42
• Surely the sum is only computable if it’s decidable whether $n \in S$ for each $n$. – mjqxxxx Jul 28 at 2:45
• Are you sure that it is always possible to compute digit-by-digit the result of the sum $\sum_\limits{n \in S} \frac{1}{2^n}$ even if $S$ is the subset of primes numbers? – Angelo Jul 28 at 2:51
• Next time, edit, don't delete. – Asaf Karagila Jul 28 at 11:03
• Sorry, @asaf-karagila. Most comments didn’t make any sense anymore after the edit because they discussed if the previous sum actually yields unique values. Also there was no answer yet. That’s why I thought it’s better to create a new, clean question. But if this is against the community rules, I’ll just edit the question next time. – LinusK Jul 28 at 19:32

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".

• Such subsets seem very strange. Not being able to determine if an element is contained in a set feels like it contradicts the very definition of what a set actually is. But you’re right. Sets can have an undecidable member relation. Though how can you determine if $S$ is actually a subset of $\mathbb{N}$ if the member relation is not decidable? Because the subset relation is defined using the member relation: “If all the members of set A are also members of set B, then A is a subset of B” – LinusK Jul 28 at 19:42
• Why does it even matter if I can compute if some $n$ is in $S$? Isn’t it enough to show that for any given $S$ there is a corresponding computable number? – LinusK Jul 29 at 0:15