Why can no one in sci.math understand my simple point?
in [Logic]
|
From: Peter Webb on 16 Jun 2010 23:25 > > 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. 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.
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 |