Cantor's Diagonal?
in [Math]
|
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.
From: Peter Webb on 3 Feb 2010 01:20 > > 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. _______________________________ Yeah, and if you try and put peanut butter into your fuel tank your car will probably fail as well. Of course I picked an arrangement where I could use Cantor's argument; picking some arrangement where it doesn't work would be a complete waste of time.
From: zuhair on 3 Feb 2010 02:04 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: > > > 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 Well no doubt I am ignorant of math, that's something that I admit repeatedly. I have a lot of personal arguments, yes, no doubt, they are insignificant , also yes not doubt. However I see that my point (if it can be called as a point) is missed really. Most of the answers here were in my personal opinion irrelevant. I'll try to illustrate my point in a Naive manner. 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 ,.... so this natural order have the following properties (1) there is a starting member, i.e. a member that is not the successor of any member. (2) there is an immediate successor member for each member (3) Except the starting member every member have an immediate predecessor member.. (4) No two members have the same successor. So when N is thrown into this natural order, then if we compare N with S , then we can define a diagonal, and the diagonal argument works, since every injection from N (when thrown into this order ) to S cannot be surjective, because the counter-diagonal would be an infinite binary sequence that is in S but not in the Range of the injective function f from N(as ordered above) to S. But my question is: Is that enough to show that S is uncountable? We only compared S with a certain arrangement of N, is that sufficient to prove that there is not bijection between S and N. It definitely prove that there is no bijection between S and N as N is put in the natural order, but does that mean that we cannot have a bijection between S and N if N is put in another order. It seems that it does really, but I want the proof of that. For example lets rearrange N into an ordinal arrangement that is similar to the set w+1 Lets put the 0 to the end of all natural numbers, so lets order N in the following manner N={1,2,3,.....,0 } Now lets try to find a diagonal with N thrown into that arrangement. ... 0 , 1 , 2 , 3 , ... 1 H , O , O , H ,.... 2 O , H , H , O ,.... 3 H , H , H , H ,.... 4 O ,O , H , H ,.... .. .. .. .. 0 O, O , O, O ,... One can easily see that one cannot define a diagonal here, since 0 is the Omega_th member of N, and there is no Omega_th entry in any infinite binary sequence, so one cannot have a diagonal argument with N thrown into this arrangement. My question is: in the later situation if we don't have a diagonal, then how can we be sure that there cannot be a bijection between S and N. My point is that if we cannot define a diagonal for all arrangements of N, so how can we know from the diagonal argument per se, that no bijections are possible from N to S. Definitely there is something I am missing. Zuhair
From: Marshall on 3 Feb 2010 02:20 On Feb 2, 11:04 pm, zuhair <zaljo...(a)gmail.com> wrote: > > Lets put the 0 to the end of all natural numbers, so lets order N in > the following manner > > N={1,2,3,.....,0 } That's not a sequence. Marshall
From: zuhair on 3 Feb 2010 08:04
On Feb 3, 12:38 am, Tim Little <t...(a)little-possums.net> wrote: > On 2010-02-03, zuhair <zaljo...(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. Well that is my question in first place isn't it? you just replied with an assertion, I don't see a proof? Let me put things to you in this way, since I think it would definitely be easier. To show that any set X is uncountable, you need the following: not Exist f ( f:X --> N, f is injective ). Now in the case were X is an infinite set , then the following is enough: not Exist f (f:N --> X, f is bijective) Now lets suppose that N is comparable to X, in other words, lets suppose there exist an injection from N to X, so in this case the following would be enough to prove that X is uncountable For all f ( (f:N-->X, f is injective) -> f is not surjective ). N in all the above is of course the set of all natural numbers. Now is their an injection from N to X were X is the set of all infinite binary sequences? The answer is yes. Simply anyone can see the following with the infinite binary sequences that have only one O at one entry and the rest is H letters for all other entries: 0 <-> O H H H H H............... 1 <-> H O H H H H............... 2<-> H H O H H H.............. .. .. .. .. so there is an injection from N to the set of all binary sequences that have one O letter in them. So there exist an injection from N to X, since the set of all binary sequences that have one O letter in them is a subset of X. Now all what we need is to prove that: For all f ( (f:N-->X, f is injective) -> f is not surjective ). in words, the requirement for proving the uncountablility of X is to prove that *ALL* injections from N to X are not surjective. The question is WERE is the SET of All injections from N to X in Cantor's Diagonal argument? I personally fail to see it. Clarification: when I am saying "All injections from N to X, I mean injections within the model of ZF and not outside it" Cantor's Diagonal argument is illustrating the set of all injections from N to X, that have a special kind of order, which is the following order(see my last reply to Arturo Magidin). (1) there is a starting member, i.e. a member that is not the successor of any member. (2) there is an immediate successor member for each member (3) Except the starting member every member have an immediate predecessor member.. (4) No two members have the same successor. So actually What Cantor's Diagonal is speaking of, is the following: All injections from N to X that has the above arrangement are not surjective. Which is true, since for these particular kind of injections we can always find a diagonal and the counter diagonal would be in X but not in the range any of these injections, thus they fail to be surjective. BUT my question here is that: the set of all injections from N to X that have the above arrangement is NOT the set of all injections (within the model of ZF) from N to X. We can have injections from N to X that has an arrangement similar to that of w+1 and higher ordinals, and for these kind of injections the Diagonal argument of Cantor's fail to show that they are not surjective, simply because we CANNOT define a diagonal for those functions. The way how I see matters, is that it appears to me that the Diagonal argument didn't succeed to prove that: For *all* f ( (f:N-->X, f is injective) -> f is not surjective ). it only proved it for *some* injective functions from N to X, but not for all of them. That's why I am saying that it failed to prove that *all injections from N to X are not surjections" because it is simply not speaking of all these injections. But it seems somehow that there must be a way to prove that if all injections from N to X in the above-mentioned order(see above) are not surjective, then every injection from N to X in any other order would also be not surjective! and it is this proof that I am looking for, since I don't see that directly from the presentation of the Diagonal argument. Do you know this proof? Zuhair > > - Tim |