> "Owen Jacobson" <angrybaldguy@gmail.com> wrote in message > news:2010062819564372407-angrybaldguy@gmailcom... >> On 2010-06-28 02:16:28 -0400, Peter Webb said: >> >>> "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". >> >> 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. >> >>>> Where should we insert the word "computable" (or the term "recursively >>>> enumerable") to arrive at your argument? > > The proof as you have revised it is the proof that the cardinality of a > powerset exceeds that of the set itself, for the special case where the > set is N.
That's all that Cantor's diagonalization proof demonstrates.
> As I have already said several times, I have no problem with that > proof, and no problem with card(P(N)) > card(N), from which the > uncountability of the Reals follows immediately. My problem is with the > standard presentation of Cantor's diagonal argument applied to decimal > expansions.
Ah. So, if we do away with informal wordings[0], your proposition regarding computable reals also disappears? Then I won't think about it any further, as it's obviously not a formal mathematical argument. I'm still interested in the failure of comprehension that lead to your proposition, though.
> This rather unfortunately starts off with a purported "list", and then > proves no such list can exist. However, there are countable subsets of > R which cannot be formed into an explicit list either. Proving that no > explicit list can exist is not the same as proving uncountability.
Various presentations have varying degrees of formality, and some of them are informal enough to use the term "list" without first defining it, or are taken out of context and given without definitions. Invariably[1], the implied or omitted definition of "list of reals" is along the lines of "a function from N to R", without regard to computability or any other notion of being finitely describable.
> I think that you have rather proved my point. You admit that your proof > contains an error
No, I admit that my presentation of it contained an error: specifically, I was not formal enough to avoid specific misunderstandings. I made no changes to the structure of the proof; I only replaced wordings like "we can identify" with more formal phrasings like "there exists".
> and you needed to change your proof to remove the explicit use of the > nth digit of the nth decimal.
I deny making any such change. You have interpreted my original wording in a way that is incompatible with the corrected wording; however, the change was only to remove this source of confusion. Others (thanks, Tim!) in this thread would likely agree that both forms present the same argument, only differing in pedanticness and formality.
Note that the corrected version also explicitly mentions the well, x'th element of L(x) when giving the properties of d. Why does the phrasing
"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)."
not cause you to object, while the phrasing
"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)."
does?
> In its common form, it proves that you cannot from an explicit list of > Reals. This does not immediately mean that the Reals are uncountable; > merely that they are not recursively enumerable.
I don't understand how, given an argument that uses an undefined term ("list"), you would reach the conclusion that it says anything about recursive enumerability. Surely the strongest conclusion you can reach from such an argument is "Therefore, no list contains every real... but what's a list?"
Cheers,
-o
[0] Used, believe it or not, to *ease* comprehension. The best laid plans... [1] Well, actually, I'd be very interested in a published version of this argument where "list" means something incompatible.
