"Owen Jacobson" <angrybaldguy@gmail.com> wrote in message news:2010063022395694615-angrybaldguy@gmailcom... > On 2010-06-29 04:33:09 -0400, Peter Webb said: > >> "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?
What proposition are you referring to?
> 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.
Without you saying what the proposition was, obviously I can't respond.
> >> 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. >
Excepting that the standard presentation of Cantor's proof - and indeed your first attempt at reformulating it - does assume the list is known in advance sufficiently well that we can explicitly identify the nth digit of the nth item.
>> 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.
What is the difference between a "proof" and a "presentation of a proof" ? Do proofs have some kind of fixed existence independent of their presentation?
> 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". >
Indeed, you changed your proof (or your presentation of the proof, if that is somehow a different thing) to eliminate exactly the problem I identified with the standard presentation of Cantor's proof.
Given that you made and acknowledged exactly the same error as I identified in other presentations of Cantor's proof, it seems bizarre that you would attempt to claim the error doesn't occur - you yourself made the error, admitted it was an error, and posted a new version without the error.
>> 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.
Gee, as if I hadn't explained the connection a thousand times already.
And you yourself made exactly the same error.
Cantor's digit proof in its standard form:
1. Explicitly uses the value of the nth digit of the nth element, as you yourself did in your first go.
2. Proves that nobody can generate a list of all Reals. This does not prove uncountability; it proves that the Reals cannot be recursively enumerated. You can't form a list of all uncomputable Reals either, but they are countable.
> Surely the strongest conclusion you can reach from such an argument is > "Therefore, no list contains every real... but what's a list?" >
Well, we know what a "list" is Cantor's standard proof, because of the properties that are assumed for the list.
A list is a mapping from N -> R such that the nth digit of the nth item is known.
