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: James Burns on 3 Feb 2010 10:10 zuhair wrote: > On Feb 3, 12:39 am, Arturo Magidin <magi...(a)member.ams.org> wrote: >>On Feb 2, 11:26 pm, zuhair <zaljo...(a)gmail.com> wrote: >>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. [...] > Cantor's argument DOES show that every injection f from N to S > *provided that N is ordered in the natural way* and S is the set of > all infinite binary sequences, then f is not surjective. > > I have put an emphasis above on the clause "when N is ordered in the > natural way" > what I mean by that is N is ordered such that 0 is the first of all > members of N > then followed by 1 then followed by 2 then by 3 ,.... Look at Arturo Magidin's argument again, only substitute N', N with some arbitrary ordering, for the set A. (Is there a bijection between N' and N, you may ask. Yes: i: N' -> N, i(n) = n.) It's not clear what your objection to using the standard ordering is. It doesn't stop existing just because you have distracted your audience with some other arbitrary ordering. Jim Burns
From: Marshall on 3 Feb 2010 10:35 On Feb 3, 3:35 am, "Jesse F. Hughes" <je...(a)phiwumbda.org> wrote: > Marshall <marshall.spi...(a)gmail.com> writes: > >> 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. > > <,> is ordered pair. Just reverse the ordered pairs he wrote down and > you'll see what sequence he means: > > X = { <0,O>, <1,H>, <2,O>, .... } > > I assume he accidentally wrote the ordered pairs backwards. Bleah. Even with <x,y> as an ordered pair, and reversing the elements of the pair, it's still not valid set builder notation. But I suppose this is just another case of a computer programmer getting fussy about syntax; with the bits you've supplied, it's clear that's what he meant. Anyway, thank you for the explanation. Marshall
From: LauLuna on 3 Feb 2010 10:52 On Feb 3, 3:58 am, zuhair <zaljo...(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. But if your bijection existed, then it would also exist a bijection in which your wth sequence is associated with 0 and, for each natural n, the nth sequence in your table gets associated with n+1. However, this other bijection does not exist (by the diagonal argument). Hence neither yours. Regards
From: MoeBlee on 3 Feb 2010 12:01 Zuhair, It seems to me that your problem here is that you are failing to understand the principle of universal generalization. I've been telling you for a long time that your lack of study of the predicate calculus is a huge gap in your studies. Two specific points: The issue is even simpler than you've presented: We know that if there is no surjection from N onto the set of denumerable binary sequences then there is no bijection from N onto the set of denumerable binary sequences. You agree with this, I surmise. So, to prove that there is no bijection from N onto the set of denumerable binary sequences, all we have left to do is prove that, for any f that is a function from N to the set of denumerable binary sequeces, we have that f is not a surjection onto the set of denumerable binary sequences. And we do this by talking about an ARBITRARY f that is a function from N to set of denumerable binary sequences, as we then prove (via Cantor's method) that for this ARBITRARY f, it is not a surjection onto the set of denumerable binary sequences. Thus, since we assumed NOTHING about this f other than what we know about ANY f that is a function from N to the set of denumerable binary sequences, we may conclude that there is NO f that is a surjection from N onto the set of denumerable binary sequences. And so we are FINISHED. PERIOD. Also, in this context, please forget about this thing about "models" that you keep referring to. It is only confusing you and is not immediately relevant to the very simple proof that N is uncountable. MoeBlee
From: MoeBlee on 3 Feb 2010 12:05
On Feb 3, 11:01 am, MoeBlee <jazzm...(a)hotmail.com> wrote: > N is uncountable. Of course that is a typo. I meant: The set of denumerable binary sequences is uncountable. > MoeBlee |