Cantor's Diagonal?
in [Math]
|
From: Arturo Magidin on 3 Feb 2010 17:09 On Feb 3, 12:14 pm, Arturo Magidin <magi...(a)member.ams.org> wrote: > 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. 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. -- Arturo Magidin
From: Ask me about System Design on 3 Feb 2010 18:05 On Feb 2, 6:59 pm, zuhair <zaljo...(a)gmail.com> wrote: > Hi all, > > I have some difficulty digesting the diagonal argument of Cantor's. > > The argument is that the set of all infinite binary sequences cannot > have a bijection to the set of all natural numbers, thereby proving > that the former set is uncountable? > > However the argument looks to me to be so designed as to reach to that > goal? > > One can look at matters from an alternative way such as to elude > Cantor's conclusion! > > Examine the following: > > Lets take the infinite binary sequences of the letters O and H > > so for example we have the sequence > > X = OHOHOH........ > > in which O is coupled to the even naturals and H coupled to the odd > naturals. > > so the sequence above is > > X= {<O,i>,<H,j>| i is an even natural, j is an odd natural} > > so X is just an example of a infinite binary sequence. > > However lets try to see weather we can have a bijection between > the set of all infinite binary sequences and the set w+1 > which is {0,1,2,....,w} > > so we'll have the following table: > > 0 , 1 , 2 , 3 , ... > 0 H , O , O , H ,.... > 1 O , H , H , O ,.... > 2 H , H , H , H ,.... > 3 O ,O , H , H ,.... > . > . > . > . > > w O, O , O, O ,... > > Now according to the above arrangement one CANNOT define a diagonal ! > since the w_th sequence do not have a w_th entry > to put H or O in it. > > So if we can have a diagonal then this would be of the set of all > infinite binary sequences except the w_th one, i.e. of the following > > 0 , 1 , 2 , 3 , ... > 0 H , O , O , H ,.... > 1 O , H , H , O ,.... > 2 H , H , H , H ,.... > 3 O ,O , H , H ,.... > . > . > . > . > > Suppose that the diagonal of those was D=HHHHH.... > i.e. D={<H,n>| n is a natural number} > > Now the counter-diagonal would be D' = OOOO... > i.e. D' = {<O,n>| n is a natural number} > > However there is nothing to prevent the w_th infinite binary sequence > from being D' ? > > So neither we can have a diagonal of all the infinite binary > sequences, nor the diagonal of a subset of these sequences would yield > a successful diagonal argument such as to conclude that the set of all > infinite binary sequences is uncountable? > > Thereby Cantor's argument fail in this situation! > > What I am trying to say is that this Diagonal argument seems to be > purposefully designed to reach the goal of concluding that > the set of all infinite binary sequences is uncountable, by merely > selecting a particular bijection with the set {0,1,2,3,....} > in a particular arrangement, such as to make a diagonal possible, such > as to conclude the uncountability of these infinite binary sequences, > While if we make simple re-arrangement like the one posed above then > this argument vanish! > > There must be something wrong with the way I had put things here, but > I would rather want to read the full proof of this diagonal argument > in Zermelo's set theory. > > Zuhair I'm going to break my habit of staying out of posts on Cantor's Diagonal argument, because I believe I can address the concerns being raised. I would like a reply posted to know if my attempt succeeded. The modification to the diagonal argument of Cantor is akin to the following: let's just remove a number from the list and not use it at all. Then the modified process may fail in producing a number different from the number that was removed. But the modified process is no longer Cantor's argument. So Cantor's argument does not fail. It seems what is wanted is an argument where the well- ordering of N is not needed, or at least not as apparent. I like the following: Suppose X is a set that is equipollent with the natural numbers. P(X), the power set of X, is equipollent with the set of real numbers. But every map from X to P(X) fails to be surjective. Why? Because any map from X to a proper subset of P(X), (P(X) - { emptyset } ), fails to be surjective. Why? Take any map f from X to ( P(X) - {emptyset} ). Consider the set { x : x \not \in f(x) }, and call this set C. C is in P(X). Now take any x, and call f(x) D; either x in D, so x not in C, so C <> D, so f(x) <> C , OR x not in D, x is in C, so C <> D, so C <> f(x) . So for any x, f(x) is not C. So for any map f from X into (P(X) - {emptyset}), f is not surjective. This is an abstract form of diagonalization that can be adapted to many situations, including the situation in a previous post. A flaw in that post is the idea that changing A into Z and then showing that Z is wrong means there is also something wrong with A. This argument above that I like should show that one cannot find a map that establishes that N and R have the same cardinality. Let me know how the experiment worked. Gerhard "Ask Me About System Design" Paseman, 2010.02.03
From: Bill Dubuque on 3 Feb 2010 18:06 Arturo Magidin <magidin(a)member.ams.org> wrote: > On Feb 3, 12:14 pm, Arturo Magidin <magi...(a)member.ams.org> wrote: > >> 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. > > 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. In [1] I gave a simple vivid account of Cantor diagonalization. It also contains some interesting references on related such diagonalizations. Namely that du Bois-Reymond preceded Cantor with his diangonalization on growth rates (orders of infinity) and related work on diagonalizing out of primitive recursive functions with the Ackermann function. --Bill Dubuque [1] http://google.com/groups?selm=y8zogkamq8u.fsf%40berne.ai.mit.edu
From: master1729 on 3 Feb 2010 08:27 > Hi all, > > I have some difficulty digesting the diagonal > argument of Cantor's. > > The argument is that the set of all infinite binary > sequences cannot > have a bijection to the set of all natural numbers, > thereby proving > that the former set is uncountable? > > However the argument looks to me to be so designed as > to reach to that > goal? > > One can look at matters from an alternative way such > as to elude > Cantor's conclusion! > > Examine the following: > > Lets take the infinite binary sequences of the > letters O and H > > so for example we have the sequence > > X = OHOHOH........ > > in which O is coupled to the even naturals and H > coupled to the odd > naturals. > > so the sequence above is > > X= {<O,i>,<H,j>| i is an even natural, j is an odd > natural} > > so X is just an example of a infinite binary > sequence. > > However lets try to see weather we can have a > bijection between > the set of all infinite binary sequences and the set > w+1 > which is {0,1,2,....,w} > > so we'll have the following table: > > 0 , 1 , 2 , 3 , ... > 0 H , O , O , H ,.... > 1 O , H , H , O ,.... > 2 H , H , H , H ,.... > 3 O ,O , H , H ,.... > . > . > . > . > > w O, O , O, O ,... > > > Now according to the above arrangement one CANNOT > define a diagonal ! > since the w_th sequence do not have a w_th entry > to put H or O in it. > > So if we can have a diagonal then this would be of > the set of all > infinite binary sequences except the w_th one, i.e. > of the following > > 0 , 1 , 2 , 3 , ... > 0 H , O , O , H ,.... > 1 O , H , H , O ,.... > 2 H , H , H , H ,.... > 3 O ,O , H , H ,.... > . > . > . > . > > Suppose that the diagonal of those was D=HHHHH.... > i.e. D={<H,n>| n is a natural number} > > Now the counter-diagonal would be D' = OOOO... > i.e. D' = {<O,n>| n is a natural number} > > However there is nothing to prevent the w_th infinite > binary sequence > from being D' ? > > So neither we can have a diagonal of all the infinite > binary > sequences, nor the diagonal of a subset of these > sequences would yield > a successful diagonal argument such as to conclude > that the set of all > infinite binary sequences is uncountable? > > Thereby Cantor's argument fail in this situation! > > What I am trying to say is that this Diagonal > argument seems to be > purposefully designed to reach the goal of concluding > that > the set of all infinite binary sequences is > uncountable, by merely > selecting a particular bijection with the set > {0,1,2,3,....} > in a particular arrangement, such as to make a > diagonal possible, such > as to conclude the uncountability of these infinite > binary sequences, > While if we make simple re-arrangement like the one > posed above then > this argument vanish! > > There must be something wrong with the way I had put > things here, but > I would rather want to read the full proof of this > diagonal argument > in Zermelo's set theory. > > Zuhair > > > > > > > > > > > its sad that you dont understand...
From: Mike Terry on 3 Feb 2010 21:26
"zuhair" <zaljohar(a)gmail.com> wrote in message news:3faa561b-3c72-4efa-ab73-936d9d68ceae(a)m31g2000yqb.googlegroups.com... > On Feb 2, 11:25 pm, "Peter Webb" > <webbfam...(a)DIESPAMDIEoptusnet.com.au> wrote: > > "zuhair" <zaljo...(a)gmail.com> wrote in message > > > > news:38df2f48-b006-4005-ba49-e21d47a154b3(a)b2g2000yqi.googlegroups.com... > > > > > > > > > > > > > Hi all, > > > > > I have some difficulty digesting the diagonal argument of Cantor's. > > > > > The argument is that the set of all infinite binary sequences cannot > > > have a bijection to the set of all natural numbers, thereby proving > > > that the former set is uncountable? > > > > > However the argument looks to me to be so designed as to reach to that > > > goal? > > > > > One can look at matters from an alternative way such as to elude > > > Cantor's conclusion! > > > > > Examine the following: > > > > > Lets take the infinite binary sequences of the letters O and H > > > > > so for example we have the sequence > > > > > X = OHOHOH........ > > > > > in which O is coupled to the even naturals and H coupled to the odd > > > naturals. > > > > > so the sequence above is > > > > > X= {<O,i>,<H,j>| i is an even natural, j is an odd natural} > > > > > so X is just an example of a infinite binary sequence. > > > > > However lets try to see weather we can have a bijection between > > > the set of all infinite binary sequences and the set w+1 > > > which is {0,1,2,....,w} > > > > That's not a bijection between R and N. The set N doesn't include w. > > So you are not attempting to disprove Cantor's claim. > > 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. > > 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. > > > > It just so happens that a very minor change to Cantor allows a proof that R > > cannot be bijected with w+1. > > > > Let the Real that the number n maps to be defined as R(n). > > > > Consider the sequence of Reals > > > > R(w), R(1), R(2), R(3) ... > > > > Cantors argument applied to this list shows R cannot be bijected with w+1, > > or indeed any countable ordinal. > > Yes of course, BUT the Diagonal argument fails with other > arrangements, that's my point. For this Diagonal argument to be > general enough I tend to think that we must find a diagonal for all > arrangements of all countable sets, which is not the case, I think this is where you have your problem. Recall that the actual definition of uncountable is: [A] Set A is uncountable if there doesn't exist a surjection f: N-->A From what you've just written, it seems you believe the definition should be something like: [B] Set A is uncountable if there doesn't exist a surjection f: X-->A for ANY countable set X. This last definition is simply wrong. (It doesn't even make sense, as the definition is circular!, but no matter - in any case definition [A] is what Cantor is using) So to show that A is uncountable, Cantor's proof only needs to show that there is no surjection f mapping N to A. The structure of the proof is: 1) let f be ANY function mapping N to A 2) blah blah, therefore it follows f is not a surjection 3) i.e. there does not exist a surjection f: N-->A. (you understand a surjection is a specific type of *function*, right?) 4) i.e. A is uncountable, according to the definition [A] above Of course this does not prove (or claim to prove) that A is uncountable according to definition [B] above, or according to any other definition of uncountable... Regards, Mike. |