Why can no one in sci.math understand my simple point?
in [Logic]
|
From: Peter Webb on 20 Jun 2010 11:43 >> Perhaps if you could explain how my proof differs from Cantor's >> proof, that would be a start. > > I have done already, but perhaps I can explain it in different terms > for you. > > >> You seem to accept Cantor's proof, but not mine. Yet they are almost >> identical, the only difference being I have inserted the word >> "computable" in front of "reals". >> >> I can't see how you can accept one and not the other. > > Cantor's proof shows that for any mapping L:N->R, antidiag(L) is real > and not in range(L). Cantor's proof does include a proof that > antidiag(L) is real. It does not show that antidiag(L) is a > computable real. > Yes. > You cannot just drop "computable" in there and suppose that the logic > works, just as you cannot drop "rational" in there and suppose that > the logic works. > Well, it does work. > If you want to prove that for any mapping L:N->R, antidiag(L) is > computable, you need to include a proof that antidiag(L) satisfies the > mathematical definition for a computable real. > OK. I an specify it to n places for all n using the following simple algorithm. Change the nth digit of the nth term from a 1 to a 2 and else to a 1. Thus if your list contained say: ..1111111 ..2222222 ..1111222 The antidiagonal is 0.212... Notice that I computed this quite easily? Every item on the list is computable. So every item is known to at least n decimal places of accuracy, and Cantor gives us a very easy way to compute the first n terms on the anti-diagonal given the first n items on the list to n decimal places. > >> It is extremely easy to compute. >> >> Take the nth decimal place of the nth term. > > The nth decimal place of the nth term of what? The list L? That's > fine if you permit infinite lists of reals as input to the algorithm, > but the definition of "computable real" permits no such thing. > No, to calculate the first n terms of the anti-diagonal you require only te first n items on the list to n places of accuracy. Cantor's anti-diagonal is computable because the first n items on the list are computable, and he provides an explicit contruction for his number which is very easy to compute indeed. > >> I am using Cantor's proof exactly, except for inserting the word >> "computable" before every use of the word "real". That is the whole >> point. > > That doesn't work because Cantor's work does not include any proof > that antidiag(L) is computable: only that it is real. Hence there is > a gaping hole in the validity of your modified text. Well, no. Cantor actually provides an explicit construction for the anti-diagonal. He does have to prove its a computable number; he actually computes it. If every item on the list is computable, every item can be specified to any required degree of accuracy (in decimal, in this case), and we can "compute" the nth decimal place of each. Clearly we can compute the Cantor substitution to explicitly construct another number, the anti-diagonal. Simply substituting a "1" fo a "2" etc is still computable. > > You will not be able to fill that hole, because there are well-defined > functions L for which antidiag(L) is *not* a computable real. > There > are even explicitly-definable such lists, and furthermore there are > such lists where there are only two values in the range: for example, > let L(n) = 0 if the n'th digit of Omega is 0, L(n) = 1/9 otherwise. > I am having a bit of trouble computing even the first term of that. I am also wondering how Cantor would have felt about that. I can't see that he can change a "1" to a "2" etc if he doesn't know what the value is. But you have made an excellent point in your example. When Cantor is confronted with some digit as poorly defined your Chaitan's number example, it can simply say "I don't care what the number actually is". There is not the same luxury with computable Reals; this act of arbitrary/random choice can make them uncomputable, as your example shows. > Both members of range(L) are very obviously computable - they're even > rational! But the decimal antidiagonal is not computable. > Well, yes, but I am failing to see how you are providing a list of computable Reals when you won't actually tell me even what is the first computable Real on the list. Cantor's algorithm requires slightly more than a set of Reals, it also demands they are ordered for us - there is a mapping from N to that set. He asks for and uses in his proof a "list" of numbers. What number does 1 map to in your example? > > - Tim That's still a nice example, that every item in a list can be computable but the anti-diagonal is not. But I still don't think you are really playing fair with this one. You have to tell me what the first, second, third etc items are on the list. I mean, that's what a list is after all, a mapping from N, and that is what Cantor's proof requires as input.
From: Peter Webb on 20 Jun 2010 11:52 "Tim Little" <tim(a)little-possums.net> wrote in message news:slrni1qvhp.jrj.tim(a)soprano.little-possums.net... > On 2010-06-20, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: >> Cantor's proof that Reals cannot be listed requires an explicit >> list, such that the nth digit of the nth term can be determined. > > No, it just requires that the nth digit of the nth term exist. It > does not require that the nth digit of the nth term be computable by a > finite algotihm. It does not even require that there is a finite > mathematical formula defining it. > > >> What Cantor proved (in more modern parlance) is that there is no >> recursively enumerable function from N -> R. > > False on three counts: > > 1) Recursive enumerability has nothing to do with it. > So you assert. Personally, I think that the fact that the computable Reals are not recursively enumerable is intimately related, as a set being recursively enumerable in this context basically means the same thing as there being a mapping from N to exactly that set, ie a list of elements. It is so intimately related as to being different words for the same thing. > 2) The word you should be using instead of "recursively enumerable" > is "surjective". > Well, recursively enumerable is a property of sets, and surjective is a property of mappings, so dunno what you are talking about. > 3) There are plenty of recursively enumerable functions from N -> R. > I don't dispute that. > Please, learn how to understand mathematical proofs so that you don't > embarrass yourself further in future. > Well, that's very rude of you. > > - Tim
From: Jesse F. Hughes on 20 Jun 2010 11:51 Newberry <newberryxy(a)gmail.com> writes: > On Jun 19, 6:06 am, "Jesse F. Hughes" <je...(a)phiwumbda.org> wrote: >> Newberry <newberr...(a)gmail.com> writes: >> >> Because every infinite sequence of digits represents a real number? And >> >> the antidiagonal is one such sequence? >> >> > If it does not exist then it does not represent anything let alone a >> > number. >> >> > Now it is clear that it does not exist. Since all the reals are on the >> > list and the anti-diagonal would differ from any of them. This >> > violates the assumption. Hence the anti-diagonal does not exist. >> >> Wow. Are you saying that the *sequence of digits* specified by the >> anti-diagonal does not exist? > > That's right. There is no formula or algorithm to construct the list. > It means that you would have to flip each and every digit one by one. > And that is impossible. Of course, it is perfectly reasonable to accept that there is no such list, because Newberry says so. Cantor was this utterly insane freak who chose not to accept Newberry's word for it, and instead *prove* that there was no list of all real numbers. Obviously, his proof is nonsense, because, after all, Newberry said there was no list. -- "I suggest to those who listen that they enjoy the world, whatever their piece of it may be, as much as they can over the next few days, as soon enough, it will pass away, thanks to people who call themselves 'mathematicians'." -- JSH envisions geek Ragnarok
From: Peter Webb on 20 Jun 2010 12:03 "Tim Little" <tim(a)little-possums.net> wrote in message news:slrni1r53f.jrj.tim(a)soprano.little-possums.net... > On 2010-06-20, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: >> "Tim Little" <tim(a)little-possums.net> wrote in message >>> If you intend your proof to be "exactly the same as Cantor's, but with >>> the only difference being the word "computable" in front of the word >>> "Real"", it must start with a conditional introduction. In other >>> words, something like: >>> >>> "Suppose that L is a list of computable Reals. That is, L is a >>> function from N to R and for all n in N, there exists a Turing >>> Machine T_n such that when provided with k as input, T_n halts and >>> outputs the k'th decimal digit of L(n)." >> >> That's not how Cantor's proof starts. > > Correct: It didn't feature any mention of computable reals (but as I > recall it did feature the relevant properties of the definition of a > real number). > > I am presuming that you want *your* proof to substitute "computable > real" for "real", and therefore you need to substitute the definition > of computable real number for the definition of real number. That > means you also need to make that substitution in the definition of a > list of computable real numbers. > I can't see how the move from addition of "computable" in front of "Reals" requires any additional substitution in my "definition of a list". A list is simply a mapping from N. Yes, I want to know the first item, the second item etc; that is what a list is. > Are you starting to see now why it makes no sense to just drop > "computable" in front of every occurrence of the word "real" in the > proof? > Sort of. You are saying that you could effectively not specify what the first computable Real on the list is, because it depends upon some uncomputable function based on Chaitans. I can see why that is less of a problem to Cantor than it is to me, because he cares less about what it really was. But I still can't accept that you are providing a list of computable Reals when you aren't even telling me what the first one actually is. That's cheating. > > - Tim
From: WM on 20 Jun 2010 12:28
On 20 Jun., 17:51, "Jesse F. Hughes" <je...(a)phiwumbda.org> wrote: > Cantor was this utterly insane freak who chose not to accept Newberry's > word for it, and instead *prove* that there was no list of all real > numbers. Obviously, his proof is nonsense, because, after all, Newberry > said there was no list. His proof is nonsense because it proves that a countable set, namely the set of all reals of a Cantor-list and all diagonal numbers to be constructed from it by a given rule an to be added to this list, cannot be listed, hence, that this indisputably countable set is uncountable. Even completely blinded matheologicians should be able, perhaps after some contemplation, to recognize that. Regards, WM |