Why can no one in sci.math understand my simple point?
in [Math]
|
Prev: power of a matrix limit A^n
Next: best way of testing Dirac's new radioactivities additive creation Chapt 14 #163; ATOM TOTALITY
From: Virgil on 21 Jun 2010 16:17 In article <600855ab-102e-46ba-a33a-10a6af6c08b0(a)w12g2000yqj.googlegroups.com>, WM <mueckenh(a)rz.fh-augsburg.de> wrote: > On 20 Jun., 21:55, Virgil <Vir...(a)home.esc> wrote: > > > > > The reals in a certain Cantor-list are countable. And if you form the > > > anti-diagonal of that list and add it (for instance at first position) > > > to the list, this new list is also countable. Again construct the > > > anti-diagonal and add it to the list. Continue. The situation remains > > > the same for all anti-diagonals you might want to construct. Therefore > > > all reals constructed in that way are countable. Nevertheless it is > > > impossible to put all of them in one list, because there would be > > > another resulting anti-diagonal. > > > > > Conclusion: It is impossible to obtain a bijection of all these reals > > > with N although all "these" reals are countable with no doubt. > > > > Equal cardinality of two sets requires, by definition, a bijection > > between them. > > > > The naturals are, by definition of COUNTABLE cardinality so that any set > > of equally countable cardinality must have a bijection with the > > naturals. > > But the set of all diagonals constructed according to the scheme given > above is countable but cannot be listed. Whatever do yu mean by "the set of all diagonals"? If you mean one "diagonal" for each possible list, that set of diagonals is not countable. If you mean the set of all "diagonals" for a single list, that is not countable either, since each of uncountably many permutations of the list produces a different "diagonal". > > > > Cantor has shown that the set of all reals cannot biject with the > > naturals, ergo, the set of all reals is NOT of countable cardinality. > > The same proof shows that some countable sets are of not countable > cardinality. I have yet to see such a "proof" that was not as flawed ad WM's views on mathematics. > > But you prefer not to think about that? I don't mind thinking about it at all, but I do not choose to believe anything that requires WM's perverse assumptions about mathematics to justify it.
From: WM on 21 Jun 2010 16:22 On 21 Jun., 21:35, "Mike Terry" <news.dead.person.sto...(a)darjeeling.plus.com> wrote: > > It is an irrational number. Add it at first position to the former > > list L0, obtain L1. Now construct the diagonal of L1 (according to a > > fixed scheme). It is certainly an irrational number. Add ist to the > > list L1 at first position, obtain list L2. Now construct the > > diagonal, ... and continue. I this way you get a countable set > > consisting of all rationals and of all diagonal numbers of these > > lists. > > No... What you get is an infinite sequence of lists (L0, L1, L2, ...) > > Each Ln in the sequence contains all rationals, and Ln contains the > antidiagonals for L0,...L(n-1). Ln doesn't contain its own antidiagonal, > and doesn't contain any antidiagonals for Lm with m>n. Correct. Therefore the set of antidiagonals appears to be uncountable = unlistable. But it is countable. > > > This set is certainly not countable, because you can prove that > > there is always a diagonal number not in the list. > > What set? The set of antidiagonals that can be constructed (by a given substitution rule) from an infinite sequence of lists. > It seems you're thinking there is some "limit list" for the > sequence of lists (L0, L1, L2, ...), or do you mean a specific list Ln for > some n? No, there is no limit list, there is an infinite sequences of lists. > > If you mean some kind of limit list, please define exactly what this is. There is no limit. There is a set of numbers, namely all rational numbers and all antidiagonals. > > > On the other hand, > > the set is countable by construction. What now? > > That depends on how you answer my previous question! Not at all. Every number that can be definied by any means, be it constructible, definable, computable, computable relative to a given list, X1, X2, X3 (where the Xn may be further notions to be devised by clever set theorists in order to avoid contradictions in set theory), every such number belongs to a countable set. That observation does not depend on any further definition. By the way: Cantor proved (or thought to prove) that the set of definable reals is uncountable. Cantor did not believe in undefinable reals (as he wrote to Hilbert in August 1906). In fact an undefinable number is nonsense, because the basic property of a number is the trichotomy with other numbers. Regards, WM
From: Mike Terry on 21 Jun 2010 16:23 "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote in message news:4c1eafa3$0$1025$afc38c87(a)news.optusnet.com.au... > > "Mike Terry" <news.dead.person.stones(a)darjeeling.plus.com> wrote in message > news:B8WdnX3itoZ7zYPRnZ2dnUVZ7qednZ2d(a)brightview.co.uk... > > "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote in message > > news:4c1e2b53$0$316$afc38c87(a)news.optusnet.com.au... > >> > >> "Tim Little" <tim(a)little-possums.net> wrote in message > >> news:slrni1r0ra.jrj.tim(a)soprano.little-possums.net... > >> > On 2010-06-20, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > >> >> Explain to me how my requirements for the input list of all > >> >> computable Reals is different to Cantor's requirements for the input > >> >> list of all Reals, other than the requirement that every item on the > >> >> list is computable? > >> > > >> > It is not. Your error comes later. > >> > > >> > Cantor's proof includes a construction taking a list L and defining an > >> > antidiagonal real antidiag(L) from it. Your error is supposing that > >> > this construction is a finite algorithm fitting the definition of > >> > "computable real". It is not. By stretching the definition of > >> > "algorithm" somewhat, it can be supposed to be an algorithm accepting > >> > finite input n and infinite input L, and producing the n'th > >> > antidiagonal digit. This is a stretch since algorithms are normally > >> > not supposed to have infinite inputs. > >> > >> The calculation of the nth digit only requires the first n digits to n > >> decimal places, and hence it is clearly a finite algorithm. > >> > >> Its simply ludicrous to suggest that the antidiagonal is not computable > >> given that a very simple algorithm will explicitly churn it out. > > > > Not so - the "very simple algorithm" you are suggesting requires "the > > input > > list" in its raw (infinite) form as input. > > No. Computing the the anti-diagonall to n places only requires the first n > items on the list to n digits of accuracy. > > And it clearly is computable. I can compute it. I take the nth digit of the > nth term, and ... blah blah. Yes, of course the first n digits of any number are computable, for a fixed n. You are just saying that GIVEN n, there is a TM: TM_n that computes the first n digits of the antidiagonal with only finite input. Well, that's not too amazing if you think about it :-) What you need to be able to claim is that there is single TM_ALL using finite input data, such that TM_ALL will calculate ALL the antidiagonal digits (i.e. infinitely many of them). So your approach above fails, because either you have to : - fix n [in which case I agree you are only using a finite amount of input data from the original list, but your TM_n doesn't do the required job for ALL m (i.e. it can't handle m>n] OR - not fix n [in which case you have an algorithm of sorts that can generate ALL antidiagonal digits, but it requires as input the FULL Cantor input list, which is an INFINITE amount of data] > > How is this number any less computable than the square root of 2? > > In both cases there is a finite algorithm to calculate the number to n > decimal places for all n. No that's exactly not what computable means! OBVIOUSLY every real (computable or not) can be "computed to n decimal places for all n". That's because every FINITE set can be computed simply by an algorith that internally encodes every element of the set. Let's be clear about this, because I doubt you said what you really meant to say, so lets get this issue out of the way. Take Pi = 3.14159... Obviously 3 is computable. Obviously 3.1 is computable. Obviously 3.14 is computable. Obviously 3.141 is computable. Well, the last number is getting pretty complicated (4 digits) so let's check that one. A function like this will do: (excuse the "C" like notation :) CalcDigit_4(n) { if (n == 1) Output 3 // digit 1 else if (n == 2) Output 1 // digit 2 else if (n == 3) Output 4 // digit 3 else if (n == 4) Output 1 // digit 4 else Output 0 // ..the rest :) } There we go - a finite algorithm computing 3.141 Similarly 5,6,7 digits, and so on. If we FIX n, and just look at the first n digits of Pi, OF COURSE THAT NUMBER IS COMPUTABLE! It's just a longer version of CalcDigit_4! Now reread what you stated: -- -- In both cases there is a finite algorithm to calculate the number to n -- decimal places for all n. So what you wrote is trivial, since it applies without any thought to every single real number r, computable or not. So having "a finite algorithm to calculate a number to n decimal places for all n" is useless as a definition of computable number. OK - what SHOULD the definition of computable number say? Clearly the definition should (and does) require that there is ONE algorithm, which we might call CalcDigit_All in line with my earlier examples, which can calculate the n'th digit for all n. Maybe you think this is saying the same thing as you said, but it's not. The order of qualifiers is different. Specifically, your definition was: Defn: r is computable if... for all n exists finite algorithm CalcDigit_n (m) CalcDigit_n(m) = m'th digit of r if m<=n The proper definition is: Defn: r is computable if... exists finite algorithm CalcDigit_All (m) CalcDigit_n(m) = m'th digit of r for ALL m Specifically, for sqrt(2), there is clearly a suitable CalcDigit_All algorithm that will accept m as input and produce the m'th digit of sqrt(2). There is not necessarily a suitable CalcDigit_All for your antidiagonal number, unless you can prove such exists (using only a finite amount of input data) > > > > > > As such, this is not an > > algorithm that can be implemented on a Turing machine. I.e. the algorithm > > is not the sort of algorithm that counts as "computable". Maybe you will > > dispute this, but it's been explained to you several times (including one > > of > > my posts), and you can always go away and look up the definition of > > computable function / Turing Machine etc., but it seems you've not done > > this. > > I don't have to look it up. I know it. Well, clearly not given what you've said above... :-) Mike.
From: Virgil on 21 Jun 2010 16:24 In article <4f120c56-2943-47b2-8786-1fb0059e8081(a)q12g2000yqj.googlegroups.com>, WM <mueckenh(a)rz.fh-augsburg.de> wrote: > On 20 Jun., 22:18, Virgil <Vir...(a)home.esc> wrote: > > In article > > <f92c169d-ee85-40c2-aa82-c8bdf06f7...(a)j4g2000yqh.googlegroups.com>, > > > > �WM <mueck...(a)rz.fh-augsburg.de> wrote: > > > 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. > > > > That is a deliberate misrepresentation of the so called "diagonal proof". > > But this proof can be applied to this countable set and shows its > uncountability. For every list of binary sequences, that list plus its "anti-diagonal" sequence can be listed. But there is no such list for which the "anti-diagonal" is a member of the list, so none of those lists ennumerates the set of ALL such sequences. Thus the set of all such sequences cannot be listed, or, equivalently, counted. Mutatis mutandis, the same is true for listing reals.
From: Mike Terry on 21 Jun 2010 16:30
"Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote in message news:4c1eb078$0$1028$afc38c87(a)news.optusnet.com.au... > > "Mike Terry" <news.dead.person.stones(a)darjeeling.plus.com> wrote in message > news:dLGdnUdTkbKpzoPRnZ2dnUVZ8hKdnZ2d(a)brightview.co.uk... > > "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote in message > > news:4c1e3743$0$1028$afc38c87(a)news.optusnet.com.au... > >> >> 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. > > > > So you require as input: > > - the 1st digit to 1 place of accuracy > > - the 2nd digit to 2 places of accuracy > > - the 3rd digit to 3 places of accuracy > > - ... > > > > The ... above is the give away! For your algorithm to work its going to > > require an INFINITE amount of input data. (Remember, you are trying to > > find > > a SINGLE stand-alone FINITE algorithm that produces ALL the required > > digits > > of the antidiagonal.) > > > > No, I only need a finite algorithm which will calculate it to n decimal > places with finite input. The definition of computable only requires me to > produce it to arbitrary accuracy. But obviously this single finite algorithm needs to be able to do this FOR ANY n. (I made an earlier post with more details.) > > I'm pretty sure you can't produce an algorithm which will produce *every* > digit in sqrt(2) in finite time. Sqrt(2) is computable because we can > calculate it to arbitrary accuracy, not because we can explicitly list every > digit in its decimal expansion in finite time; we can't. > > > > > So Tim was quite right, and you haven't answered his point correctly > > yet... > > > > Regards, > > Mike. > > > > > |