Cantor's Diagonal?
in [Math]
|
From: zuhair on 4 Feb 2010 03:02 On Feb 4, 2:13 am, Virgil <Vir...(a)home.esc> wrote: > In article > <8150b996-fe50-4183-a302-39fe99725...(a)k19g2000yqc.googlegroups.com>, > > > > > > zuhair <zaljo...(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. Agreed, provided what you mean by the standard proof the one in which prove that *every* function from a set to its power is not surjective. The diagonal argument is speaking of binary sequences, so the matter is different, the diagonal argument is a special case of the standard proof, but it is not equivalent to it, to generalize the diagonal argument we need to use binary sequences of uncountable sizes, and they must be *sequences* i.e. well orderable even if uncountable (although the standard definition of an infinite binary sequence is that of a map from N to {0,1}, but yet this can be extended to higher cardinals so we can have a higher sequence as a map from Aleph_i to {0,1} were i is an ordinal), I can hardly imagine a sequence from for example an uncountable non well orderable set X as a map from X to {0,1}, that doesn't not seem to be a sequence, even if we presume that how can we illustrate the diagonal with such non well orderable set X, how can we prove that X is not bijective to its power using the diagonal argument? Zuhair Zuhair > > > > > > > Regards. > > > Zuhair
From: Herman Jurjus on 4 Feb 2010 05:03 zuhair wrote: > 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 It appears that your interpretation of what counts as 'diagonal argument' is too narrow. Something like the following is usually also referred to as a diagonal argument: Let X be any set, and f: X -> P(X) be any function. Define D = { x in X | x is-not-an-element-of f(x) }. Then D is an element of P(X). Hence, if f were surjective, then we'd have, for some x in X, f(x) = D. But Then x \in D iff x not in D. Contradiction. Therefore, there exists no surjection from X to P(X). And even something like this: There exists no countable set that contains all subsets of N. Proof: Let X be any countable set, and f: N -> X a bijection. Define D = { n in N | f(n) is not a set or n is-not-an-element-of f(n) }. Then D is a subset of N. But D is not an element of X, otherwise there would be a k in N such that f(k) = X, and we'd have a contradiction (k in D iff k not in D). Note that, for the latter argument to make sense, you don't even have to accept the power set axiom. You wouldn't even have to accept the existence of any uncountable sets at all, btw. -- Cheers, Herman Jurjus
From: Tonico on 4 Feb 2010 06:14 On Feb 4, 9:53 am, zuhair <zaljo...(a)gmail.com> wrote: > 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 It's almost unbelievable that after ALL the explanations you've been given you still have the nerve, and the wilful ignorance, to write all the nonsense above: the proof that Power(Omega) < 2^Power(Omega) doesn't depend on ordering, well or bad, and it never minds if you call your set Power(Omega), Power Off or Power Ranger....can't you see this? The argument using the map that Russell's Paradox presented, and which gives the proof for the above almost at once, remains the same... Tonio
From: zuhair on 4 Feb 2010 07:34 On Feb 4, 5:03 am, Herman Jurjus <hjm...(a)hetnet.nl> wrote: > zuhair wrote: > > 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 > > It appears that your interpretation of what counts as 'diagonal > argument' is too narrow. Yes, what I mean by the diagonal is the kind of argument that deal with infinite binary sequences. I don't mean the other arguments, although I know they are called diagonal arguments,but still here in this thread I am not referring to them when I am mentioning the diagonal argument. Zuhair > > Something like the following is usually also referred to as a diagonal > argument: > > Let X be any set, and f: X -> P(X) be any function. Define > D = { x in X | x is-not-an-element-of f(x) }. > Then D is an element of P(X). Hence, if f were surjective, then we'd > have, for some x in X, f(x) = D. But Then x \in D iff x not in D. > Contradiction. Therefore, there exists no surjection from X to P(X). > > And even something like this: > > There exists no countable set that contains all subsets of N. > Proof: Let X be any countable set, and f: N -> X a bijection. > Define > D = { n in N | f(n) is not a set or n is-not-an-element-of f(n) }. > Then D is a subset of N. But D is not an element of X, otherwise > there would be a k in N such that f(k) = X, and we'd have a > contradiction (k in D iff k not in D). > > Note that, for the latter argument to make sense, you don't even have to > accept the power set axiom. You wouldn't even have to accept the > existence of any uncountable sets at all, btw. > > -- > Cheers, > Herman Jurjus
From: zuhair on 4 Feb 2010 07:38
On Feb 4, 6:14 am, Tonico <Tonic...(a)yahoo.com> wrote: > On Feb 4, 9:53 am, zuhair <zaljo...(a)gmail.com> wrote: > > > > > > > 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 > > It's almost unbelievable that after ALL the explanations you've been > given you still have the nerve, and the wilful ignorance, to write all > the nonsense above: the proof that Power(Omega) < 2^Power(Omega) > doesn't depend on ordering, well or bad, and it never minds if you > call your set Power(Omega), Power Off or Power Ranger....can't you see > this? First which proof you are speaking about, if you mean the one which proves that all functions from any set X to its power are not surjective, then I am not speaking of this proof, I know that this one doesn't depend on Choice, or any kind of ordering, I know it is a theory of Z. So don't mix up matters. I was speaking of the diagonal argument that uses infinite binary sequences, and not of the other kinds of arguments (although Arturo say they the same). > The argument using the map that Russell's Paradox presented, and which > gives the proof for the above almost at once, remains the same... what Russell's paradox has to do with this? > > Tonio |