"Owen Jacobson" <firstname.lastname@example.org> wrote in message news:2010062100324493978-angrybaldguy@gmailcom... > On 2010-06-19 22:31:56 -0400, Peter Webb said: > >> Cantor's original proof requires the list to be provided in advance > > No, it does not. It's an existence proof showing that: > > IF a list of reals L(x) (where L : N -> R) exists, THEN a real A_L exists > such that for every natural number n, L(n) ? A_L. > > Or, equivalently, showing that: > > For every function L from N to R, there exists a real r not in the image > of L. > > Being a constructive proof, it's usually *presented* as if it were an > algorithm or a procedure, but it's only for ease of comprehension.
Umm, I am talking about Cantor's proof as it is generally presented, and in that case it is an explicit algorithm.
> Unfortunately, that seems to have backfired on you. >
So you are saying that Cantor's proof in its usual form is incorrect, as it pretends to include an algorithmic process for computing the anti-diagonal?
> -o > > Incidentally, "countable" and "listable" mean the same thing in > conventional set theories: an infinite set S is countable if and only if > there exists an surjective function f from N to S. Since a "list" of > elements of S is most easily formalized as a surjective function from N to > S, denying that S is listable is equivalent to denying that it is > countable. >
The existence of a surjective function from N to S proves it is countable.
The ability to prepare a list of exactly the elements proves the list is recursively enumerable.
If you cannot form the list, you have proved that it is not recursively enumerable. This is a somewhat weaker condition that it being uncountable.