Cantor's Diagonal?
in [Math]
|
From: zuhair on 2 Feb 2010 21:59 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
From: Tim Little on 2 Feb 2010 22:35 On 2010-02-03, zuhair <zaljohar(a)gmail.com> wrote: > However the argument looks to me to be so designed as to reach to that > goal? Surely it should not be surprising that a proof of a theorem should be so constructed as to prove that theorem. > One can look at matters from an alternative way such as to elude > Cantor's conclusion! [...] > 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} If one tries to use the methods of Cantor's proof to prove a different theorem with different premises, one may fail! Shock ensues. > 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,....} The theorem is that every function from N to 2^N fails to be a surjection. Hence bijections of N with some other countable set (like w+1) are irrelevant to the theorem. Are you expecting that by cleverly selecting some countable set A, you'll be able to find a surjection g:A->2^N? It is a simple corollary of Cantor's theorem that this is impossible. You don't need to redo a whole proof for every such A, all you need is the trivial theorem that when f:X->Y is surjective and g:Y->Z is surjective, then (g o f):X->Z is surjective. Use X=N, Y=A, Z=2^N. - Tim
From: zuhair on 2 Feb 2010 23:18 On Feb 2, 10:35 pm, Tim Little <t...(a)little-possums.net> wrote: > On 2010-02-03, zuhair <zaljo...(a)gmail.com> wrote: > > > However the argument looks to me to be so designed as to reach to that > > goal? > > Surely it should not be surprising that a proof of a theorem should be > so constructed as to prove that theorem. > > > > > One can look at matters from an alternative way such as to elude > > Cantor's conclusion! > [...] > > 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} > > If one tries to use the methods of Cantor's proof to prove a different > theorem with different premises, one may fail! Shock ensues. > > > 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,....} > > The theorem is that every function from N to 2^N fails to be a > surjection. Hence bijections of N with some other countable set (like > w+1) are irrelevant to the theorem. > > Are you expecting that by cleverly selecting some countable set A, > you'll be able to find a surjection g:A->2^N? No. > > It is a simple corollary of Cantor's theorem that this is impossible. > You don't need to redo a whole proof for every such A, all you need is > the trivial theorem that when f:X->Y is surjective and g:Y->Z is > surjective, then (g o f):X->Z is surjective. Use X=N, Y=A, Z=2^N.. No, that is a different argument altogether from the Diagonal argument. I was speaking specifically about the Diagonal argument and not about the other proof, so don't mix the two arguments. The diagonal argument is only about a specific arrangement, it fails to be a generalized argument, that's my point. While the other argument of Cantor's, i.e. the one in which he proves that every injection from N to P(N) is not surjective, were N is the set of all natural numbers, is a general argument and it constitute what I may call as a proof of uncountability of N. Back again to my point which is: the Diagonal argument do not seem to constitute a proof like the other argument of uncountability of N. Let me clarify, suppose you had the Diagonal argument working for all countable sets and in all arrangements of these countable sets, i.e. suppose we could have found a diagonal always with any countable set like w+1, w+2 ,.etc, then I would say that this is an argument general enough to make me conclude that the set of all infinite binary sequences is uncountable, but Cantor's Diagonal argument do not work like that, and I showed that we CANNOT have a diagonal with w+1, the diagonal only works with sets that are isomorphic to w, this make this argument restricted and not general enough to conclude something like uncountability of the set of all infinite binary sequences. Anyhow I must be mistaken really. > > - Tim
From: Peter Webb on 2 Feb 2010 23:25 "zuhair" <zaljohar(a)gmail.com> wrote in message news:38df2f48-b006-4005-ba49-e21d47a154b3(a)b2g2000yqi.googlegroups.com... > 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} > That's not a bijection between R and N. The set N doesn't include w. So you are not attempting to disprove Cantor's claim. It just so happens that a very minor change to Cantor allows a proof that R cannot be bijected with w+1. Let the Real that the number n maps to be defined as R(n). Consider the sequence of Reals R(w), R(1), R(2), R(3) ... Cantors argument applied to this list shows R cannot be bijected with w+1, or indeed any countable ordinal.
From: zuhair on 3 Feb 2010 00:26
On Feb 2, 11:25 pm, "Peter Webb" <webbfam...(a)DIESPAMDIEoptusnet.com.au> wrote: > "zuhair" <zaljo...(a)gmail.com> wrote in message > > news:38df2f48-b006-4005-ba49-e21d47a154b3(a)b2g2000yqi.googlegroups.com... > > > > > > > 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} > > That's not a bijection between R and N. The set N doesn't include w. > So you are not attempting to disprove Cantor's claim. 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. 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. > > It just so happens that a very minor change to Cantor allows a proof that R > cannot be bijected with w+1. > > Let the Real that the number n maps to be defined as R(n). > > Consider the sequence of Reals > > R(w), R(1), R(2), R(3) ... > > Cantors argument applied to this list shows R cannot be bijected with w+1, > or indeed any countable ordinal. Yes of course, BUT the Diagonal argument fails with other arrangements, that's my point. For this Diagonal argument to be general enough I tend to think that we must find a diagonal for all arrangements of all countable sets, which is not the case, In many arrangement of some countable sets you simply cannot define a diagonal! so my point is, since that is the case then the Diagonal argument fails to be a general argument sufficient to make a proof of uncountability of these infinite binary sequences. However I do really think that I am mistaken, but I don't know were is my mistake exactly. Let me put it in other words, perhaps I was not clear: To me personally, I see Cantor's argument to be similar (although remotely) to one who saying that w+1 is not bijective to w because the function f:w -->w+1 , f(n)=n , is not a bijection, so as you see this claim is a false generalization over a specific situation, which bears some remote resemblance to the Diagonal argument of Cantor's, you see the Diagonal argument of Cantor's stipulates a *specific* arrangement of infinite binary sequences with N, and then concludes a *general* statement of the set of all those infinite binary sequences being *non countable*, so it is a *generalization over a specific situation*, which is the matter that I am objecting to. It is clear that we cannot have Diagonals with other arrangements of *countable* sets like w+1 that I posed in the head post, so this argument fails in these situations, which make one think that the Diagonal argument is not sufficient enough to prove what it claims. If one would find Diagonals for all arrangements of Countable sets, then this argument would have been sufficient for its claim, that's my point. hope I was clear. Zuhair |