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 6 Jun 2010 15:48 On Jun 6, 11:18 am, stevendaryl3...(a)yahoo.com (Daryl McCullough) wrote: > 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 Thank you Daryl. What got me started on this was realizing that in ZF, without the Axiom of Choice, and without invoking Cantor's diagonalization procedure, you would get uncountable ordinals. I probably knew that before, but hadn't thought about it until recently and I've noticed some discussion here about diagonalization as if that's the key to uncountability.
From: Lee Davidson on 6 Jun 2010 18:16 On Jun 6, 11:18 am, stevendaryl3...(a)yahoo.com (Daryl McCullough) wrote: > George Greene says... > > > 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 Oh, Daryl. Here's an interesting problem. My proof depends upon the well-ordering of N. Suppose ZF without AC and that x is some arbitrary non-well-orderable set. Can you still prove P(x) is bigger than x without the Cantor diagonalization procedure?
From: Rotwang on 6 Jun 2010 20:21 Lee Davidson wrote: > On Jun 6, 11:18 am, stevendaryl3...(a)yahoo.com (Daryl McCullough) > wrote: >> George Greene says... >> >> >> 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 > > Oh, Daryl. Here's an interesting problem. My proof depends upon the > well-ordering of N. Suppose ZF without AC and that x is some arbitrary > non-well-orderable set. Can you still prove P(x) is bigger than x > without the Cantor diagonalization procedure? Yes; let f: x -> P(x) be any function, and consider the set S in P(x) defined by S = {y in x | y is not in f(y)} Then one can show by contradiction that S is not in the image of f so f is not surjective. Though sorry if I've completely missed the point of your question, but the Cantor diagonalisation procedure does not rely on x being well ordered; one doesn't need a well-order to diagonalise a function g: x -> 2^x (and if g is related to f by the usual correspondence between P(x) and 2^x then the resulting element of 2^x corresponds to the set S given above, so I suppose you could argue that the proof above is really the diagonal argument in disguise).
From: Lee Davidson on 6 Jun 2010 21:16 On Jun 6, 5:21 pm, Rotwang <sg...(a)hotmail.co.uk> wrote: > Lee Davidson wrote: > > On Jun 6, 11:18 am, stevendaryl3...(a)yahoo.com (Daryl McCullough) > > wrote: > >> George Greene says... > > >> 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 > > > Oh, Daryl. Here's an interesting problem. My proof depends upon the > > well-ordering of N. Suppose ZF without AC and that x is some arbitrary > > non-well-orderable set. Can you still prove P(x) is bigger than x > > without the Cantor diagonalization procedure? > > Yes; let f: x -> P(x) be any function, and consider the set S in P(x) > defined by > > S = {y in x | y is not in f(y)} > > Then one can show by contradiction that S is not in the image of f so f > is not surjective. Though sorry if I've completely missed the point of > your question, but the Cantor diagonalisation procedure does not rely on > x being well ordered; one doesn't need a well-order to diagonalise a > function g: x -> 2^x (and if g is related to f by the usual > correspondence between P(x) and 2^x then the resulting element of 2^x > corresponds to the set S given above, so I suppose you could argue that > the proof above is really the diagonal argument in disguise). Yes, any argument using x not in x or x not in f(x) is a diagonal argument. The Cantor argument certainly doesn't rely on x being well- ordered. All I was wondering was if you can avoid diagonalization for non-well-ordered x by analogy with that I did.
From: Rotwang on 6 Jun 2010 21:48
Lee Davidson wrote: > On Jun 6, 5:21 pm, Rotwang <sg...(a)hotmail.co.uk> wrote: >> >> [...] > > Yes, any argument using x not in x or x not in f(x) is a diagonal > argument. The Cantor argument certainly doesn't rely on x being well- > ordered. All I was wondering was if you can avoid diagonalization for > non-well-ordered x by analogy with that I did. Right, I hadn't seen your earlier post when I wrote my reply. Sorry I wasn't much help. |