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: 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: Peter Webb on 3 Feb 2010 00:20 > 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} ? So OHOH... is an element of X, as are OOOOO..., HHHH..., HOO... etc? 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" ?
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
From: Arturo Magidin on 3 Feb 2010 00:36 On Feb 2, 10:18 pm, zuhair <zaljo...(a)gmail.com> wrote: > 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, So... the standard here is not "correctness", but "enough to force you to admit it"? > but Cantor's Diagonal argument do not work > like that, and I showed that we CANNOT have a diagonal with w+1, You showed that *you* couldn't come up with a diagonal. The standard, again, seems to be personal uniwllingness to accept something. >the > diagonal only works with sets that are isomorphic to w, Your definiition of "works" seems to be as surjective as your definition of "proof". > this make this > argument restricted and not general enough to conclude something like > uncountability of the set of all infinite binary sequences. Your definition of "restricted", "general", and "enough to conclude" seems to be uttelry subjective (and utterly worthless). > Anyhow I must be mistaken really. Ya think? If alpha is any countable ordinal and your "arrangement" is a map f:alpha --> B (where B is the set of binary sequences), then let t:omega-->alpha be a bijection between omega and alpha. Then ft is a map from omega to B. Define "the diagonal" in terms of ft; that f is not surjective follows from the fact that t is bijective and ft is not surjective. If you original alpha was omega, and t is not the identity, the argument still holds. -- Arturo Magidin
From: Tim Little on 3 Feb 2010 00:38
On 2010-02-03, zuhair <zaljohar(a)gmail.com> wrote: > 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. I was trying to work out why you brought totally superfluous ordinals into the discussion. > 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. "X is uncountable" is defined as "there does not exist a surjection from N to X". The diagonal argument shows that every function f:N->2^N fails to be a surjection, which *by definition* proves that 2^N is uncountable. The End. - Tim |