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 2 Feb 2010 21:58 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: Marshall on 2 Feb 2010 22:34 On Feb 2, 6:58 pm, zuhair <zaljo...(a)gmail.com> wrote: > > 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? Of course. You don't think it should be designed to show what it wants to show? If it shows something other than what it was designed for, it was not designed very well! > 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} Can you explain this a bit better? What is the sequence? What does <> mean? I would expect a "sequence" to be a mapping from the naturals to some target set. > so X is just an example of a infinite binary sequence. I don't see how. > 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 the naturals, so it doesn't seem to have anything to do with Cantor's proof. On the other hand, what would you say the cardinality of that set is? Is it the same as the naturals? If so, then why don't you just use the naturals? If it's otherwise, then it doesn't relate to Cantor's diagonal proof. > 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. What if you just put the last line first? Also note that anything with a last element is not an infinite sequence. > 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! What can be shown is that for any purported sequence S of all possible infinite sequences, it is possible to construct an infinite sequence that is not in the sequence S. It doesn't matter how S is constructed; one can always construct from S an infinite sequence that is not in S. Marshall
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: zuhair on 2 Feb 2010 23:24
On Feb 2, 10:34 pm, Marshall <marshall.spi...(a)gmail.com> wrote: > On Feb 2, 6:58 pm, zuhair <zaljo...(a)gmail.com> wrote: > > > > > 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? > > Of course. You don't think it should be designed to show what > it wants to show? If it shows something other than what it > was designed for, it was not designed very well! > > > > > > > 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} > > 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....... I would expect a "sequence" to be > a mapping from the naturals to some target set. Yes it is. > > > so X is just an example of a infinite binary sequence. > > I don't see how. > > > 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 the naturals, so it doesn't seem to have anything to do > with Cantor's proof. On the other hand, what would you say the > cardinality of that set is? Is it the same as the naturals? If so, > then why don't you just use the naturals? If it's otherwise, then > it doesn't relate to Cantor's diagonal proof. > > > > > 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. > > What if you just put the last line first? Also note that anything > with a last element is not an infinite sequence. > > > 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! > > What can be shown is that for any purported > sequence S of all possible infinite sequences, it is possible to > construct an infinite sequence that is not in the sequence S. > It doesn't matter how S is constructed; one can always construct > from S an infinite sequence that is not in S. > > Marshall |