Why can no one in sci.math understand my simple point?
in [Logic]
|
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
From: Peter Webb on 17 Jun 2010 03:29 "Virgil" <Virgil(a)home.esc> wrote in message news:Virgil-6240F4.21454316062010(a)bignews.usenetmonster.com... > 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. That does not follow, and I have already provided a counter-example. Computable numbers are countable, but cannot be listed. > > 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. > Only if the bijection can be explicitly created. There are countable sets which cannot be listed, such as the countable set of computable Reals. > Since the set of reals is infinite but cannot be listed in this way, it > follows that the reals necessarily are NOT countable. By this (incorrect) logic, the computable numbers must also be uncountable. But they are not. >> >> 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. No. Witness the infinite set of computable numbers. Countable but not listable. Cantor's proof shows that the set of Real numbers cannot be listed. It does not immediately follow that they are uncountable. Plenty of countably infinite sets cannot be listed. The set of computable numbers is one. The set of halting TMs is another.
From: WM on 17 Jun 2010 03:49 On 16 Jun., 23:43, MoeBlee <jazzm...(a)hotmail.com> wrote: > > Look simply at the results. > > If a theory says that there is an uncountable set of real numbers such > > each number can be identified as a computable or definable or > > constructable one, or in other ways, then this theory is provably > > wrong. > > Please tell me which EXACT, SPECIFIC theorem of ZFC "says" that "each > real number can be identified as a computable or definable or > constructable one, or in other ways". If you start with Cantor's list, then the diagonal can be identified. Do you mean that in ZFC Cantor's argument is wrong? Further: A number that cannot be put in trichotomy with others is not a number. Is such an unknown entity called a number in ZFC? > > > Reason: Cantor either proves that a countable set is uncountable or > > that a constructible/computable/definable number is not constructible/ > > computable/definable. > > Whatever Cantor proves, my question is specifically as to ZFC. I consider results only. If ZFC allows the conclusion that Cantor's diagonal argument is wrong, then ZFC may be right. Is it right? > > > What the theory internally may be able to prove or not to prove is, at > > least for my person, completely uninteresting. > > What interests you is entirely up to you, of course. But you've not > shown that ZFC is inconsistent (where 'inconsistent' is defined as > "having as a theorem some formula and its negation"). I have been told that ZFC yields this result: There are uncountable many real numbers. And by number I understand something that can be put in trichotomy with other numbers. If this is not the case, ZFC may be right. Others have told me that ZFC does not prove any uncountability at all and that the "standard model" is not a model of ZFC at all. If this is the case, ZFC may be right. Regards, WM
From: Virgil on 17 Jun 2010 03:54 In article <4c19cd2c$0$316$afc38c87(a)news.optusnet.com.au>, "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > 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. To be correct, there is no computable list of ALL of the computable numbers, even though the set of computable numbers is e countable, but there are lots of possible computable lists of computable numbers. For example, for n in {1,2,3,...}, f(n) = 1/n is a computable 'list' of computable numbers. > > 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
From: Virgil on 17 Jun 2010 03:59
In article <4c19cef9$0$17178$afc38c87(a)news.optusnet.com.au>, "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > "Virgil" <Virgil(a)home.esc> wrote in message > news:Virgil-6240F4.21454316062010(a)bignews.usenetmonster.com... > > 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. > > That does not follow, and I have already provided a counter-example. > Computable numbers are countable, but cannot be listed. > > > > > 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. > > > > Only if the bijection can be explicitly created. There are countable sets > which cannot be listed, such as the countable set of computable Reals. > > > Since the set of reals is infinite but cannot be listed in this way, it > > follows that the reals necessarily are NOT countable. > > > By this (incorrect) logic, the computable numbers must also be uncountable. > But they are not. > > > >> > >> 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. > > No. Witness the infinite set of computable numbers. Countable but not > listable. > > Cantor's proof shows that the set of Real numbers cannot be listed. It does > not immediately follow that they are uncountable. Plenty of countably > infinite sets cannot be listed. The set of computable numbers is one. The > set of halting TMs is another. One can create lists which contain all of the computable numbers , (or all of the halting TMs) but which, of necessity, list some other things as well. |