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: Virgil on 4 Feb 2010 00:04 In article <c3c98452-4379-412c-8eda-26b5e55460c7(a)k2g2000pro.googlegroups.com>, "Ross A. Finlayson" <ross.finlayson(a)gmail.com> wrote: > Yes it is well known that the binary case requires refinement and > there is one anti-diagonal, of the matrix expansion of the elements. If one goes by the "infinite matrix" model of a proof, it is quite easy to show that there are at least as many anti-diagonals as there are rows in that infinite matrix, one for each natural number (including zero) offset before starting to anti-diagonalize.
From: zuhair on 4 Feb 2010 00:55 On Feb 3, 1:14 pm, Arturo Magidin <magi...(a)member.ams.org> wrote: > 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 Ok, Thanks. I know now were was my mistake, the diagonal is not necessarily the linear diagonal I always thought of. With this clarification I can see that actually one can define a diagonal over actually any countable set! so my first example in the head post was erroneous, it is just the case that the diagonal over w+1 have a different shape when illustrated from the diagonal over N, although N itself can have infinitely many shapes of diagonals, all the matters were illustrative matters, and you are correct in saying that they are not the essence of the argument itself. Now I *SEE* this so called *Diagonal* argument. It seems to me that a modification of this argument can actually work for every well orderable set, however I don't know if a modification of this argument can be made general enough to prove that the power of every non well orderable set is bigger than it. The other proof does that for all sets, so it seems to be more general than the diagonal argument, however what I dislike of the later proof is that it seems to rely heavily on the existence of the empty set which is something that I don't like although it is almost universally acceptable, the diagonal argument on the other hand is not affected by weather the empty set exist or not. Regards. Zuhair
From: Arturo Magidin on 4 Feb 2010 01:04 On Feb 3, 11:55 pm, zuhair <zaljo...(a)gmail.com> wrote: > > Now I *SEE* this so called *Diagonal* argument. Given your comments below, NO, you don't. You still don't understand it and you are just fooling yourself. As usual. > > It seems to me that a modification of this argument can actually work > for every well orderable set, however I don't know if a modification > of this argument can be made general enough to prove that the power of > every non well orderable set is bigger than it. There is no "modification" needed. The argument IS EXACTLY THE SAME ARGUMENT that shows that no set is bijectable with its power set. > The other proof There is no "other" proof. THEY ARE THE SAME ARGUMENT. THEY ARE THE SAME PROOF. > does > that for all sets, so it seems to be more general than the diagonal > argument, THEY ARE THE EXACT SAME ARGUMENT. > however what I dislike of the later proof is that it seems > to rely heavily on the existence of the empty set No, it does not. You are, as usual, speaking nonsense. > which is something > that I don't like although it is almost universally acceptable, the > diagonal argument on the other hand is not affected by weather the > empty set exist or not. Nonsense. You are, as usual, spewing hot air and pretending you are making sense. -- Arturo Magidin
From: Virgil on 4 Feb 2010 02:13 In article <8150b996-fe50-4183-a302-39fe99725732(a)k19g2000yqc.googlegroups.com>, zuhair <zaljohar(a)gmail.com> wrote: > On Feb 3, 1:14�pm, Arturo Magidin <magi...(a)member.ams.org> wrote: > > 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 > > Ok, Thanks. I know now were was my mistake, the diagonal is not > necessarily the linear diagonal I always thought of. With this > clarification I can see that actually one can define a diagonal over > actually any countable set! so my first example in the head post was > erroneous, it is just the case that the diagonal over w+1 have a > different shape when illustrated from the diagonal over N, although N > itself can have infinitely many shapes of diagonals, all the matters > were illustrative matters, and you are correct in saying that they are > not the essence of the argument itself. > > Now I *SEE* this so called *Diagonal* argument. > > It seems to me that a modification of this argument can actually work > for every well orderable set, however I don't know if a modification > of this argument can be made general enough to prove that the power of > every non well orderable set is bigger than it. The standard proof that the cardinality of a power set is greater than that of the base set in no way requires that either of the sets be ordered, much less well ordered. > > Regards. > > Zuhair
From: zuhair on 4 Feb 2010 02:53
On Feb 4, 1:04 am, Arturo Magidin <magi...(a)member.ams.org> wrote: > On Feb 3, 11:55 pm, zuhair <zaljo...(a)gmail.com> wrote: > > > > > Now I *SEE* this so called *Diagonal* argument. > > Given your comments below, NO, you don't. You still don't understand > it and you are just fooling yourself. As usual. > > > > > It seems to me that a modification of this argument can actually work > > for every well orderable set, however I don't know if a modification > > of this argument can be made general enough to prove that the power of > > every non well orderable set is bigger than it. > > There is no "modification" needed. The argument IS EXACTLY THE SAME > ARGUMENT that shows that no set is bijectable with its power set. > > > The other proof > > There is no "other" proof. THEY ARE THE SAME ARGUMENT. THEY ARE THE > SAME PROOF. > > > does > > that for all sets, so it seems to be more general than the diagonal > > argument, > > THEY ARE THE EXACT SAME ARGUMENT. > > > however what I dislike of the later proof is that it seems > > to rely heavily on the existence of the empty set > > No, it does not. You are, as usual, speaking nonsense. Oh yes it does, there is no doubt about that at all, you are absolutely wrong about that point. Take a set theory T were the empty set do not exist, and in which a Quine atome Q exist as a set, let's say that T can define powers for every set. Now we have Power(Q)=Q would be a theorem of T, since there is no empty set! so in T we don't have the rule that for every set x, power(x) strictly supernumerous to x. The standard proof do heavily depend on the *existence* of the empty set, without it I can hardly see how it works. On the other hand the Diagonal argument seems to require well ordering, can you illustrate to me a Diagonal argument of a non well orderable set, for instance consider Power(Omega) as non well orderable set, then can you prove to me using the Diagonal argument i.e. using binary series of size Power(Omega) that Power(Omega) < 2^ Power(Omega). Zuhair > > > which is something > > that I don't like although it is almost universally acceptable, the > > diagonal argument on the other hand is not affected by weather the > > empty set exist or not. > > Nonsense. You are, as usual, spewing hot air and pretending you are > making sense. > > -- > Arturo Magidin |