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: FF on 7 Feb 2010 12:11 On Sun, 07 Feb 2010 15:58:57 +0000, Frederick Williams wrote: >> If I was supposed to get that reference, I missed it. >> > Well, I *think* that Frege didn't believe in the empty set. > Nope. Actually, he was one of the first to work with it. FF
From: Ilmari Karonen on 7 Feb 2010 13:06 ["Followup-To:" header set to sci.math.] On 2010-02-07, zuhair <zaljohar(a)gmail.com> wrote: > On Feb 7, 9:09 am, "Jesse F. Hughes" <je...(a)phiwumbda.org> wrote: >> >> 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. Um... wait. Fix some (non-empty, non-all-inclusive) set B, and let P(y) <=> y /e B (where /e means "is not a member of"). Then, in your modified axiom of separation for this P, what is x when A = B? -- Ilmari Karonen To reply by e-mail, please replace ".invalid" with ".net" in address.
From: FredJeffries on 7 Feb 2010 13:13 On Feb 7, 9:11 am, FF <f...(a)simple-line.de> wrote: > On Sun, 07 Feb 2010 15:58:57 +0000, Frederick Williams wrote: > >> If I was supposed to get that reference, I missed it. > > > Well, I *think* that Frege didn't believe in the empty set. > > Nope. Actually, he was one of the first to work with it. > > FF Didn't R L Moore espouse the non-existence of the empty set?
From: Brian on 7 Feb 2010 13:19 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 Something that might interest you.. There is a proof that involves less of what you may perceive to be "hand waving" of the statement "the set of reals is uncountable." The fact this proof relies on is that there is never a function from a set -onto- its power set. This fact is applied to the set of natural numbers (which is known to be equipollent to the set of rational numbers). The power set of N is equipollent to the set of reals. Thus, the set of reals is not countable while the set of rationals is. The fact that there is never a function from a set onto its power set that I know of involves a little sleight of hand, but certainly not hand waving.
From: Arturo Magidin on 7 Feb 2010 14:15
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: > > > 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. Mike Terry has done so. > > 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. You are being either disingenious, or willfully obtuse. As to your continued insistence that the argument "may fail in other set theories", you are being purposely dishonest. Naturally, a proof that works in theory T need not work in theory T'. As I pointed out, the diagonal argument can be "tweaked" (aka modified slightly) to work in set theories that do not have empty sets if you do two modifications: one is to modify the statement so that it only applies to sets that are not singletons; the second modification is that the argument needs to be 'tweaked' (suitably modified) so that the constructed function/set is not the zero function/emtpy. This is a process similar to the one used to avoid problems of dual representations when presenting the argument as proving no bijection exists between the natural numbers and the real numbers in the interval [0,1). -- Arturo Magidin |