"Virgil" <Virgil@home.esc> wrote in message news:Virgil-F1698A.20153920062010@bignews.usenetmonster.com... > In article <4c1eb48b$0$1027$afc38c87@news.optusnet.com.au>, > "Peter Webb" <webbfamily@DIESPAMDIEoptusnet.com.au> wrote: > >> "Virgil" <Virgil@home.esc> wrote in message >> news:Virgil-B10127.13553420062010@bignews.usenetmonster.com... >> > In article >> > <7d59f93c-4bc8-43e2-9b40-485733a01305@z8g2000yqz.googlegroups.com>, >> > WM <mueckenh@rz.fh-augsburg.de> wrote: >> > >> >> On 20 Jun., 01:58, Tim Little <t...@little-possums.net> wrote: >> >> > On 2010-06-19, Virgil <Vir...@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.
