Register to reply

Why can't the well ordering of the reals be proven with Dedikind cuts without AC?

by SW VandeCarr
Tags: cuts, dedikind, ordering, proven, reals
Share this thread:
rasmhop
#19
Apr6-10, 11:51 AM
P: 424
See the well-ordering theorem on Wikipedia. Basically you form the set of all well-ordered subsets of the real numbers, then you invoke Zorn's lemma to conclude that there is a maximal such well-ordered subset, and you then note that it must actually be a well-ordering of the real numbers themselves.
vici10
#20
Apr6-10, 02:34 PM
P: 41
Quote Quote by CRGreathouse View Post
Would you expand on this? I don't see why it would be better to say it's some (the unique!) [tex]\aleph_\kappa[/tex] with [tex]\aleph_\kappa=\beth_1[/tex] rather than just biting the bullet and saying it's [tex]\beth_1[/tex].
You can think about it as about [tex]\beth_1[/tex], since [tex]\beth_1=2^{\aleph_0}[/tex] by definition. I just want SW VandeCarr get away from natural order of R. Anyway bethas are defined from alphas because GCH is independent. Another way to think of well-ordered reals as ordinals of cardinality [tex] 2^{\aleph_0} [/tex]

Anyway using AC one can proves that every set can be well-ordered and therefore has cardinality equal to some [tex]\aleph_{\alpha}[/tex]

To SW VandeCarr,

AC equivalent to well-ordering theorem, and from it every set can be well-ordered, hence set of cardinality [tex]2^{\aleph_0}[/tex] can be well ordered. So with AC we can compare cardinalities.

Definition of AC: Every family of non-empty sets has a choice function.

Choice function: If S is a family of sets and [tex]\emptyset \not \in S[/tex] then a choice function for S is f on S such that [tex]f(X) \in X[/tex] for every [tex]X \in S[/tex].

THM: AC -> every set can be well-ordered.
Proof: Let A be a set. For every [tex] \alpha[/tex] we can define
[tex] a_{\alpha} = f(A - \{a_{\xi}: \xi < \alpha\}) [/tex] if [tex] A - \{a_{\xi}: \xi < \alpha\}[/tex] is not empty, by induction. let [tex] \theta[/tex] be the least ordinal such that [tex] A = \{a_{\xi} : \xi < \theta\}[/tex]. So we found enumeration of A.

THM: Every-set can be well-ordered -> AC
Proof: Let S be a family of sets then we shall well-order [tex] \cup S[/tex] and f(X) will be defined as the least element of X for every [tex]X \in S[/tex].

Now since reals is [tex] 2^{\aleph_0} [/tex] then it is can be well-ordered and hence be one of alephs.
SW VandeCarr
#21
Apr6-10, 03:36 PM
P: 2,501
Quote Quote by vici10 View Post
THM: AC -> every set can be well-ordered.
Proof: Let A be a set. For every [tex] \alpha[/tex] we can define
[tex] a_{\alpha} = f(A - \{a_{\xi}: \xi < \alpha\}) [/tex] if [tex] A - \{a_{\xi}: \xi < \alpha\}[/tex] is not empty, by induction. let [tex] \theta[/tex] be the least ordinal such that [tex] A = \{a_{\xi} : \xi < \theta\}[/tex]. So we found enumeration of A.

THM: Every-set can be well-ordered -> AC
Proof: Let S be a family of sets then we shall well-order [tex] \cup S[/tex] and f(X) will be defined as the least element of X for every [tex]X \in S[/tex].

Now since reals is [tex] 2^{\aleph_0} [/tex] then it is can be well-ordered and hence be one of alephs.
Thank you vici10. I do have a couple of (possibly dumb) questions. I assume [tex]\forall a_{\xi}:a_{\xi}\in A[/tex]. What exactly do [tex]\xi[/tex] and [tex]\alpha[/tex] represent?
vici10
#22
Apr6-10, 04:19 PM
P: 41
Quote Quote by SW VandeCarr View Post
I assume [tex]\forall\a_{xi}:a_{\xi}\in A[/tex]. What exactly do [tex]\xi[/tex] and [tex]\alpha[/tex] represent?
The proof is based on induction over ordinal numbers, so [tex]\xi[/tex] and [tex]\alpha[/tex] are ordinal numbers. [tex]a_{\xi} \in A[/tex] because f was a choice function over all non-empty subsets of A (sorry I have not mentioned it in previous post). And by definition of choice function [tex] f(X) \in X[/tex] for any [tex] X \subseteq A[/tex]. Therefore [tex] f(A-\{a_{\xi} : \xi < \alpha\}) [/tex] is an element of A.

Anyway, idea of the proof is simple. Choose one element after another and by doing so you order them.
SW VandeCarr
#23
Apr6-10, 05:05 PM
P: 2,501
Quote Quote by vici10 View Post
The proof is based on induction over ordinal numbers, so [tex]\xi[/tex] and [tex]\alpha[/tex] are ordinal numbers. [tex]a_{\xi} \in A[/tex] because f was a choice function over all non-empty subsets of A (sorry I have not mentioned it in previous post). And by definition of choice function [tex] f(X) \in X[/tex] for any [tex] X \subseteq A[/tex]. Therefore [tex] f(A-\{a_{\xi} : \xi < \alpha\}) [/tex] is an element of A.

Anyway, idea of the proof is simple. Choose one element after another and by doing so you order them.
And one can do this ad infinitum,. "Internally" it seems to work, but we are dealing with at least three equivalent propositions: AC, ZL and WO. Make any one an axiom and you can prove the other two as theorems. All three are independent of ZF in the sense that a presumably consistent, if weaker, set theory can be based on ZF alone.

While I won't pursue the issue here, it seems we could proceed with some kind of constructive approach for the reals with the same logic: constructing the next element ad infinitum by continuation. I don't have a problem using AC in conjunction with other non-equivalent axioms/theorems, but I don't like proofs that essentially rely on AC alone. Thanks for clarifying this for me.


Register to reply

Related Discussions
Well-ordering of reals Set Theory, Logic, Probability, Statistics 13
|P(N)| = |Reals| Calculus & Beyond Homework 1
Well-ordering of the reals General Math 16
Well-ordering of the Reals Set Theory, Logic, Probability, Statistics 4
Can Someone explain Dedikind cuts? Linear & Abstract Algebra 11