Why can no one in sci.math understand my simple point?
in [Logic]
|
From: Virgil on 17 Jun 2010 23:29 In article <4c1ae37b$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-11576A.01595017062010(a)bignews.usenetmonster.com... > > 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. > > No. > > Lets imagine you give me a list which is supposed to contain all computable > numbers in [0, 1.0] , and possibly some other Reals. You can even have some > computable Reals appearing multiple times in the list. > > I can use the Cantor diagonal construction to create a Real not on the list, > which means that it is not a computable number. So the list cannot contain > all computable numbers. How does showing the list does not contains a non-computable number show that it does not contain a computable number? > > That you cannot list some set is not the same as the set in uncountable. That does not parse. > Computable numbers are countable but cannot be listed. The only ways I know to show a set to be countable are: 1: Showing that its elements can be listed (surject N to the set). 2: Showing it to be a subset of a countable set. You have now claimed that neither of these is possible for the set of non-computable numbers.
From: Sylvia Else on 17 Jun 2010 23:37 On 18/06/2010 10:40 AM, Transfer Principle wrote: > On Jun 17, 6:56 am, Sylvia Else<syl...(a)not.here.invalid> wrote: >> On 15/06/2010 2:13 PM, |-|ercules wrote: >>> the list of computable reals contain every digit of ALL possible >>> infinite sequences (3) >> Obviously not - the diagonal argument shows that it doesn't. > > But Herc doesn't accept the diagonal argument. Just because > Else accepts the diagonal argument, it doesn't mean that > Herc is required to accept it. > > Sure, Cantor's Theorem is a theorem of ZFC. But Herc said > nothing about working in ZFC. To Herc, ZFC is a "religion" > in which he doesn't believe. Well, if he's not working in ZFC, then he cannot make statements about ZFC, and he should state the axioms of his system. > > Else's post, therefore, is typical of the posts which seek > to use ZFC to prove Herc wrong. Part of the problem, as others have noted, lies in determining what it is that Herc thinks he's proving. His assertions become inpenetrable as an increasing function of their distance from the start of his posting. Sylvia.
From: Virgil on 18 Jun 2010 00:47 In article <4c1ae6b7$0$18229$afc38c87(a)news.optusnet.com.au>, "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > > > > Since by definition, "listability" = "countability", Cantor's proof of > > unlistability proves uncountability. > > Really? Where did you get that from? > > The computable Reals cannot be listed. > > Therefore according to you they are uncountable. > > But they aren't. > > Maybe your definition needs a little work? Consider the set of computable numbers, S. According to http://en.wikipedia.org/wiki/Countable_set, one definition of such a set, S, being countable is that there is a injective function from S to N, which is equivalent to there being a surjective function from N to S. Since you object to there being any bijection from N to any superset of S, you must equally be rejecting any surjection from N to S and rejecting any injection from S to N, since from any such bijection such a surjection is easily derived. So in what sense do you claim that the the set S of computable numbers is countable? It is certainly not in any sense that I am aware of.
From: |-|ercules on 18 Jun 2010 01:03 "Sylvia Else" <sylvia(a)not.here.invalid> wrote > On 18/06/2010 10:40 AM, Transfer Principle wrote: >> On Jun 17, 6:56 am, Sylvia Else<syl...(a)not.here.invalid> wrote: >>> On 15/06/2010 2:13 PM, |-|ercules wrote: >>>> the list of computable reals contain every digit of ALL possible >>>> infinite sequences (3) >>> Obviously not - the diagonal argument shows that it doesn't. >> >> But Herc doesn't accept the diagonal argument. Just because >> Else accepts the diagonal argument, it doesn't mean that >> Herc is required to accept it. >> >> Sure, Cantor's Theorem is a theorem of ZFC. But Herc said >> nothing about working in ZFC. To Herc, ZFC is a "religion" >> in which he doesn't believe. > > Well, if he's not working in ZFC, then he cannot make statements about > ZFC, and he should state the axioms of his system. Can you prove from axioms that is what I should do? If you want to lodge a complaint with The Eiffel Tower that the lift is broken do you build your own skyscraper next to the Eiffel Tower to demonstrate that fact? > >> >> Else's post, therefore, is typical of the posts which seek >> to use ZFC to prove Herc wrong. > > Part of the problem, as others have noted, lies in determining what it > is that Herc thinks he's proving. His assertions become inpenetrable as > an increasing function of their distance from the start of his posting. heheh. That's my favorite Simpson's quote, "The potential for mischief varies inversely with one's proximity to the authority figure.". Herc
From: Peter Webb on 18 Jun 2010 01:10
"Virgil" <Virgil(a)home.esc> wrote in message news:Virgil-6672C4.22473617062010(a)bignews.usenetmonster.com... > In article <4c1ae6b7$0$18229$afc38c87(a)news.optusnet.com.au>, > "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > >> > >> > Since by definition, "listability" = "countability", Cantor's proof of >> > unlistability proves uncountability. >> >> Really? Where did you get that from? >> >> The computable Reals cannot be listed. >> >> Therefore according to you they are uncountable. >> >> But they aren't. >> >> Maybe your definition needs a little work? > > Consider the set of computable numbers, S. > > According to http://en.wikipedia.org/wiki/Countable_set, > one definition of such a set, S, being countable is that there is a > injective function from S to N, which is equivalent to there being a > surjective function from N to S. > > Since you object to there being any bijection from N to any superset of > S, you must equally be rejecting any surjection from N to S and > rejecting any injection from S to N, since from any such bijection such > a surjection is easily derived. > > So in what sense do you claim that the the set S of computable numbers > is countable? > http://en.wikipedia.org/wiki/Computable_number "Although the set of real numbers is uncountable, the set of computable numbers is countable". Easily proved. All computable numbers can be generated by a finite TM (by definition), and there are only countable finite TMs (as these can easily be enumerated). > It is certainly not in any sense that I am aware of. That a set of Real numbers cannot be listed is *not* the same thing as the set is uncountable. Cantor's proof does *not* demonstrate that Reals are uncountable, it just proves there can be no explicit enumeration of them. This is easily seen by comparison with a diagonal proof that all computable Reals cannot be listed - this doesn't immediately mean they are uncountable, as they aren't. |