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

SW VandeCarr

OK. Can you, or anyone else, please tell me how you can perform the miracle of proving the real numbers can be well ordered with the Axiom of Choice?

rasmhop

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

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

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

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

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.