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: Tim Little on 16 Jun 2010 23:35 On 2010-06-15, Virgil <Virgil(a)home.esc> wrote: > Such a "number" would have no turing machine if it would require > infinitely many steps do determine that one ambiguous digit. There is no such thing as an "ambiguous digit" of an uncomputable real. For every digit position, there is a Turing machine that can compute all digits up to that position. However there is no Turing machine that computes all digits; the quantifiers cannot be reversed. - Tim
From: Tim Little on 16 Jun 2010 23:39 On 2010-06-15, |-|ercules <radgray123(a)yahoo.com> wrote: >> "|-|ercules" <radgray123(a)yahoo.com> wrote: >> >>> Consider the list of increasing lengths of finite prefixes of pi >>> >>> 3 >>> 31 >>> 314 >>> 3141 >>> .... [...] > How many digits of pi do all the list's members contain? Only the first digit. It is not true that all the list's members contain the 2nd digit, the third, or any later digit. - Tim
From: Virgil on 16 Jun 2010 23:45 In article <4c1995e5$0$26118$afc38c87(a)news.optusnet.com.au>, "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > > > > It is proof that there is no countable set of all real numbers, since > > any alleged such set is provably and constructably incomplete. > > > > Similarly, it is proof that there is no countable set of all > > constructable numbers, since any alleged such set is provably and > > constructably incomplete. > > I hate to disagree with you, because we are on much the same "side", but > this is not correct. Cantor's proof shows that you cannot form a list of all > Reals. This is not the same as the Reals being uncountable. If the reals were countable they would be listable, since such a list would be a "counting" of them, so that NOT being listable implies NOT being countable. An infinite set is defined to bee countable if and only if there is a surjection from the set of natural numbers to that set. When such a function is a bijection, it is commonly called a list. Since the set of reals is infinite but cannot be listed in this way, it follows that the reals necessarily are NOT countable. > > You can use Cantor's diagonal construction to similarly prove that you > cannot form a list of all computable numbers. However the computable numbers > are in fact countable. You can't simply equate the two concepts; they are > not exactly the same thing. For infinite sets, listability and countability are equivalent.
From: Tim Little on 17 Jun 2010 00:51 On 2010-06-17, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > I hate to disagree with you, because we are on much the same "side", but > this is not correct. Cantor's proof shows that you cannot form a list of all > Reals. This is not the same as the Reals being uncountable. An infinite list of reals is just a function from N to R. Cantor's proof shows that no such function is surjective (and so in particular, not bijective). That is *exactly* the same as the Reals being uncountable. > You can use Cantor's diagonal construction to similarly prove that you > cannot form a list of all computable numbers. No, you can use something like Cantor's diagonal construction to similarly prove that you cannot form a *computable* list of all computable numbers. The qualifier is necessary to the proof. - Tim
From: Peter Webb on 17 Jun 2010 03:21
"Tim Little" <tim(a)little-possums.net> wrote in message news:slrni1jadp.jrj.tim(a)soprano.little-possums.net... > On 2010-06-17, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: >> I hate to disagree with you, because we are on much the same "side", but >> this is not correct. Cantor's proof shows that you cannot form a list of >> all >> Reals. This is not the same as the Reals being uncountable. > > An infinite list of reals is just a function from N to R. Cantor's > proof shows that no such function is surjective (and so in particular, > not bijective). That is *exactly* the same as the Reals being > uncountable. > > >> You can use Cantor's diagonal construction to similarly prove that you >> cannot form a list of all computable numbers. > > No, you can use something like Cantor's diagonal construction to > similarly prove that you cannot form a *computable* list of all > computable numbers. The qualifier is necessary to the proof. > Precisely, and that is the error. Cantor's proof applied to computable numbers proves you cannot form a computable list of computable numbers. Cantor's proof applied to Reals proves you cannot form a computable list of Reals. The property "that you cannot form a computable list" is not the same as the property "is uncountable". For example, computable numbers have the first property but not the second. Cantor's proof is about what can be expressed in a list, and not directly about uncountable sets (which don't even get mentioned in the proof). > > - Tim |