5
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ Not every real number is computable. Indeed, not every subset $S$ of $\mathbb{N}$ is recursive. $\endgroup$ – user10354138 Jul 28 at 2:42
  • 3
    $\begingroup$ Surely the sum is only computable if it’s decidable whether $n \in S$ for each $n$. $\endgroup$ – mjqxxxx Jul 28 at 2:45
  • $\begingroup$ 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? $\endgroup$ – Angelo Jul 28 at 2:51
  • $\begingroup$ Next time, edit, don't delete. $\endgroup$ – Asaf Karagila Jul 28 at 11:03
  • $\begingroup$ 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. $\endgroup$ – LinusK Jul 28 at 19:32
10
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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” $\endgroup$ – LinusK Jul 28 at 19:42
  • $\begingroup$ 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? $\endgroup$ – LinusK Jul 29 at 0:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.