Why can no one in sci.math understand my simple point?
in [Logic]
|
From: Virgil on 28 Jun 2010 13:55 In article <slrni2gr79.jrj.tim(a)soprano.little-possums.net>, Tim Little <tim(a)little-possums.net> wrote: > On 2010-06-28, Virgil <Virgil(a)home.esc> wrote: > > It does not require that any element in the listing be known, but > > correctly tells what to do for any listing > > I think that is even a bit too informal for Peter. The phrase "tells > what to do" is superfluous, all that is mathematically required is > that existence of an antidiagonal sequence for each list is proven. > He's going to latch onto "tells what to do" and think that it means > that there is an algorithm for everything involved. There are certainly simple algorithms for finding up to countably many antidiagonals to any given list of reals or of binary sequences.
From: Owen Jacobson on 28 Jun 2010 19:27 On 2010-06-28 05:35:37 -0400, Tim Little said: > On 2010-06-28, Virgil <Virgil(a)home.esc> wrote: >> It does not require that any element in the listing be known, but >> correctly tells what to do for any listing > > I think that is even a bit too informal for Peter. The phrase "tells > what to do" is superfluous, all that is mathematically required is > that existence of an antidiagonal sequence for each list is proven. > He's going to latch onto "tells what to do" and think that it means > that there is an algorithm for everything involved. > > Witness his confusion over the example I defined of a list where each > entry was computable but the list itself (and its antidiagonal) was > not. He didn't dispute that the list *existed*, but considered it > cheating because he couldn't use the definition to extract actual > digits of the antidiagonal - it didn't "tell him what to do" in his > own special sense. Ah, you're right, of course. I'll revise that part. Don't get me wrong. I'm not in this to "educate" anyone or to correct misconceptions. I'm mostly in this for the practice, both at working with various proofs and at identifying misconceptions. If anything useful comes of it for someone else, all the better, but I won't feel bad if people exit this thread thinking exactly as they came into it. -o (Unlike Virgil, I'll eventually get bored and go away. :)
From: Owen Jacobson on 28 Jun 2010 19:56 On 2010-06-28 02:16:28 -0400, Peter Webb said: > "Owen Jacobson" <angrybaldguy(a)gmail.com> wrote in message > news:2010062800145641786-angrybaldguy(a)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. -o
From: Peter Webb on 29 Jun 2010 04:33 "Owen Jacobson" <angrybaldguy(a)gmail.com> wrote in message news:2010062819564372407-angrybaldguy(a)gmailcom... > On 2010-06-28 02:16:28 -0400, Peter Webb said: > >> "Owen Jacobson" <angrybaldguy(a)gmail.com> wrote in message >> news:2010062800145641786-angrybaldguy(a)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.
From: Owen Jacobson on 30 Jun 2010 22:39
On 2010-06-29 04:33:09 -0400, Peter Webb said: > "Owen Jacobson" <angrybaldguy(a)gmail.com> wrote in message > news:2010062819564372407-angrybaldguy(a)gmailcom... >> On 2010-06-28 02:16:28 -0400, Peter Webb said: >> >>> "Owen Jacobson" <angrybaldguy(a)gmail.com> wrote in message >>> news:2010062800145641786-angrybaldguy(a)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. |