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: Arturo Magidin on 3 Feb 2010 13:14 On Feb 3, 1:04 am, zuhair <zaljo...(a)gmail.com> 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: > > > > 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. The problem isn't that you are ignorant, the problem is that you are WILLFULLY ignorant. > 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. Actually, no. Your "point" was not missed. You, on the other hand, clearly failed to actually read my reply. So thanks for wasting everyone's time with your willfulness, as usual. > Most of the answers here were in my personal opinion irrelevant. No, they weren't. You just don't want to bother understanding them, as that would undermine that ignorance you are so proud of. > 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. No, it does not. The diagonal argument does not in fact use the order of N in any way; you are confusing the ILLUSTRATION of the argument with the argument itself. What is truly laughable is that you claim to accept the "general" argument that no set can be bijected with its power set, but object to this. The reason it is laughable is that in the incarnation you have chosen (maps from N to binary sequences) what you have *IS* a map from N to its power set. The "diagonal argument" here is ->exactly<- the same as the argument in Cantor's Theorem. Here's why: a sequence of 0's and 1's is a map from N to {0,1}. The maps from N to {0,1} are in one-to-one bijective correspondence with the subsets of N, by letting the function f:N-->{0,1} correspond to the set {n in N | f(n) = 1}. (That is, interpreting f as the characteristic function of the set). So what is the diagonal argument, then? Well: let B be the set of all binary sequences; this is the set B = { f:N-->{0,1} }. If f is in B, let us use f[k] to denote the kth term of the sequence. Now let g:N-->B be any function. We usually "illustrate" this function as a list, by putting g(0) first, g(1) next, then g(2), etc. But that is just a way of illustrating the function (just like a graph). It's not the actual function. What is the "diagonal" binary sequence? We define a function h:N--> {0,1} as follows: given n in N, let h(n) = 0 if g(n)[n] = 1, and we define h(n)=1 if g(n)[n] = 0. There is no "order" in this definiiton. Now, is h = g(k) for some k? No. Because h(k) =/= g(k)[k] by construction. So h =/= g(k). This holds for all k. Therefore, h is not in Im(g), so g is not surjective. QED Nowhere was the "usual order" of N 'used'. Now, if you describe the argument by writing your sequences as horizontal lists that extend infinitely to the right f[0], f[1], f[2], f[3], ..., f[n], ... and you describe the function g as an infinite list that extends infinitely down g(0) = g(0)[0] g(0)[1] g(0)[2] g(0)[3] g(0)[4] ... g(1) = g(1)[0] g(0)[1] g(1)[2] g(1)[3] g(1)[4] ... . . . , . . g(n) = g(n)[0] g(n)[1] g(n)[2] g(n)[3] g(n)[4]... . . . *then* you can "visualize" the definition of h as going "down the diagonal". Of course, if you illustrate g differently (by putting "0 at the end", e.g., as omega+1), then the visualization of the definition of h *of course* is not the same as if you list it in the usual ordering. The visualization changes because you have changed the way in which you are visualizing the function g. But the argument is still the same. In short: you are confusing what the name of the song is called with the song. Now, your other confusion lied in saying that, for some reason, the proof should take "any" countable set, not just N. That is, you seem to be saying that in order to prove that a set X is not countable, it is not enough to show (1) For all f (if f is a function from N to X then f is not surjective) but rather that you need to show (2) For all A, for all f (if A is countable, and f is a function from A to X, then f is not surjective). But (2) *trivially* follows from (1): if A is countable and f is any function from A to X, then: if A is infinite, let g:N-->A be a bijection (possible since A is countable). Then gf is a function N-- >X, hence gf is not surjective by (1). Since g is bijective, the fact that gf is not surjective implies that f is not surjective. And if A is finite, then enlarge it to make a countable infinite set A', and extend f any which way to f' defined on all of A'. Then f' is not surjective by the previous argument, and therefore its restriction f is also not surjective. So (2) trivially follows from (1). And (1) does not use the natural ordering of the natural numbers, except in the illustration of it. > 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? Of course it is. > Definitely there is something I am missing. A desire to stop being ignorant, perhaps, instead of flaunting that ignorance? -- Arturo Magidin
From: Virgil on 3 Feb 2010 13:53 In article <11fe4ef3-cfb8-4511-8e9f-2ed04f4ac207(a)c4g2000yqa.googlegroups.com>, zuhair <zaljohar(a)gmail.com> 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: > > > > > 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 How does one even DEFINE N without using the "natural ordering"? I know of no such way f defining or specifying N that does not require the use of that natural ordering, at least indirectly. WWhen you can show us such a definition or specification, only then will your argument have any foundation.
From: Tonico on 3 Feb 2010 13:59 On Feb 3, 3:04 pm, zuhair <zaljo...(a)gmail.com> wrote: > 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 ). No, I don't...who told you that?? I could, for example, try to show that there's exist an injection T --> X , with T an uncountable set, or I could try to show that there exists some surjection X --> T, with, again, T an uncountable set. Tonio
From: Tim Little on 3 Feb 2010 16:32 On 2010-02-03, zuhair <zaljohar(a)gmail.com> wrote: > Well that is my question in first place isn't it? I have no idea. According to the thread structure in my newsreader, you didn't start with a question, you started with an assertion that the diagonal argument was insufficient. > Let me put things to you in this way, since I think it would > definitely be easier. Okay. > Now in the case were X is an infinite set , then the following is > enough: > > not Exist f (f:N --> X, f is bijective) Correct. Furthermore it is sufficient to show that not Exist f (f:N-->X, f is surjective), since every bijective function is surjective. We need not concern ourselves with whether f is injective or not. > Now all what we need is to prove that: > > For all f ( (f:N-->X, f is injective) -> f is not surjective ). No we don't. We need merely prove For all f ((f:N-->X) -> f is not surjective). > The question is WERE is the SET of All injections from N to X in > Cantor's Diagonal argument? The proof does not need to involve a SET of All such functions. Such a SET need not even exist in the theory. > Clarification: when I am saying "All injections from N to X, I mean > injections within the model of ZF and not outside it" That's obvious, since a theorem cannot quantify over objects outside its universe. > Cantor's Diagonal argument is illustrating the set of all injections > from N to X, that have a special kind of order Whoops, there you go again with this irrelevant "order" thing. Order makes no difference. > 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. That's not a question, it's an assertion. It's even an assertion that doesn't make sense, since functions do not require their domains to be ordered. The mathematical essence of the diagonal argument is simply this: For any f:N-->2^N, there exists g in 2^N such that for all n in N, g(n) != f(n)(n), hence g not in range(f), and so f not surjective. That typically gets illustrated by an example with a pretty picture which may vaugely imply some particular ordering, but one should not confuse the picture with the proof itself. > 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! Where in the definition of injection and surjection do you see any mention of ordering? - Tim
From: Arturo Magidin on 3 Feb 2010 17:09
On Feb 3, 12:14 pm, Arturo Magidin <magi...(a)member.ams.org> wrote: > What is truly laughable is that you claim to accept the "general" > argument that no set can be bijected with its power set, but object to > this. The reason it is laughable is that in the incarnation you have > chosen (maps from N to binary sequences) what you have *IS* a map from > N to its power set. The "diagonal argument" here is ->exactly<- the > same as the argument in Cantor's Theorem. > > Here's why: a sequence of 0's and 1's is a map from N to {0,1}. The > maps from N to {0,1} are in one-to-one bijective correspondence with > the subsets of N, by letting the function f:N-->{0,1} correspond to > the set {n in N | f(n) = 1}. (That is, interpreting f as the > characteristic function of the set). > > So what is the diagonal argument, then? Well: let B be the set of all > binary sequences; this is the set B = { f:N-->{0,1} }. If f is in B, > let us use f[k] to denote the kth term of the sequence. > > Now let g:N-->B be any function. We usually "illustrate" this function > as a list, by putting g(0) first, g(1) next, then g(2), etc. But that > is just a way of illustrating the function (just like a graph). It's > not the actual function. > > What is the "diagonal" binary sequence? We define a function h:N--> > {0,1} as follows: given n in N, let h(n) = 0 if g(n)[n] = 1, and we > define h(n)=1 if g(n)[n] = 0. And, if you interpret elements of B as subset of N (by thinking of the elements of B as characteristic functions, and identifying the characteristic function with the corresponding subset), then what is the subset h? It is the set of those elements n of N such that n is not an element of g(n) (that is, h(n)=1 if and only if g(n)[n]=0). That is, the diagonal number h is *exactly* *the* *same* as the diagonal set you get in the proof of Cantor's Theorem that any function g:X-->P(X) is not surjective. -- Arturo Magidin |