# Can uncountable be defined as unable to be generated by any algorithm

I'm trying to describe the concept of uncountable to someone with even less knowledge of math than myself ;-). I came up with the idea that for any countable set, $S$, you could create an algorithm $A$, such that for any proper subset $T$ of $S$, you could generate all elements of $T$ in a finite number with a sufficient number of iterations of $A$, but that for an uncountable set, there is no such algorithm that could do this for every proper subset.

Is this a valid statement?

• No, not every subset of a countable set can be generated by an algorithm. Apr 1, 2017 at 2:32
• What if you take an infinite proper subset $T \subset \{s_1, s_2, s_3, ...\}$? How do you generate an infinite number of elements in finite time? On the other hand, for any finite subset $T$ you can just list the elements of $S$ and stop once all elements of $T$ have appeared. Apr 1, 2017 at 3:31
• @MarkVY How do you list the countable set of all Turing machines that do not halt on the empty string? Apr 1, 2017 at 5:40
• @MarkVY Your comments here are wrong in a number of ways. Your first comment asserts that every countable set is recursively enumerable (we can write an algorithm to list the elements), which is false. It also says that there is no algorithm that lists all the real numbers, but it's not even clear what it means to "list" even a single real number that's, e.g., transcendental. Your second comment says that any set which is not recursive cannot be recursively enumerable, but this is also false. Apr 1, 2017 at 11:28
• @MarkVY The halting problem $H$ is a good example of this: we can enumerate it (put $e$ into $H$ when we see the $e$th Turing machine halt on input $e$), but we can't co-enumerate it (how do you know the $e$th Turing machine on input $e$ will never halt? no matter how long you wait, maybe it halts in "just one more step"). Apr 3, 2017 at 13:00

There are uncountably many subsets of $\Bbb N$ (and all these subsets are countable). But there are only countably many algorithms. Hence you cannot describe all these sets by an algorithm.
On the other hand, there are real numbers that cannot be described by an algorithm (again, because there are more real numbers than algorithms). For such a number $\alpha$, already the singleton set $\{\alpha\}$ is problematic for your approach.
• @brianmearns Since there are uncountably many subsets of $\mathbb{N}$, and only countably many computer programs, "most" subsets of $\mathbb{N}$ don't have corresponding computer programs. Apr 3, 2017 at 12:43