Why can no one in sci.math understand my simple point?
in [Logic]
|
From: Tim Little on 20 Jun 2010 22:52 On 2010-06-21, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > Actually, he shows that any purported list of all Reals must miss at last > one Real. > > *not* the same as being uncountable Yes it is. Look up the definitions. > witness the same argument applied to computable Reals. Applying the same argument shows that any purported list of all computable reals must miss at least one real. So? >> Actually Cantor's original "diagonal" proof was based on the set of >> all functions from the naturals to a two element set, > > No. Yes, actually. There are many more modern reforumlations of Cantor's diagonal construction, and you are likely confusing those with the original. The more modern ones are more streamlined with the benefit of hindsight. That is why you were asked by one poster *exactly which* version of Cantor's diagonal argument you are talking about. So far it seems to be a strawman proof you invented yourself and are ascribing to Cantor. - Tim
From: Peter Webb on 20 Jun 2010 22:53 "Tim Little" <tim(a)little-possums.net> wrote in message news:slrni1tg3v.jrj.tim(a)soprano.little-possums.net... > On 2010-06-20, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: >> Thus if your list contained say: >> >> .1111111 >> .2222222 >> .1111222 >> >> The antidiagonal is 0.212... >> >> Notice that I computed this quite easily? > > I notice that your algorithm only works for n < 4. > Works for any n. I just picked 4 as an example. Indeed, I can explicitly compute the anti-diagonal to any arbitrary degree of accuracy. > >>> 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. > > According to one of Chaitin's papers, the first term is 0. OK, so the first digit of the anti-diagonal is "1". What is the second item on your purported list of all computable Reals? > > But that's irrelevant: it is either 0 or 1/9 and in *both* cases it is > a computable real. You personally might not know what it is, I might > not know what it is, but the list entry exists and is a computable > real either way. Yes. But you haven't provided a list of your computable Reals; you have just provided a set of possible computable Reals. You haven't told me what the first term is, your second term is, etc. And BTW your set is missing 0.333..... > > >> 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. > > You appear to be laboring under the misapprehension that Cantor had to > change any value to anything. > > He proved that if *there exists* a list of reals, then *there exists* > an antidiagonal real that is not on the list. If we don't know what > is on the list, then we won't know what the antidiagonal is - but we > still know it has one. > OK, I have a list of all Reals. Which real is missing? > >> 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's not poorly defined at all; it is precisely defined. > No, its not precisley defined, you can't tell me its value to arbitrary accuracy. Specifically you can't tell me the nth digit. You will note Cantor's proof uses the nth digit of the nth item on the list to construct a missing Real. I ask for no more or less. > But even that is more than required: the proof even works for > *undefinable* lists of reals. For every hypothetical mathematical > object that is a list of reals, that list has an antidiagonal. > And every list of computable numbers has an anti-diagonal. Computable numbers are after all Reals. By your own statement, you are saying that a list of computable Reals also has an anti-diagonal. And guess what? Its not on the list. > >> 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. > > It is not arbitrary or random at all. Omega has a precise > mathematical definition and is a single real value. > What is nth digit? You see, Cantor's construction of the anti-diagonal uses the nth digit of the nth item on the list. If I am going to construct the anti-diagonal number, like Cantor did, I need to know the nth digit of the nth item. > >> 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. > > I did tell you with clear mathematical precision. Not sufficient for Cantor's proof. This accepts as input the decimal expansions of every item on the list. You have not provided this. > > >> 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. > > I provided that mapping. It is precisely defined and mathematically > unambiguous, merely difficult to use in practice. OK, what is the 23rd item on the list? I really can't tell you what Reals are missing from the list unless you supply the decimal expansion of every item in the list, any more than Cantor can tell you what number is missing from a list without being bold what numbers are on the list. This shouldn't be a problem; one of the definitions of a computable number is that it can be specified to any required degree of accuracy; I want merely the first n digits in its decimal expansion. > > >> 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. > > Fairness has nothing to do with it. I already provided far more than > Cantor's proof assumes. > How exactly do you think Cantor would prove there was a real missing from a list if you didn't tell him exactly what was on the list already? How could he prove Chaitan's constant was missing, unless you told him what the value of Chaitan's constant was? > >> 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. > > As state before, Cantor's proof does not require any input at all. It > proves the single *closed* proposition "there does not exist a > complete list of real numbers". No free variables, no input. Well no. It starts off with a purported list of all Reals, and then shows at least one is missing. > > It is *not* a schema of theorems "L is not a complete list of real > numbers", one for each L. In some fields of mathematics such schemata > exist, but Cantor's theorem was not an example of such. > > > - Tim
From: Tim Little on 20 Jun 2010 23:00 On 2010-06-21, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > "Tim Little" <tim(a)little-possums.net> wrote in message >> On 2010-06-20, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: >>> To produce the nth decimal of the anti-diagonal, look at the first n >>> items on the purported list of all computable Reals. >> >> In what way is that "a finite algorithm accepting only the *finite* >> input n"? > > Its finite, and its an algorithm. .... but not "accepting only the finite input n". Are you really so incapable of reading a single sentence? >> It either must embed the list within the algorithm (thus rendering >> it not finite), > > No, it embeds the first n digits of the first n terms to calculate > the first n decimal places, and does for all n. So your opinion is that any infinite set of finite sequences can always be embedded into a *finite* algorithm? What would such an algorithm look like, expressed in a computer language? int getDiagonalDigit(BigInteger n) { // ... you fill in this part ... } - Tim
From: Peter Webb on 20 Jun 2010 23:01 "Tim Little" <tim(a)little-possums.net> wrote in message news:slrni1ti2c.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 >>> 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. > > Look at the first theorem on http://en.wikipedia.org/wiki/Countable_set . > I use Wikipedia since if I quoted from a textbook you might not be > able to verify it. > > What you have just said as the definition for "recursively enumerable" > is *exactly* equivalent to being a countable set! > No. Do you believe the set of all computable numbers is recursively enumerable? Because Wikipedia only claims that the computable numbers are recursive, not that they are recursively enumerable. If you nthink that they are recursively enumerable, you have to produce a partial recursive function whose domain is exactly the uncomputable numbers, and I dare say you can't do that. > > I suggest you look up the definition for a recursively enumerable set, > and see how it differs from the definition of a countable set. > > >>> 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. > > Did you forget what you wrote? Look again at what you claimed: > > "What Cantor proved (in more modern parlance) is that there is no > recursively enumerable function from N -> R". > > You were the one applying the term "recursively enumerable" to a > function. I was merely correcting your mistake. > Whoops. I meant a recursively enumerable set. > >> Well, that's very rude of you. > > Yes, it was. Polite correction of your errors wasn't getting > anywhere, and you did not appear to be aware of how bad it looks to be > declaiming "Cantor didn't prove that the reals were uncountable!" > while obviously not grasping some of the most basic concepts in set > theory, proof, and computability. > Again, rude. > > - Tim
From: Peter Webb on 20 Jun 2010 23:04
"Virgil" <Virgil(a)home.esc> wrote in message news:Virgil-F1698A.20153920062010(a)bignews.usenetmonster.com... > 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. Yes. But that is not the proof I am using as a model. >> >> *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. Its the proof to which I refer. I want to discuss mathematics, not history. >> >> 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. Hmmm. >> >> 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. |