Cantor's Diagonal?
in [Math]
|
From: William Hughes on 7 Feb 2010 15:47 On Feb 7, 3:48 pm, zuhair <zaljo...(a)gmail.com> wrote: > when one use a terminology like *Exactly* the > same, or *identical*, one would expect the existence of a rigorous > formal proof of this claim, Nope, you would use the term "exactly" when the proofs are so similar, that the only way to deny they are the same is to be obtuse. In this case both arguments start with a mapping and lead to the same set which is not in the image of the mapping. The term exactly seems more than appropriate. -William Hughes
From: Arturo Magidin on 7 Feb 2010 16:29 On Feb 7, 7:48 am, zuhair <zaljo...(a)gmail.com> wrote: > On Feb 4, 12:35 pm, Arturo Magidin <magi...(a)member.ams.org> wrote: > > > 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 You are already well on your way to confusing yourself. A was the set of even numbers. Now A is an arbitrary variable standing for an arbitrary subset of N. Which is it? > 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. This is irrelevant to the argument. > so N and {Chi_A| A subset of N} are disjoint sets. Irrelevant. > Now lets apply the diagonal of the general argument to f > > we'll have > > For all f: D_f = N. No. When you apply the diagonal argument to characteristic function (which are function from N to {0,1}, you are to get a characteristic function. The characteristic function you get is D_f = { <n, 1- f(n)[n]> : n in N} The function whose value at n is 1 if f(n)[n] is 0, and 0 if f(n)[n]=1. Remember? That's what the argument for binary sequences was, and that is what {Chi_A|A subset of N} is: it is the set of all binary sequences. > and as we know N is not a member of {Chi_A| A subset of N} You are confused. You aren't "translating", you are trying to feed English words to a Russian dictionary. You are supposed to TRANSLATE the argument, not just the inputs. > > 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. It means you (i) didn't understand and (ii) don't know what you are doing and (iii) are still clueless. The arguments, however, are the same argument. See: if you are going to apply the argument to binary N-functions, then you use the definition applicable to binary N-functions. If you are going to apply it to subsets, you use the definition that applies to subsets. Instead, you are trying to apply the definition for subsets to the binary N-function, and then complain that it doesn't make sense. It is exactly as if you were trying to translate a book by only translating every other word instead of the entire sentence, and then claimed that translation was impossible because the result didn't make sense. > so attempt of translating each arguments into the other fails > bidirectionally. Your *flawed* attempt failed, because it was wrongheaded. Purposely so, I suspect, because I find it hard to believe that *anyone* could be so clueless as you have presented yourself to be for so long. > 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. You think? Perhaps translating the entire thing instead of just piecemeal might yield a translation that actually makes sense? Miracle of miracles! > 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}. No, silly. Again: if A is *any* subset, then Chi_A(n) = 0 if n not in A, and 1 if n is in A. So if A is the empty set, then Chi_A(n) =0 for all n. So the characteristic function of the empty set AS A SUBSET OF N is { <n,0> : n in N}. Characteristic functions of SUBSETS don't depend only on the set you are looking at, they depend on the ambient set. They are defined on the AMBIENT set, and are defined in terms of the subspace. In this argument, you are looking at the characteristic functions of the subsets of X, so they always have domain X. The "characteristic function of the empty set" AS A SUBSET OF N is different from the characteristic function of the empty set as a subset of any set Y with Y=/=N. > 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. The "diagonal argument" IS the general argument. They are the same argument, if you aren't purposely dishonest or obtuse. -- Arturo Magidin
From: zuhair on 7 Feb 2010 16:44 On Feb 7, 4:29 pm, Arturo Magidin <magi...(a)member.ams.org> wrote: > On Feb 7, 7:48 am, zuhair <zaljo...(a)gmail.com> wrote: > > > > > > > On Feb 4, 12:35 pm, Arturo Magidin <magi...(a)member.ams.org> wrote: > > > > 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 > > You are already well on your way to confusing yourself. A was the set > of even numbers. Now A is an arbitrary variable standing for an > arbitrary subset of N. Which is it? > > > > > 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. > > This is irrelevant to the argument. > > > so N and {Chi_A| A subset of N} are disjoint sets. > > Irrelevant. > > > Now lets apply the diagonal of the general argument to f > > > we'll have > > > For all f: D_f = N. > > No. When you apply the diagonal argument to characteristic function > (which are function from N to {0,1}, you are to get a characteristic > function. The characteristic function you get is > > D_f = { <n, 1- f(n)[n]> : n in N} The function whose value at n is 1 > if f(n)[n] is 0, and 0 if f(n)[n]=1. Remember? That's what the > argument for binary sequences was, and that is what {Chi_A|A subset of > N} is: it is the set of all binary sequences. > > > and as we know N is not a member of {Chi_A| A subset of N} > > You are confused. You aren't "translating", you are trying to feed > English words to a Russian dictionary. You are supposed to TRANSLATE > the argument, not just the inputs. > > > > > 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. > > It means you (i) didn't understand and (ii) don't know what you are > doing and (iii) are still clueless. The arguments, however, are the > same argument. > > See: if you are going to apply the argument to binary N-functions, > then you use the definition applicable to binary N-functions. If you > are going to apply it to subsets, you use the definition that applies > to subsets. Instead, you are trying to apply the definition for > subsets to the binary N-function, and then complain that it doesn't > make sense. It is exactly as if you were trying to translate a book by > only translating every other word instead of the entire sentence, and > then claimed that translation was impossible because the result didn't > make sense. > > > so attempt of translating each arguments into the other fails > > bidirectionally. > > Your *flawed* attempt failed, because it was wrongheaded. Purposely > so, I suspect, because I find it hard to believe that *anyone* could > be so clueless as you have presented yourself to be for so long. > > > 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. > > You think? Perhaps translating the entire thing instead of just > piecemeal might yield a translation that actually makes sense? Miracle > of miracles! > > > 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}. > > No, silly. > > Again: if A is *any* subset, then Chi_A(n) = 0 if n not in A, and 1 if > n is in A. > > So if A is the empty set, then Chi_A(n) =0 for all n. > > So the characteristic function of the empty set AS A SUBSET OF N is > > { <n,0> : n in N}. > > Characteristic functions of SUBSETS don't depend only on the set you > are looking at, they depend on the ambient set. They are defined on > the AMBIENT set, and are defined in terms of the subspace. In this > argument, you are looking at the characteristic functions of the > subsets of X, so they always have domain X. The "characteristic > function of the empty set" AS A SUBSET OF N is different from the > characteristic function of the empty set as a subset of any set Y with > Y=/=N. > > > 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. > > The "diagonal argument" IS the general argument. They are the same > argument, if you aren't purposely dishonest or obtuse. No there is no purposeful dishonesty as you suspect or anything like that, I will look to your responses above an try to understand them step by step and report back my doubts if there is any, If I see that you managed to prove your claim, then I will confess it, as I confessed that the diagonal argument do prove that the set N is strictly subnumerous to the set of binary maps without any well ordering needed, and also I confess that I had the wrong impression about this argument, as I confessed that your statement that I was confusing the illustration for the argument itself, as I confessed that exactly the same argument can be generalized to any set X. In the same line if I am convinced by your illustrations above, I will state it. There is no dishonesty here. > > -- > Arturo Magidin
From: Arturo Magidin on 7 Feb 2010 16:59 On Feb 7, 3:44 pm, zuhair <zaljo...(a)gmail.com> wrote: > > The "diagonal argument" IS the general argument. They are the same > > argument, if you aren't purposely dishonest or obtuse. > > No there is no purposeful dishonesty as you suspect or anything like > that, I will look to your responses above an try to understand them > step by step and report back my doubts if there is any, If I see that > you managed to prove your claim, To *your satisfaction*. The "claim" (in fact a trivial observation) has been established long before me and it is clear and patently obvious to plenty of people in this thread alone. The problem is that *you* don't get it, so kindly put the approrpiate qualifier there. It's not whether or not I can "prove [my] claim", it is whether or not I manage to hammer it through *your* thick skull. -- Arturo Magidin
From: zuhair on 7 Feb 2010 17:01
On Feb 7, 4:29 pm, Arturo Magidin <magi...(a)member.ams.org> wrote: > On Feb 7, 7:48 am, zuhair <zaljo...(a)gmail.com> wrote: > > > > > > > On Feb 4, 12:35 pm, Arturo Magidin <magi...(a)member.ams.org> wrote: > > > > 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 > > You are already well on your way to confusing yourself. A was the set > of even numbers. Now A is an arbitrary variable standing for an > arbitrary subset of N. Which is it? > > > > > 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. > > This is irrelevant to the argument. > > > so N and {Chi_A| A subset of N} are disjoint sets. > > Irrelevant. > > > Now lets apply the diagonal of the general argument to f > > > we'll have > > > For all f: D_f = N. > > No. When you apply the diagonal argument to characteristic function > (which are function from N to {0,1}, you are to get a characteristic > function. The characteristic function you get is > > D_f = { <n, 1- f(n)[n]> : n in N} The function whose value at n is 1 > if f(n)[n] is 0, and 0 if f(n)[n]=1. Remember? That's what the > argument for binary sequences was, and that is what {Chi_A|A subset of > N} is: it is the set of all binary sequences. > > > and as we know N is not a member of {Chi_A| A subset of N} > > You are confused. You aren't "translating", you are trying to feed > English words to a Russian dictionary. You are supposed to TRANSLATE > the argument, not just the inputs. > > > > > 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. > > It means you (i) didn't understand and (ii) don't know what you are > doing and (iii) are still clueless. The arguments, however, are the > same argument. > > See: if you are going to apply the argument to binary N-functions, > then you use the definition applicable to binary N-functions. If you > are going to apply it to subsets, you use the definition that applies > to subsets. Instead, you are trying to apply the definition for > subsets to the binary N-function, and then complain that it doesn't > make sense. It is exactly as if you were trying to translate a book by > only translating every other word instead of the entire sentence, and > then claimed that translation was impossible because the result didn't > make sense. > > > so attempt of translating each arguments into the other fails > > bidirectionally. > > Your *flawed* attempt failed, because it was wrongheaded. Purposely > so, I suspect, because I find it hard to believe that *anyone* could > be so clueless as you have presented yourself to be for so long. > > > 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. > > You think? Perhaps translating the entire thing instead of just > piecemeal might yield a translation that actually makes sense? Miracle > of miracles! Well sometimes, yes I do! > > > 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}. > > No, silly. Thanks for the complement. > > Again: if A is *any* subset, then Chi_A(n) = 0 if n not in A, and 1 if > n is in A. > > So if A is the empty set, then Chi_A(n) =0 for all n. > > So the characteristic function of the empty set AS A SUBSET OF N is > > { <n,0> : n in N}. yea, I missed that, that was my error, I got your point now. > > Characteristic functions of SUBSETS don't depend only on the set you > are looking at, they depend on the ambient set. They are defined on > the AMBIENT set, and are defined in terms of the subspace. In this > argument, you are looking at the characteristic functions of the > subsets of X, so they always have domain X. The "characteristic > function of the empty set" AS A SUBSET OF N is different from the > characteristic function of the empty set as a subset of any set Y with > Y=/=N. Ah, yes, true, the arguments really translates to each other, you were right as I suspected. > > > 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. > > The "diagonal argument" IS the general argument. They are the same > argument, if you aren't purposely dishonest or obtuse. You were right, I was wrong. > > -- > Arturo Magidin |