> "Owen Jacobson" <angrybaldguy@gmail.com> wrote in message > news:2010062800145641786-angrybaldguy@gmailcom... >> On 2010-06-27 22:59:12 -0400, Peter Webb said: >>> Thirdly, I already provided a definition of "listable" which is >>> equivalent to being recursively enumerable. If people try and redefine >>> terms to mean something different, then there are going to be >>> misunderstandings. >> >> Then let's do away with the word entirely, for the sake of understanding. >> >> To recap: I believe your point to be that we can add the word >> "computable" to "real" in Cantor's diagonal argument and arrive at the >> conclusion that the computable reals are either uncountable or not >> recursively enumerable (it's unclear which). To do this, you use an >> informal presentation of Cantor's diagonal argument which uses the word >> "list". So, here is an informal presentation of Cantor's diagonal >> argument that avoids the word "list" (as well as a few other common >> verbal shortcuts): >> >> 1. Let S be the set {0, 1}^N. >> 2. For any function L from N to S, we can identify an element of S not >> in the image of L. >> 3. To do so, we identify an element d of S that is the diagonal of L: >> for every natural number x, the x'th element of d is equal to the x'th >> element of L(x). >> 4. Given d, we can identify an element d' of S that is the >> anti-diagonal of L: for every natural number x, the x'th element of d' >> is 1 if the x'th element of d is 0 and is 0 if the x'th element of d is >> 1. >> 5. Since for every natural number x, L(x) differs from d' at the x'th >> place, d' is not in the image of L. >> 6. Therefore no function from N to S is surjective. >> >> Where should we insert the word "computable" (or the term "recursively >> enumerable") to arrive at your argument? >> > > Hmmm. This proof assumes that the function L is in fact computable, and > that the function can be explicitly defined. > > This occurs in step 4. You state we can "identify an element d of S > that is on the diagonal".
As Tim pointed out, I misspoke there. Here is a revised version with that error corrected:
1. Let S be the set {0, 1}^N. 2. For any function L from N to S, there exists an element of S not in the image of L. 3. There exists an element d of S with the following property: for every natural number x, the x'th element of d is equal to the x'th element of L(x). 4. Since d exists, there also exists an element d' of S with the following property: for every natural number x, the x'th element of d' is 1 if the x'th element of d is 0 and is 0 if the x'th element of d is 1. 5. Since for every natural number x, L(x) differs from d' at the x'th place, d' is not in the image of L. 6. Therefore no function from N to S is surjective.
> However, in answer to your question, I would insert the word > "computable" before the word "function" in step 2.
This gives us the following altered argument:
1. Let S be the set {0, 1}^N. 2. For any *computable* function L from N to S, there exists an element of S not in the image of L. 3. Note that there exists an element d of S with the following property: for every natural number x, the x'th element of d is equal to the x'th element of L(x). 4. Since d exists, there also exists an element d' of S with the following property: for every natural number x, the x'th element of d' is 1 if the x'th element of d is 0 and is 0 if the x'th element of d is 1. 5. Since for every natural number x, L(x) differs from d' at the x'th place, d' is not in the image of L. 6. Therefore no *computable* function from N to S is surjective.
Since the computable functions from N to S are a subset of the functions from N to S, this argument is sound, if uninteresting -- the conclusion also follows more simply from the more general argument. However, I believe you also wish to reach a different conclusion. What else should we change?
>> (Of course, if you *really* want to be picky, we can dig up Georg's own >> paper on the subject.) >> > > The problem I have is with the standard/common presentation of Cantor's > diagonal proof using digits.
We can re-frame the argument above in terms of functions from N to the set S' = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}^N fairly easily. Doing so doesn't change the proof, other than making the specifications in steps 3 and 4 above slightly more complicated. It's also possible to prove that |S| = |S'|.
> This starts with a purported "list", and explicitly uses the values of > each item in the list. It then proves no such list can exist.
No. It proves that no list of reals can *be complete* (or, rather, that no function from N to S, or from N to R, can be surjective). Infintely many lists of reals (functions from N to R) exist.
