7
$\begingroup$

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?

$\endgroup$
10
  • 4
    $\begingroup$ No, not every subset of a countable set can be generated by an algorithm. $\endgroup$ Apr 1, 2017 at 2:32
  • 1
    $\begingroup$ 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. $\endgroup$
    – Michael
    Apr 1, 2017 at 3:31
  • 3
    $\begingroup$ @MarkVY How do you list the countable set of all Turing machines that do not halt on the empty string? $\endgroup$ Apr 1, 2017 at 5:40
  • 1
    $\begingroup$ @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. $\endgroup$ Apr 1, 2017 at 11:28
  • 1
    $\begingroup$ @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"). $\endgroup$ Apr 3, 2017 at 13:00

1 Answer 1

16
$\begingroup$

No.

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.

$\endgroup$
7
  • $\begingroup$ Can you point to a resource regarding this definition of algorithm? I come from CS background and I think the definition in my head is too flimsy for this to make sense. Thanks! $\endgroup$
    – Reed Spool
    Apr 1, 2017 at 6:03
  • 1
    $\begingroup$ It doesn't really matter how you define an algorithm. There are only countably many strings in the English language; as long as each string in the English language defines at most countably many algorithms, and each algorithm is described by some English string, there are only countably many algorithms. $\endgroup$ Apr 1, 2017 at 8:33
  • $\begingroup$ Here, presumably "algorithm" is being used in the sense of computability. Almost all definitions turn out to be equivalent (Turing Machines, register machines etc). This equivalence is known as Church's Thesis. It's not and can't be a theorem, but in practical terms this seems to be how it is. $\endgroup$ Apr 1, 2017 at 8:37
  • 1
    $\begingroup$ @ReedSpool The conventional definition in CS is that "algorithm" means "Turing machine". $\endgroup$ Apr 1, 2017 at 11:23
  • 1
    $\begingroup$ @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. $\endgroup$ Apr 3, 2017 at 12:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .