> "Owen Jacobson" <angrybaldguy@gmail.com> 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?
I am saying that interpreting it as an algorithm is less useful as a mental model than interpreting it as a description of the properties of some real number (well, actually, some infinte sequence of zeroes and ones) that must exist for any list of reals (of infinite sequences of zeroes and ones, likewise). The phrase "for each" is a verbalism for the universal quantifier, not an instruction to perform some operation.
In fact, considering your unusual definition of "list" (discussed further below), I'd like to clarify that even further and avoid the word "list" entirely: Cantor's proof demonstrates that, for every function L from N to {0, 1}^N, there exists an element of {0, 1}^N that is not in the image of L. Since this directly implies that no function from N to {0, 1}^N can be surjective, it proves that the set {0, 1}^N is uncountable.
There is a bijection between the set {0, 1}^N and the power set of N, and there is are bijections between either of those sets and the set of real numbers, so those two sets are also uncountable.
>> 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 that's what you mean by list, then this whole subthread may well be a simple misunderstanding. "A recursive enumeration" is not what anyone else in the thread means by "a list": we're all talking about totally arbitrary functions from N to some set, without any regard to computability. However, it's fairly well established that the set of computable reals is not recursively enumerable.
Just so that I'm clear, do you agree that there exists a surjective function from N to the computable reals?
