"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". 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: >
I will snip here.
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.
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. 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.
I think that you have rather proved my point. You admit that your proof contains an error, and you needed to change your proof to remove the explicit use of the nth digit of the nth decimal. This is exactly the point that I am making; the common naive presentation of Cantor's diagonal proof has an error. 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. This of course uses concepts that did not exist when Cantor devised his proof, and which almost nobody seeing the decimal diagonal proof for the first time would be aware of.
Cantor's proof that card(P(X)) > card(X) for X non-empty is fine, and his decimal diagonal proof when re-formulated as a special case of that general rule is fine.
