Why can no one in sci.math understand my simple point?
in [Logic]
|
From: Virgil on 20 Jun 2010 22:15 In article <4c1eb48b$0$1027$afc38c87(a)news.optusnet.com.au>, "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > "Virgil" <Virgil(a)home.esc> wrote in message > news:Virgil-B10127.13553420062010(a)bignews.usenetmonster.com... > > In article > > <7d59f93c-4bc8-43e2-9b40-485733a01305(a)z8g2000yqz.googlegroups.com>, > > WM <mueckenh(a)rz.fh-augsburg.de> wrote: > > > >> On 20 Jun., 01:58, Tim Little <t...(a)little-possums.net> wrote: > >> > On 2010-06-19, Virgil <Vir...(a)home.esc> wrote: > >> > > >> > > There is, however, some question in my mind about the existence of a > >> > > list of all and ONLY computable reals. > >> > > >> > Why? The computable reals can be proven countable, as you already > >> > know, so there is a bijection between N and the set of countable > >> > reals. > >> > >> That is not true. An exclusive list need not exist. > >> > >> 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 consttruct 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. > > > > 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. > > > > Actually, he shows that any purported list of all Reals must miss at last > one Real. Cantor's only direct proof of this did not involve constructing an antidiagonal at all but was based on the completeness of the reals as a whole versus the incompleteness of any sequence of reals. Suppose a sequence of reals were able to include all reals. Let a_1 be the first element of the sequence. There will be a first in that original sequence greater than a_1, which we can call a_2. And one will clearly be able to generate a subsequence, a_1, a_2, a_3, of the original in which each successive element is between the last two elements of that subsequence. It transpires that the subsequence of the a_i sequence of its odd indexed terms is strictly increasing and bounded above by the even terms and the subsequence of even indexed terms is decreasing and bounded below by the odd numbered terms. so both sequences have limits but those limits cannot be members of the sequences, nor, indeed, members of the original supposed enumeration of all reals. Thus the reals cannot be listed. > > *not* the same as being uncountable, witness the same argument applied to > computable Reals. > > > > Actually Cantor's original "diagonal" proof was based on the set of all > > functions from the naturals to a two element set, > > No. It is based upon showing that any purported list of all Reals must > neccesarily omit at least one Real, and he does this by providing an > explicit construction of the anti-diagonal based upon examining the first n > digits of the first n items on the list for all n. Not so. That form of the diagonal proof was not created by Cantor, but by one of his followers. > > Which is exactly what I am doing. > > > but several people > > have constructed bijections between that set of functions and the set of > > all reals. I have done it myself. > > Perhaps if you were to provide an actual list of all computable numbers - > and only the computable numbers - your claim that they can be listed would > be vindicated. That is not MY claim, though I have seen others claim it. > > My bet is that you will have about as much success forming a list of all > computable Reals as you would do forming a list of all Reals, but if you > think such a list exists, go for it.
From: Virgil on 20 Jun 2010 22:18 In article <4c1eb4dc$0$1027$afc38c87(a)news.optusnet.com.au>, "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > "Virgil" <Virgil(a)home.esc> wrote in message > news:Virgil-22B7E6.14010020062010(a)bignews.usenetmonster.com... > > In article > > <ccb88bb1-d8a6-4f04-bc6a-ca3346f7c8ad(a)c10g2000yqi.googlegroups.com>, > > WM <mueckenh(a)rz.fh-augsburg.de> wrote: > > > >> On 20 Jun., 02:04, "Mike Terry" > >> > > >> > No, you're misunderstanding the meaning of computable. > >> > > >> > Hopefully you will be OK with the following definition: > >> > > >> > A real number r is computable if there is a TM (Turing machine) > >> > T which given n as input, will produce as output > >> > the n'th digit of r. > >> > >> Whatever might be the true meaning: The Turing machine need a finite > >> definition. Therefore the computable number has a finite definition. > >> > >> There are only countable many finite definitions. And every diagonal > >> of a defined Cantor list has also a finite definition. > > > > Cantor's argument does not require that any member of a list of reals be > > computable beyond a finite number of decimal places, so enough of each > > can be finitely defined for the proof to work. > > Exactly the same as mine. > > Cantor calculates the anti-diagonal to n places (for all n) using only the > first n digits of the first n items. So do I. Technically speaking,CANTOR'S anti-diagonal argument involves only binary sequences, not real numbers at all, though the real number form of the argument is almost always attributed to him.
From: Tim Little on 20 Jun 2010 22:29 On 2010-06-21, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > No, I only need a finite algorithm which will calculate it to n > decimal places with finite input. You have previously stated that you can do this with "about three lines of Java code". Here's your Java method signature: int antidiagonalDigit(BigInteger n). Here are the first twenty digits of the first twenty members of my list: 93525532854532512838 32127313472944276266 70595916184994935423 20733652719572401688 30472031767118774150 47190325821263633948 74236814853458351851 58521903865615844550 91701104659863267390 39510921669610680229 19656091025330568974 49591084533660072011 81683520683673830124 93720622611168810054 50284245443806050152 11702670934156383526 58534679962278312978 68478827933494896765 83579375050000862329 50241229144880453593 Now let's see your Java code. If I then give you the first 10^100 list entries to 10^10 digits, would the same code suffice? Would it have to be enlarged? How large would it be if I required any digit up to the 10^100'th? How large would it have to be if I asked for an algorihm that produces *any* digit on request? - Tim
From: Tim Little on 20 Jun 2010 22:40 On 2010-06-21, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > Of course it is an algorithm. > > It accepts the first n digits of the first n terms on the list That's where you can stop. An algorithm for a computable real accepts as input *only* the desired precision. Nothing else. Since you mentioned Java previously in the thread (and may understand that better), you could think of it as follows: public interface ComputableReal { public int getDecimalDigit(BigInteger n); } If you can implement that interface with a finite self-contained algorithm, it's a computable real. If you can't, it isn't. Note that the interface has no signature for a method that takes "the first n digits of the first n terms on the list". If you want list data, you'll have to embed it within the implementation somehow. - Tim
From: Tim Little on 20 Jun 2010 22:47
On 2010-06-21, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > "Tim Little" <tim(a)little-possums.net> wrote in message > I do understand that. But I don't actually ask for a "finite algorithm" in > my proof, I only require that I am provided a purported list of all > comptuable Reals. Later in the proof, you claim that the antidiagonal real is computable. In other words, that there exists a finite algorithm for computing it. > Yes, in practice, this means that each item is specified by a finite > algorithm, but so what? I ask for a purported list of all computable Reals > and show there is at least one missing. At least one *what* missing? A real? Fine - Cantor's proof shows that there is a missing real. What's that? You want the antidiagonal to be a *computable* real? Well, then - you are required to show that there always exists a finite algorithm to compute it, and that is not present in Cantor's proof. So your modified "proof" is either invalid, or you must include significant amounts of material not present in Cantor's proof. As is well-known to competent mathematicians and computer scientists, no amount of material will make it valid, as the modified "theorem" is simply false. It is *not true* that any list of computable reals has a computable antidiagonal. - Tim |