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: Peter Webb on 18 Jun 2010 01:38 >> 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? The diagoinal number is clearly computable. There is a very simple algorithm for generating it, and this algorithm is easily implemented in a Turing Machine. >> >> That you cannot list some set is not the same as the set in uncountable. > > That does not parse. > The property "this set cannot be listed without missing some elements" is not the same as the property "this set is uncountable". Computable numbers cannot be listed without missing some elements, but they are definitely countable. > >> 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. For the set of all computable numbers: Proposition 1 is not true. You cannot list all computable numbers, as you can use a diagonal argument to generate a computable number not on the list. Proposition 2 is true. The list of computable numbers is trivially a subset of the Reals that can be generated by TMs (in fact its the same set), and this is a countable set. So your two ways of determining if a set is countable are clearly not the same. Things can be countable according to (2) but not countable according to (1).
From: Tim Little on 18 Jun 2010 01:44 On 2010-06-18, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > There are a countable number of computable Reals. Correct. > You can apply the Cantor construction to any purported list of all > computable Reals to form a computable Real not on the list. No, you can apply the Cantor construction to any purported list of all computable Reals to form a *non*computable Real not on the list. > This proves that the computable Reals cannot be listed. It proves no such thing. > It does *not* prove the computable Reals are uncountable, and in > fact they are not. Of course the computable reals are countable. I never claimed otherwise. You are the one claiming that they cannot be listed, a statement equivalent to their uncountability. > In exactly the same manner, Cantor proved that the Reals cannot be > listed. This does *not* automatically mean they are uncountable, > any more than the same proof applied to computable Reals proves they > are uncountable. These are different concepts. (Although they were > not when Cantor produced his proof). Computability as a concept did not even exist when Cantor produced his proof. You are extremely confused. - Tim
From: Tim Little on 18 Jun 2010 01:45 On 2010-06-18, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > The computable Reals cannot be listed. False. > Maybe your definition needs a little work? No maybe about it, your definition of "listable" needs work. - Tim
From: Tim Little on 18 Jun 2010 01:48 On 2010-06-18, Virgil <Virgil(a)home.esc> wrote: > 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. Yes, Peter is very confused. > 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. Heh, these two sentences would be great to quote out of context. In the context of Peter's premise the latter is true, but in ordinary context of mathematics it is very obviously false. - Tim
From: Tim Little on 18 Jun 2010 01:49
On 2010-06-18, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > Cantor's proof does *not* demonstrate that Reals are uncountable, it > just proves there can be no explicit enumeration of them. It proves that there is no enumeration of them, explicit or not. I have no idea where you are getting this strange notion of "explicitness". - Tim |