uncountable infinity without Cantor's diagonal proof
in [Logic]
|
Prev: Give me ONE digit position of any real that isn't computable up to that digit position!
Next: Give me ONE digit position of any real that isn't computable up to that digit position!
From: Lee Davidson on 5 Jun 2010 19:08 This will be old hat for many of you. I'm working in ZFC. The natural numbers 0,1,2... can be put into one-one correspondence with all ordered pairs of natural numbers. The reals can be put into one-one correspondence with all subsets of natural numbers. Now let N be the set of the natural numbers and consider N x N, the set of all ordered pairs. This exists, using the Axiom of Replacement. Next, take P(NxN) = the set of all sets of ordered pairs of natural numbers. This is the set of all relations on the natural numbers. Let S = the subset of P(NxN) consisting of all relations that are well- orderings. ZF proves that every well-ordering R corresponds to some ordinal a(R) such that <a,<> is isomorphic to R. The Axiom of Replacement implies that a set T = { a(R): R is an element of S } exists. Suppose a < c < b and a and b are in that set. Then a maps 1:1 into c which maps 1:1 into b which maps 1:1 onto a. So a, c, and b are all related by 1:1 correspondences, so c is the ordinal of a well-ordering of N, so c is in S. Now let a = lub of T = { a(R): R is a well-ordering in S }. a cannot be put into 1:1 correspondence with any ordinal in T, for then a would be the ordinal of a well-ordering of N. So we have a function mapping a subset of P(NxN) into a whose range cannot be put in 1:1 correspondence with N. Since P(NxN) has the same cardinality as the reals, this shows the reals are uncountable. Cantor's diagonal argument appears nowhere here, and this in fact proves just as much as Cantor's diagonal argument. What I haven't considered yet is how to prove, in the same spirit, that the infinite sum of cardinals a_i is less than the infinite product of cardinals b_i if for all i a_i < b_i, but I suspect that this is possible.
From: Virgil on 5 Jun 2010 23:29 Note that Cantor proved an uncountable infinity of real numbers with his first proof of it, well before he even thought of the diagonal proof. See http://en.wikipedia.org/wiki/Cantor's_first_uncountability_proof Or almost any of about 3,700,000 other Google hits for "Cantor's First Proof"
From: George Greene on 6 Jun 2010 13:06 On Jun 5, 7:08 pm, Lee Davidson <l...(a)meta5.com> wrote: > This will be old hat for many of you. I'm working in ZFC. > > The natural numbers 0,1,2... can be put into one-one correspondence > with all ordered pairs of natural numbers. > > The reals can be put into one-one correspondence with all subsets of > natural numbers. This is assuming too much already. You are not even DEFINING "the reals". The fact that "the reals" can be "put into 1-1 corespondence with all subsets of the natural numbers" IS MISSING THE POINT: the reason WHY this is true IS BECAUSE, as far as ZFC is concerned "the reals" MEANS p(N): "a real" IS a subset of N. More to the point, your insistence on invoking N and infinity here IS STUPID. Cantor's Theorem holds FOR ALL SETS!!!!!!!!!!!!!!!!!!!! It DOES NOT MATTER whether the set is or isn't infinite! The proof looks THE EXACT SAME! Everybody who tries to invoke infinity in dealing with this question is flaunting some fundamental gaps, to put it charitably. > Now let N be the set of the natural numbers and consider N x N, the > set of all ordered pairs. This exists, using the Axiom of Replacement. Better: let M be any set, and consider MxM. The fact that ordered pairs exist at all is also due to Replacement. > Next, take P(NxN) = the set of all sets of ordered pairs of natural > numbers. > > This is the set of all relations on the natural numbers. > > Let S = the subset of P(NxN) consisting of all relations that are well- > orderings. So far, you have not used the fact that N is infinite ANYwhere in this chain yet. > ZF proves that every well-ordering R corresponds to some ordinal a(R) > such that <a,<> is isomorphic to R. Well, what do you want for THAT, the handwave of the century award??? Seriously, if you are not going to say why ordinals matter or why anyone should care, or how this proof works out; in short, if you are not going to give some insight into what is going on here, then what is the point? If you wanted to use ordinals RATHER THAN CARDINALS (i.e., rather than defining cardinality via equivelance-class via bijection and talking about the powerset's higher cardinality), then you could have just said, "Obviously, the collection of all countable ordinals is an UNcountable ordinal" AND BEEN DONE WITH IT.
From: Daryl McCullough on 6 Jun 2010 14:18 George Greene says... > >On Jun 5, 7:08=A0pm, Lee Davidson <l...(a)meta5.com> wrote: >> The reals can be put into one-one correspondence with all subsets of >> natural numbers. > >This is assuming too much already. You are not even DEFINING "the >reals". The fact that "the reals" can be "put into 1-1 corespondence >with all subsets of the natural numbers" IS MISSING THE POINT: >the reason WHY this is true IS BECAUSE, as far as ZFC is concerned >"the reals" MEANS p(N): "a real" IS a subset of N. I would say that it's the other way around: BECAUSE there is a 1-1 correspondence between the reals and P(N), set theorists tend to identify the two. The reals are defined as the "completion" of the rationals (by adding limits of Cauchy sequences). >More to the point, your insistence on invoking N and infinity here >IS STUPID. Cantor's Theorem holds FOR ALL SETS!!!!!!!!!!!!!!!!!!!! >It DOES NOT MATTER whether the set is or isn't infinite! >The proof looks THE EXACT SAME! He's sketching an alternative proof that *doesn't* use Cantor's diagonalization procedure. Basically, to make a long story short, he's letting omega_1 be defined as the supremum of all well-orderings of the naturals. Then you can easily prove that omega_1 is uncountable. -- Daryl McCullough Ithaca, NY
From: Lee Davidson on 6 Jun 2010 15:46
On Jun 6, 10:06 am, George Greene <gree...(a)email.unc.edu> wrote: > On Jun 5, 7:08 pm, Lee Davidson <l...(a)meta5.com> wrote: > > > This will be old hat for many of you. I'm working in ZFC. > > > The natural numbers 0,1,2... can be put into one-one correspondence > > with all ordered pairs of natural numbers. > > > The reals can be put into one-one correspondence with all subsets of > > natural numbers. > > This is assuming too much already. You are not even DEFINING "the > reals". > The fact that "the reals" can be "put into 1-1 corespondence with all > subsets of > the natural numbers" IS MISSING THE POINT: the reason WHY this is > true > IS BECAUSE, as far as ZFC is concerned "the reals" MEANS p(N): > "a real" IS a subset of N. > > More to the point, your insistence on invoking N and infinity here > IS STUPID. Cantor's Theorem holds FOR ALL SETS!!!!!!!!!!!!!!!!!!!! > It DOES NOT MATTER whether the set is or isn't infinite! > The proof looks THE EXACT SAME! I'm perfectly aware of that. I focused on the reals because that's what everyone discusses. > > Everybody who tries to invoke infinity in dealing with this question > is flaunting some fundamental gaps, to put it charitably. > > > Now let N be the set of the natural numbers and consider N x N, the > > set of all ordered pairs. This exists, using the Axiom of Replacement. > > Better: let M be any set, and consider MxM. The fact that ordered > pairs exist at all > is also due to Replacement. Wrong. All you need for ordered pairs is the pair set axiom. > > > Next, take P(NxN) = the set of all sets of ordered pairs of natural > > numbers. > > > This is the set of all relations on the natural numbers. > > > Let S = the subset of P(NxN) consisting of all relations that are well- > > orderings. > > So far, you have not used the fact that N is infinite ANYwhere in this > chain yet. I'm assuming that everyone knows N is infinite. I'm working on the basis of previous theorems. > > > ZF proves that every well-ordering R corresponds to some ordinal a(R) > > such that <a,<> is isomorphic to R. > > Well, what do you want for THAT, the handwave of the century award??? Once again, previous theorems. You can prove that about well orderings using only extensionality, pair set, unions, and subsets. > > Seriously, if you are not going to say why ordinals matter or why > anyone should care, > or how this proof works out; in short, if you are not going to give > some insight into what > is going on here, then what is the point? > > If you wanted to use ordinals RATHER THAN CARDINALS (i.e., rather than > defining cardinality via equivelance-class via bijection and talking > about > the powerset's higher cardinality), then you could have just said, > "Obviously, the collection of all countable ordinals is an UNcountable > ordinal" > AND BEEN DONE WITH IT. Yes, I could have shortened the proof but in this case I was proving what I wanted more from scratch. |