Cantor's Diagonal?
in [Logic]
|
Prev: The set theoretic content of the transfinite recursion theorem
Next: Geometry surface area Contact; related to "flatness"; Pedestal-Geometry #386 Correcting Math
From: zuhair on 3 Feb 2010 00:39 On Feb 3, 12:20 am, "Peter Webb" <webbfam...(a)DIESPAMDIEoptusnet.com.au> wrote: > > Can you explain this a bit better? What is the sequence? > > What does <> mean? > > Ordered pair. > > X={<O,0>,<H,1>,<O,2>,<H,3>,<O,4>,<H,5>,.....} > > another presentation might be like that > > X= O_0, H_1, O_2, H_3,......... > > which is simply X=OHOHOH....... > > __________________________________ > > If X=OHOHOH ...., then its not an infinite set; its not a set at all. > > Do you mean: > > X is the set of all sequences a_1, a_2, a_3 ... where each a_n is an element > of {O,H} ? No > > So OHOH... is an element of X, as are OOOOO..., HHHH..., HOO... etc? No > > Ie, the set of non-terminating binary sequences with H=1 and O=0 ? > > If that is the case, why didn't you just say "the set of non-terminating > binary sequences" ? OHOHOH.... means O followed by H which is followed by O which is followed by H and so on infinitely Zuhair
From: Arturo Magidin on 3 Feb 2010 00:39 On Feb 2, 11:26 pm, zuhair <zaljo...(a)gmail.com> wrote: > Cantor's claim is of *uncountability* of the set of all infinite > binary sequences, so the matter is not limited to showing the failure > of that with a specific arrangement of a specific countable set N. Of course it is. If A is *any* countable set, then by definition there is a bijection f:A-->N. If t:A-->B is any map from A to the set of binary sequences, then since there is no bijection from N to B then tf^ {-1} (composing right to left) is not surjective. Since f^{-1} is bijective, nonsurjectivity of tf^{-1} implies that t is not surjective, thus proving that there can be no surjection from A to B either. > I am attempting to disprove Cantor's claim of course, by showing that > it is limited to specific situation, by showing that it is not general > enough to make such a claim of uncountability. By showing that, after so many years, you can still exhibit an incredible amount of projection and an overeliance on the Argument From Personal Ignorance. -- Arturo Magidin
From: Tim Little on 3 Feb 2010 00:43 On 2010-02-03, zuhair <zaljohar(a)gmail.com> wrote: > However I do really think that I am mistaken, but I don't know were > is my mistake exactly. You seem to have lost sight of the definition of countability. - Tim
From: Virgil on 3 Feb 2010 00:49 In article <38df2f48-b006-4005-ba49-e21d47a154b3(a)b2g2000yqi.googlegroups.com>, zuhair <zaljohar(a)gmail.com> wrote: > Hi all, > > I have some difficulty digesting the diagonal argument of Cantor's. > > The argument is that the set of all infinite binary sequences cannot > have a bijection to the set of all natural numbers, thereby proving > that the former set is uncountable? > > However the argument looks to me to be so designed as to reach to that > goal? > > One can look at matters from an alternative way such as to elude > Cantor's conclusion! > > Examine the following: > > Lets take the infinite binary sequences of the letters O and H > > so for example we have the sequence > > X = OHOHOH........ > > in which O is coupled to the even naturals and H coupled to the odd > naturals. > > so the sequence above is > > X= {<O,i>,<H,j>| i is an even natural, j is an odd natural} > > so X is just an example of a infinite binary sequence. > > However lets try to see weather we can have a bijection between > the set of all infinite binary sequences and the set w+1 > which is {0,1,2,....,w} > > so we'll have the following table: > > 0 , 1 , 2 , 3 , ... > 0 H , O , O , H ,.... > 1 O , H , H , O ,.... > 2 H , H , H , H ,.... > 3 O ,O , H , H ,.... > . > . > . > . > > w O, O , O, O ,... > > > Now according to the above arrangement one CANNOT define a diagonal ! > since the w_th sequence do not have a w_th entry > to put H or O in it. > > So if we can have a diagonal then this would be of the set of all > infinite binary sequences except the w_th one, i.e. of the following > > 0 , 1 , 2 , 3 , ... > 0 H , O , O , H ,.... > 1 O , H , H , O ,.... > 2 H , H , H , H ,.... > 3 O ,O , H , H ,.... > . > . > . > . > > Suppose that the diagonal of those was D=HHHHH.... > i.e. D={<H,n>| n is a natural number} > > Now the counter-diagonal would be D' = OOOO... > i.e. D' = {<O,n>| n is a natural number} > > However there is nothing to prevent the w_th infinite binary sequence > from being D' ? > > So neither we can have a diagonal of all the infinite binary > sequences, nor the diagonal of a subset of these sequences would yield > a successful diagonal argument such as to conclude that the set of all > infinite binary sequences is uncountable? > > Thereby Cantor's argument fail in this situation! > > What I am trying to say is that this Diagonal argument seems to be > purposefully designed to reach the goal of concluding that > the set of all infinite binary sequences is uncountable, by merely > selecting a particular bijection with the set {0,1,2,3,....} > in a particular arrangement, such as to make a diagonal possible, such > as to conclude the uncountability of these infinite binary sequences, > While if we make simple re-arrangement like the one posed above then > this argument vanish! > > There must be something wrong with the way I had put things here, but > I would rather want to read the full proof of this diagonal argument > in Zermelo's set theory. > > Zuhair IIRC, the Cantor arguments proves "given ANY ennumeration of binary sequences there are binary sequences not included in it." And it does this by showing that if one assumes that one HAS an ennumeration, one can construct binary sequences not included in it. I do not see that what you say above is relevant to that argument.
From: Virgil on 3 Feb 2010 00:55
In article <3faa561b-3c72-4efa-ab73-936d9d68ceae(a)m31g2000yqb.googlegroups.com>, zuhair <zaljohar(a)gmail.com> wrote: > Cantor's claim is of *uncountability* of the set of all infinite > binary sequences, so the matter is not limited to showing the failure > of that with a specific arrangement of a specific countable set N. You misread the Cantor argument. When correctly read it shows that ANY enumeration of binary sequences is necessarily incomplete. |