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 7 Feb 2010 10:36 On Feb 7, 8:48 am, zuhair <zaljo...(a)gmail.com> wrote: > On Feb 4, 12:35 pm, Arturo Magidin <magi...(a)member.ams.org> wrote: > > > > > > > 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. " > > That is still not clear to me. If anybody can further clarify that, it > would be of great help. > > Let me try: > > first let me begin with the characteristic function: > > The definition given above is: > > 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. > > Let A be the set of all even numbers, so A={ 2n| n e N } > > What is the characteristic function of A? > > Chi_A= {<0,1>,<1,0>,<2,1>,<3,0>,....} > > Now lets replace each subset A of N by its characteristic function > Chi_A, and then apply the apply the general argument to it. > > The diagonal of the general argument is defined by > > For every f:N->P(N) > > D_f={x | x e N & ~ x e f(x)} > > Now lets replace P(N) by the set of all characteristic functions of > subsets of N > > let f:N --> {Chi_A| A subset of N} > > Now each characteristic function is a set of ordered pairs of elements > of N, while elements of N on the other hand are not ordered pairs of > its elements. > > so N and {Chi_A| A subset of N} are disjoint sets. > > Now lets apply the diagonal of the general argument to f > > we'll have > > For all f: D_f = N. > > and as we know N is not a member of {Chi_A| A subset of N} > > Now although N is not in the range of f, but N is not in the co-domain > of f, > so we cannot conclude that every function f such that > f:N --> {Chi_A| A subset of N} is not surjective. > > This mean that replacing each subset N with its characteristic > function > and applying the general argument, would not result in any proof of > N being strictly smaller than the set of all characteristic functions > of subsets of N. > > This mean that the two arguments are not the same arguments. > > Also the other way round cannot be done, we cannot go to the Diagonal > argument > and replace each sequence to its inverse characteristic function which > would be a subset of N of course, then we define a function from each > member of N to > these subsets of N using notations like g(n) n or so, since subsets of > N do not contain ordered pairs of N as their elements. correction .... ordered pairs of *elements* of N as their elements. > > so attempt of translating each arguments into the other fails > bidirectionally. > > However there is another way of looking at matters, we can translate > from maps to subsets of N using these characteristic functions *after* > diagonalization has been made, and not prior to diagonalization as in > the attempts above. > > So from the general argument translate each subset A of N to its > characteristic function i.e. to Chi_A , and we also translate the > Diagonal D_f={x:xeN & ~ x e f(n)} > to its characteristic function Chi_(D_f), and then we prove that > Chi_(D_f) is the same diagonal we get from the Diagonal argument, > which must be the case. > > But the problem is that this is not always the case, for example using > the general argument we can have the empty set as the diagonal of each > function f:N-->P(N) > were n e f(n) for every n e N. So the Diagonal of these functions > would be the empty set. > > Now what would be the Characteristic function of { }, it must be > {<{ }, 1> }, but > this set is not a map from N to {0,1}. > > Now lets go to the other direction, i.e. lets attempt to translate > from > the Diagonal argument to the General argument. > > So we'll translate each map and the diagonal as well, to its > corresponding > subset of N using inverse characteristic functions, now the diagonal > would be > the diagonal of argument 1. > > So it seems from the above, unless i am mistaken (which might be the > most likely case), that the Diagonal argument is a sub-argument of > the general argument. > > All the above is speaking in Z, or any theory that proves the > bijection between > subsets of N and their characteristic functions. > > However this bijective correspondence might fail in other set > theories, and I gave an example of such a theory T that do not have > an empty set, and that have > Quine atoms, and lets say it has two primitive constants O and H > so now the set of all maps f:Q -> {O,H} would be {<Q,O>, <Q,H>} > which is bigger than the power set of Q which is Q itself, since we > have Q={Q} > since Q is a Quine atom. > > We can actually construct infinite number of set theories in which > this bijective correspondence fails, and these two arguments would not > work in the same manner as its thought, even one argument would not be > a sub-argument of the other. > > So it appears to me that under Z, the two arguments are NOT the same > argument > and that the Diagonal argument is a sub-argument of the general > argument. > > However in other theories T in which the bijective correspondence > Power(x) and the {f | f:X --> {H,O}} fails, then these two arguments > are separate arguments. > > Zuhair > > > > > > > > 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 > > ... > > read more »
From: Jesse F. Hughes on 7 Feb 2010 10:45 Frederick Williams <frederick.williams2(a)tesco.net> writes: > "Jesse F. Hughes" wrote: > >> In any case, I don't know of any serious researcher (sorry, Zuhair) >> who works in a set theory without the empty set, so it's a bit >> disingenuous to worry about whether the two proofs really are the same >> in such a theory. > > I may know of one who's now dead. If I was supposed to get that reference, I missed it. -- Jesse F. Hughes "You know that view most people have of mathematicians as brilliant people? What if they're not?" -- James S. Harris
From: Mike Terry on 7 Feb 2010 10:52 "zuhair" <zaljohar(a)gmail.com> wrote in message news:2a51fa70-59c3-48a4-a694-608f8dcf5d67(a)m16g2000yqc.googlegroups.com... > On Feb 4, 12:35 pm, Arturo Magidin <magi...(a)member.ams.org> wrote: > > 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. " > > > That is still not clear to me. If anybody can further clarify that, it > would be of great help. > > Let me try: > > first let me begin with the characteristic function: > > The definition given above is: > > 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. > > Let A be the set of all even numbers, so A={ 2n| n e N } > > What is the characteristic function of A? > > Chi_A= {<0,1>,<1,0>,<2,1>,<3,0>,....} > > Now lets replace each subset A of N by its characteristic function > Chi_A, and then apply the apply the general argument to it. > > The diagonal of the general argument is defined by > > For every f:N->P(N) > > D_f={x | x e N & ~ x e f(x)} > > Now lets replace P(N) by the set of all characteristic functions of > subsets of N > > let f:N --> {Chi_A| A subset of N} > > Now each characteristic function is a set of ordered pairs of elements > of N, while elements of N on the other hand are not ordered pairs of > its elements. > > so N and {Chi_A| A subset of N} are disjoint sets. > > Now lets apply the diagonal of the general argument to f > > we'll have > > For all f: D_f = N. I'm sure you are being *deliberately* obtuse here. The point that has been made is that: 1) there is a natural bijection between P(N) and {0,1}^N 2) the proof that P(N) is not countable (special case of X and P(X) not being equinumerous) and the proof that {0,1}^N is not countable (by considering binary sequences) use "exactly the same argument", in view of the natural bijection. I.e. if we are given f: N-->{0,1}^N this "naturally" corresponds to a g: N-->P(N) and the diagonal argument (for showing X and P(X) are not equinumerous) gives us a G in P(N) such that: Ax in N: g(x) != G, so g is not surjective. The set G corresponds naturally to an F in {0,1}^N, and clearly we have Ax in N: f(x) != F, showing that f is not surjective. Furthermore, when you look at the Cantor proof that f is not surjective (looking at binary sequences), you see that it is constructing the exact same F as we would get above by mapping back and forth between P(N) and {0,1}^N as required in the obvious manner. In fact, considering the naturalness of the bijection between P(N) and {0,1}^N, most people would have no trouble asserting that the proofs are using "exactly the same argument". Anyone who understands the general powerset proof, and who is aware of the natural bijection between P(N) and {0,1}^N, would have no difficulty proving the binary-sequence proof by applying "the same argument". Note, this doesn't mean that the proofs are line by line identical - that's misinterpreting the meaning of the phrase "exactly the same argument" - argument and proof are not synonyms! So... you are (deliberately I suspect) misapplying the "general argument" to f. You should not be applying the powerset-proof argument directly against the ordered pairs making up the functions Chi_A etc., but rather, mapping back and forth between P(N) and {0,1} as required to apply the argument... > [snip consequences of mistaken application of general argument] > > This mean that the two arguments are not the same arguments. > No it doesn't. It is true that whether the two arguments are "exactly the same" is a matter of common sense interpretation, and a matter of having sufficient insight into the structure of the two proofs to apply common sense. I.e. the question is not purely a mathematical question, so nobody can prove to you that the arguments are EXACTLY the same if you don't have the common sense / insight to see it... Mike.
From: Frederick Williams on 7 Feb 2010 10:58 "Jesse F. Hughes" wrote: > > Frederick Williams <frederick.williams2(a)tesco.net> writes: > > > "Jesse F. Hughes" wrote: > > > >> In any case, I don't know of any serious researcher (sorry, Zuhair) > >> who works in a set theory without the empty set, so it's a bit > >> disingenuous to worry about whether the two proofs really are the same > >> in such a theory. > > > > I may know of one who's now dead. > > If I was supposed to get that reference, I missed it. Well, I *think* that Frege didn't believe in the empty set. -- Mathematics is a part of physics. Physics is an experimental science, a part of natural science. Mathematics is the part of physics where experiments are cheap. (V.I. Arnold)
From: Jesse F. Hughes on 7 Feb 2010 10:56
zuhair <zaljohar(a)gmail.com> writes: > On Feb 7, 9:09 am, "Jesse F. Hughes" <je...(a)phiwumbda.org> wrote: >> zuhair <zaljo...(a)gmail.com> writes: >> > However this bijective correspondence might fail in other set >> > theories, and I gave an example of such a theory T that do not have >> > an empty set, and that have Quine atoms, and lets say it has two >> > primitive constants O and H so now the set of all maps f:Q -> {O,H} >> > would be {<Q,O>, <Q,H>} which is bigger than the power set of Q >> > which is Q itself, since we have Q={Q} since Q is a Quine atom. >> >> If you don't have the empty set, then it's pretty hard to have >> separation. Without separation, it's hard to guess just what >> constructions are available in your pet theory. > > Yes, you can have a modified form of separation. > > Exist y (P(y)) -> For all A exist x for all y ( y e x <-> ( y e A & > P(y) ) ) > > that is not difficult at all, actually we can build a whole set > theory in a ZF like fashion without the empty set, that's not > difficult. It's not clear to me just how well this modified form of separation allows the usual constructions. Maybe it's obvious to you, but not to me. Anyway, I haven't been following this thread closely and don't care to take the time to explain Arturo's point here. So, pardon me for not responding to the rest of your post. -- "People think there are brilliant people at important government agencies like the NSA or CIA that will save them, when I know, sadly, that mathematicians rule the roosts in the key places in all the major government agencies, even the shadowy ones." -- James S. Harris |