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: zuhair on 4 Feb 2010 08:08 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. How in hell they are *exactly* the same argument, can you tell me. What I call as the *general* argument is stated for *every* set x, it proves that for *every* set x we cannot have a surjection from x to Power(x). While what I refereed to here as the Diagonal argument is the one you have written __________________________ Quote: 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 Arturo Magidin ____________________________ were N is the set of all natural numbers right. So this argument only prove that the set of all natural numbers is smaller than its power. What the diagonal argument prove is only a special case of what the *general* argument prove. So how in hell they are EXACTLY the same argument? A real question that present itself, Can we remove the restriction on N being the set of all natural numbers. Can we have *Exactly* the same argument above but with N being *any* set, weather it is well orderable or not well orderable? If the answer is yes, then I can understand you saying that both arguments are equivalent, this would make sense to me. The second issue, I said that the general argument (and in case N can be generalized as above then both the general argument and the diagonal argument with N being any set since they would be the same argument) heavily depends on the existence of an empty set, and it is. and I showed that if we are working in a theory in which the empty set do not exist, and in which a Quine atom exist, then the power of any Quine atom would be equinumerous to any Quine atom, so in this theory Cantor's argument fail actually. however this is a limited situation. Regards Zuhair > > > 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: Arturo Magidin on 4 Feb 2010 12:26 On Feb 4, 1: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! Sigh. The only case in which X is equipollent with P(X)-{{}} is when X is a singleton. For any other kind of set, Cantor's proof can be suitably tweaked so that the argument does not produce a set that is empty. And if you are considering binary X-sequences, then the whole issue goes away entirely. So you *are* speaking nonsense, as usual. > 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. And we all know that your inability to see something is absolute proof of... nothing. > On the other hand the Diagonal argument seems to require well > ordering, Nonsense. > can you illustrate to me a Diagonal argument of a non well orderable > set, Let X be any set. Let f:X-->P(X). Define D = {x in X : x not in f(x)}. Then f(x)=/=D for all x in X. Therefore, there is no surjection X-- >P(X). If you want to see it with functions to {0,1} instead of P(X), then let B(X)= {g:X-->{0,1} | g is a function} Let f:X-->B(X) be any map. Let h:X-->{0,1} be defined as follows: h(x) = 0 if f(x)[x] = 1 h(x) = 1 if f(x)[x] = 0. Then h is a well defined map X-->{0,1}. But h =/= f(x) for any x, since h(x)=/=f(x)[x]. Therefore, there is no surjection from X to B(X). That's the THIRD TIME I've "shown" you this. At this point, you are in danger of drifting from cluelessness to dishonesty. All in the service of your willful ignorance. That *IS* the diagonal argument, silly. There is no well ordering involved except in the pretty pictures. Are you really that distracted by the shiny object that you can't even *think* because of it? > 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). See above, and don't get distracted by that ball of twine. -- Arturo Magidin
From: Arturo Magidin on 4 Feb 2010 12:35 On Feb 4, 7:08 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. > > How in hell they are *exactly* the same argument, can you tell me. I already did, you ignorant boffoon. Binary sequences N-->{0,1} correspond to subsets, by identifying a subset with its characteristic function. If A is a subset of N, then Chi_A:N-->{0,1} is the characteristic function of A, where Chi_A(n) = 1 if n in A, and Chi_A(n)=0 if n is not in A. And as I said already: (quoting) "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. " > What I call as the *general* argument is stated for *every* set x, it > proves that for *every* set x we cannot have a surjection > from x to Power(x). Yes. It is THE SAME ARGUMENT. > While what I refereed to here as the Diagonal argument is the one you > have written IT IS THE SAME ARGUMENT. A cat still has four legs, even if you call the tail a leg. Your incapacity, your ignorance, your willfulness, and your stiff-neckedness not withstanding, THEY ARE THE SAME ARGUMENT. If you are too busy looking at the pretty pictures to be able to think, then isn't it well past time you stop pretending that you are trying to understand any math and you confess that all you are interested in is being an ignoramus? > __________________________ > > Quote: > > 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 > > Arturo Magidin > ____________________________ > > were N is the set of all natural numbers right. > > So this argument only prove that the set of all natural numbers is > smaller than its power. ITS THE SAME ARGUMENT. > What the diagonal argument prove is only a special case of what the > *general* argument prove. No, it does not. ITS THE SAME ARGUMENT. Given a function g:X-->2^X, It constructs the function h:X-->{0,1} by letting h(x) = 0 if g(x)[x]=1 and h(x)=1 if g(x)[x]=0. It's EXACTLY THE SAME ARGUMENT as the diagonal function. > > So how in hell they are EXACTLY the same argument? In the obvious way. > A real question that present itself, Can we remove the restriction on > N being > the set of all natural numbers. Can we have *Exactly* the same > argument above > but with N being *any* set, weather it is well orderable or not well > orderable? Yes, as I've shown you four times *this* *thread* *alone*. There is no question. > If the answer is yes, then I can understand you saying that both > arguments are equivalent, this would make sense to me. The arguments are not even "equivalent". THEY ARE IDENTICAL except for the pretty picture that is sometimes drawn to explain it to those who have trouble with abstractions. > The second issue, I said that the general argument (and in case N can > be generalized as above then both the general argument and the > diagonal argument > with N being any set since they would be the same argument) heavily > depends on the existence of an empty set, and it is. The argument can be easily made to work for any set with more than one element. > and I showed that if we are working in a theory in which the empty set > do not exist, and in which a Quine atom exist, then the power of any > Quine atom would be equinumerous to any Quine atom, so in this theory > Cantor's argument fail actually. > > however this is a limited situation. Ya think? -- Arturo Magidin
From: Arturo Magidin on 4 Feb 2010 12:44 On Feb 4, 2:02 am, zuhair <zaljo...(a)gmail.com> wrote: > On Feb 4, 2:13 am, Virgil <Vir...(a)home.esc> wrote: > > 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, Sigh. The set of binary X-functions (maps X-->{0,1}) (which, when X=N, is the set of binary sequences, since a "sequence" is a function whose domain is N) is in one-to-one, natural, bijective correspondence with the power set of X. Given a subset A of X, the binary X-function Chi_A: X-->{0,1} defined by Chi_A(x) = 1 if x is in A, Chi_A(x)=0 if x is not in A, known far and wide as the "characteristic function of A" is a binary X-function. Given a binary X-function f:X-->{0,1}, the set A_f = { x in X : f(x) = 1} is a subset of X. The correspondences A|-> Chi_A, f|->A_f are inverses of each other: A_{Chi_A} = {x in X : Chi_A(x) = 1} = {x in X: x in A} = A. Chi_{A_f}(x) = 1 if and only if x in A_f, if and only if f(x)=1, so Chi_{A_f}(x)=f(x) for all x, so Chi_{A_f}=f. Since the correspondences are inverses of each other, the set of binary X-functions and the power set of A are in bijective correspondence. > 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* No. You need to use binary X-functions. > i.e. well orderable even if uncountable Nonsense. You are so lost in the pretty pictures you don't know what you are talking about. As usual. > 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? In the exact way that YOU'VE BEEN TOLD HUNDREDS OF TIMES ALREADY. -- Arturo Magidin
From: MoeBlee on 4 Feb 2010 13:57
Zuhair, did you read my post? What do you get when you consider the very simple situation I described? |