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: Don Stockbauer on 5 Feb 2010 07:37 On Feb 5, 6:24 am, zuhair <zaljo...(a)gmail.com> wrote: > On Feb 5, 12:44 am, "M. M i c h a e l M u s a t o v" > > > > <marty.musa...(a)gmail.com> wrote: > > Results 1 - 10 for CANTOR'S DIAGONAL. (0.28 seconds) > > > Cantor's diagonal argument - Wikipedia, the free encyclopediaCantor's > > diagonal argument, also called the diagonalisation argument, the > > diagonal slash argument or the diagonal method, was published in 1891 > > by Georg ... > > en.wikipedia.org/wiki/Cantor's_diagonal_argument > > > Google Directory - Science > Math > Logic and Foundations > Set > > TheoryArticle in the Platonic Realms, describing Cantor's diagonal > > argument that showed that 'infinite integers' can be ordered. ...www.google.com/Top/Science/Math/Logic_and.../Set_Theory/ > > > Cantor's Diagonal ProofSimplicio: I'm trying to understand the > > significance of Cantor's diagonal proof. I find it especially > > confusing that the rational numbers are considered to ...www.mathpages.com/HOME/kmath371.htm > > > PlanetMath: Cantor's diagonal argumentOne of the starting points in > > Cantor's development of set theory was his discovery that there are > > different degrees of infinity. ... > > planetmath.org/encyclopedia/CantorsDiagonalArgument.html > > > Cantor Diagonal Method -- from Wolfram MathWorldThe Cantor diagonal > > method, also called the Cantor diagonal argument or Cantor's diagonal > > slash, is a clever technique used by Georg Cantor to show that the ... > > mathworld.wolfram.com/CantorDiagonalMethod.html > > > Diagonal argument - Wikipedia, the free encyclopediaA variety of > > diagonal arguments are used in mathematics. "Cantor's diagonal > > argument" was the earliest. Cantor's diagonal argument · Cantor's > > theorem ... > > en.wikipedia.org/wiki/Diagonal_argument > > > Kids.Net.Au - Encyclopedia > Cantor's diagonal argumentA generalized > > form of the diagonal argument was used by Cantor to show that for > > every set S the power set of S, i.e., the set of all subsets of S > > (here ... > > encyclopedia.kids.net.au/page/ca/Cantor's_diagonal_argument > > > Simple Argument Against Cantor's Diagonal ProcedureI was also inspired > > by the page at <http://users.javanet.com/~cloclo/infinity.html>, > > entitled "Problems with Cantor's Diagonal Method and Infinity in ... > > homepage.mac.com/ardeshir/ArgumentAgainstCantor.html > > > Cantor's diagonal argumentContrary to what many mathematicians > > believe, the diagonal argument was not Cantor's first proof of the > > uncountability of the real numbers, ...www.fact-index.com/c/ca/cantor_s_diagonal_argument.html > > > Cantor's diagonal method2 posts - 1 author > > I just wanted to share with you a pretty formulation of Cantor's > > diagonal argument that there is no bijection between a set X and its > > power set P(X). ...www.physicsforums.com/showthread.php?t=82110 > > > 1 2 3 4 5 6 7 8 9 10 Next > > > On Feb 4, 9:43 pm, Virgil <Vir...(a)home.esc> wrote: > > > > In article > > > <f3e811e3-c4b0-4309-97b2-9d4771ed6...(a)u41g2000yqe.googlegroups.com>, > > > > zuhair <zaljo...(a)gmail.com> wrote: > > > > On Feb 4, 7:33 pm, MoeBlee <jazzm...(a)hotmail.com> wrote: > > > > > On Feb 4, 5:59 pm, zuhair <zaljo...(a)gmail.com> wrote: > > > > > > > ANY is EVERY. > > > > > > In a certain sense in logic, yes. So? > > > > > I just wanted to clarify to Virgil that in logic ANY is EVERY, > > > > apparently Virgil > > > > thought they are different, so he iterated my argument replacing ANY > > > > (as he > > > > emphasized it by writing in CAPITAL letters) instead of EVERY, so > > > > my reply to him was a clarification that ANY is EVERY, that's all. > > > > > > Do you have any remaining question or doubt that in Z set theory > > > > > proves there is no bijection between w and {f | f: w -> {0 1}}? > > > > > > MoeBlee > > > > > No. > > > > > Zuhair > > > > You missed my point. When there is a proof, as there is, covering ANY > > > instance, it automatically covers EVERY instance too. > > > > Thus one does not need a separate proof for both.- Hide quoted text - > > > > - Show quoted text - > > Most of the links are not working. > > Zuhair Take a bullwhip to them.
From: zuhair on 7 Feb 2010 08:48 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. 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 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: Jesse F. Hughes on 7 Feb 2010 09:09 zuhair <zaljohar(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. 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. -- Jesse F. Hughes Playin' dismal hollers for abysmal dollars, Those were the days, best I can recall. -- Austin Lounge Lizards, "Rocky Byways"
From: zuhair on 7 Feb 2010 10:04 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. > > 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 agree with you, I am not saying that these theories in which there is no empty set, or even a theory in which there is no set of cardinality less than n, I am not saying that these theories are serious theories at all, neither I am saying that they should be the subject of serious research, I am only making an argument here against generalizing the similarity of these two arguments over all possible set theories in FOL. I myself don't take that in a very serious manner. However If and I say if I am correct then even in ZF, it seems that the Diagonal argument is a sub-argument of the general argument, and it seems that they are not exactly the same argument as one of the discussers in this thread was stating explicitly, however seeing that this other discusser is a professional mathematician then there is the greater chance that I am actually wrong about this particular issue, but up till now that's how matters look to me. Zuhair > > -- > Jesse F. Hughes > Playin' dismal hollers for abysmal dollars, > Those were the days, best I can recall. > -- Austin Lounge Lizards, "Rocky Byways"
From: Frederick Williams on 7 Feb 2010 10:19
"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. -- 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) |