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: 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: 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.
From: Bill Taylor on 3 Feb 2010 21:29 Well, one good thing seems to have come out of these latest two threads by Zuhair, anyway. For some time I had been wondering if his Cardinality threads were replete with subtle technical ideas, or stunning flashes of metamathematical insight. They were just a tad too technical and just a tad too far from my own interests for me to try to adjudge them myself, nor could I tell much from the followups. So, was he a figure of technical excellence and penetrative insight, or was he just another crackpot? It seems now that it is the latter. -- Bitter Bill P.S. Yes, I know I write a lot of crackpot posts too, don't bother to remind me. It is beside the point.
From: Ross A. Finlayson on 3 Feb 2010 22:10
On Feb 2, 7:34 pm, Marshall <marshall.spi...(a)gmail.com> wrote: > On Feb 2, 6:58 pm, zuhair <zaljo...(a)gmail.com> wrote: > > > > > 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? > > Of course. You don't think it should be designed to show what > it wants to show? If it shows something other than what it > was designed for, it was not designed very well! > > > > > 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} > > Can you explain this a bit better? What is the sequence? > What does <> mean? I would expect a "sequence" to be > a mapping from the naturals to some target set. > > > so X is just an example of a infinite binary sequence. > > I don't see how. > > > 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 the naturals, so it doesn't seem to have anything to do > with Cantor's proof. On the other hand, what would you say the > cardinality of that set is? Is it the same as the naturals? If so, > then why don't you just use the naturals? If it's otherwise, then > it doesn't relate to Cantor's diagonal proof. > > > > > 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. > > What if you just put the last line first? Also note that anything > with a last element is not an infinite sequence. > > > 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! > > What can be shown is that for any purported > sequence S of all possible infinite sequences, it is possible to > construct an infinite sequence that is not in the sequence S. > It doesn't matter how S is constructed; one can always construct > from S an infinite sequence that is not in S. > > Marshall Yes it is well known that the binary case requires refinement and there is one anti-diagonal, of the matrix expansion of the elements. In square matrix expansions of course there are always the same number of rows and columns. The unit interval of reals is a special case in terms of its cardinality and measure. In cardinality it's equal to the powerset of integers. In measure, it's the prototype unit of measure. So, two of them are two, in units of measure. But, that is not about the real numbers or you would admit nonstandard facts about the real numbers, that for example some have shared expansions, like .999 = 1. Here, the binary coded powerset of the integers is not the same thing as the real numbers' representations standardly. Hmm, with the equivalency function, EF(w) would equal one. Here w is Omega, or omega, the ordinal, that is the regular limit ordinal greater than any finite ordinal. Putting it in front would make the antidiagonal .0111.... Repeating, it would go to zero, in halves, the antidiagonal. The antidiagonal would go to zero while the the list again went to zero, from one. This is a simple translation of the equivalency function. The equivalency function is standardly modeled by finite approximations. (Not a real function.) It's a real function, nonstandardly real. EF(0) is zero. EF(1) is just the least infinitesimal difference, not even a distance, but all the distances add up to one, and the differences. It is just approximately dx the differential used in calculus with summations of them. It fits in the diagonal argument so the results don't apply, but, it uses non-Vitali numbers. Vitali's systems don't have those, establishing non- measurable sets. Then, it's really simple, the function EF(oo) = 1. Here, taking the list elements from the back and putting them in the front, it steps from zero to one then drops back to zero, while the change is monotone, the change in the antidiagonal steps halves while the change in EF is monotone, ranging over the same variable. EF(n+1) = EF( EF^(-1) (1 - EF( n) ) antidiagonal(EF(n+1)) = antidiagonal(EF(n)) / 2 As you can see, in cases where n has a constant rate of change, these only happen with large numbers. Here this is where the list starts at the end or the extent and processes. All perfectly integrable, via simple reflections of symmetries. Regards, Ross Finlayson |