Why Can't Well Ordering of Reals be Proven with Dedekind Cuts?

[SW VandeCarr]

I know this can't be done but I don't know why. It's been established that the Axiom of Choice is required to prove the well ordering of the reals. Why can't we say that for any pair of real numbers a,b in the set R there exists a Dedekind cut that falls between a and b such that always a>b or always a<b?. Does the AC somehow come into play here? I don't see it.

http://www.math.sc.edu/~nyikos/sem.pdf

 

[vici10]

Maybe I misunderstood you, then correct me. But by Dedikind cuts in (Q,<) one will define natural order of R which is not well-ordering. Well ordering of reals is actually 2^{\aleph_0} and needs AC which is equivalent to the fact that any set can be well-ordered.

 

[CRGreathouse]

Right. The natural order < orders the reals, but it does not well-order the reals. For example, there is no least element in (0, 1) with respect to the natural order.

 

[SW VandeCarr]

Right. The natural order < orders the reals, but it does not well-order the reals. For example, there is no least element in (0, 1) with respect to the natural order.

OK, but is it not possible to construct nonempty subsets of the reals using Dedekind cuts such that least elements exist in each subset of the chain beginning with A,B where A has a least element?:

$$A={a\in Q:a^{2}< 2\bigvee a\leq 0}$$
$$B={b\in Q:b^{2}\geq 2\bigwedge b>0}$$

Again I realize AC must be used at some point if the above process doesn't prove R is a well ordered set , but I don't see why this can't be done only with Dedekind cuts on the rationals.

 

[Martin Rattigan]

You seem to be saying that a well-ordering of the reals should follow from their construction as Dedekind cuts, but it's not clear, to me at any rate, what you have in mind.

"Why can't we say that for any pair of real numbers a,b in the set R there exists a Dedekind cut that falls between a and b such that always a>b or always a<b?. "

So long as we understand a genuine pair of (i.e. two distinct) numbers, we can say that, but how does it get any closer to specifying a well order on the reals?

"... is it not possible to construct nonempty subsets of the reals using Dedekind cuts such that least elements exist in each subset of the chain beginning with A,B where A has a least element?"

What chain is that? Do A and B here refer to the lower and upper segments of the Dedekind cut corresponding to $\sqrt{2}$ as defined on the next two lines?

"... if the above process doesn't prove R is a well ordered set , but I don't see why this can't be done only with Dedekind cuts on the rationals"

Do you see why it can be done only with Dedekind cuts on the rationals?

You say at the start, "I know this can't be done", but on what grounds? It seems to conflict with the rest of your post.

 

[SW VandeCarr]

Do you see why it can be done only with Dedekind cuts on the rationals?

You say at the start, "I know this can't be done", but on what grounds? It seems to conflict with the rest of your post.

First, I admit I do not understand the Axiom of Choice (AC). I know what it says, but I don't understand "choosing" in the mathematical sense. Choice is the volitional act of a conscious mind. That's philosophy, not math. I understand you can index the elements of a set of with a bijective mapping from the set of natural numbers allowing the specification of one element from each set of a family of sets, but why do we need an axiom for that? I think we can also define a random variable over a family of sets which "chooses" exactly one element from each set.


I would like to see a proof of the well ordering of the reals without AC (or even some weaker form of choice), but my research indicates this cannot be done even though it's possible to "prove" AC from the well ordering theorem (WOT). Since the Dedekind cut can be used to construct the reals, and the reals can be well ordered by WOT, it seems we can have a "constructive" proof of this well ordering by continuation. That is, if you can construct a lower bound closed set [a,b) of well ordered reals, you can say it applies to all reals by considering the reals as an infinite set of lower bound closed well ordered subsets. I would simply like to know why this isn't the case.

By the way, I'm not a "constructivist". However, a constructive proof ought to be valid.

 

[Martin Rattigan]

I'll attempt a reply to some of your points, though I'm still not clear what you have in mind.

As far as the first paragraph is concerned, you need a choice axiom or something similar to prove results in a formal system, otherwise you simply get stuck proving lots of standard mathematical results. The statement of the axiom would, with the usual interpretation, assert the existence of a set or function. The set or function could be thought of as a choice from an arbitrary collection of nonempty sets, but has not much to do with consciousness.

If you're not proving results in a formal system then you can follow practice prior to about 1900 (and probably mostly since) by taking AC as read, without losing too much - as you apparently do.

Incidentally you say in the first paragraph, "I understand you can index the elements of a set of [sic] with a bijective mapping from the set of natural numbers". This may be meant just as an example, but it's very relevant that you can't index the elements of the set of Dedekind cuts in $\mathbb{Q}$ with a bijective mapping from the set of natural numbers.

Regarding the second paragraph, you say that the reals are well ordered. I trust that you are aware that, as pointed out by CRGreathouse previously, with their usual ordering they are most definitely not (as neither are the rationals). It is more accurate to say that the reals may or may not be well ordered depending on how (and, of course, if) they are ordered.

I really don't understand how analytic continuation is relevant here, so I've assumed you intended the content of the following sentence to clarify this. Unfortunately I also have problems with this sentence.

(1) In the phrase, "finite string of well ordered reals", the term "well ordered" appears to apply to the reals rather than the finite string. Was this intentional? I can't assign any very plausible meaning to an individual well ordered real number, but then a finite string would be necessarily well ordered, so the phrase would be redundant if it applied to the finite string. But what string do you have in mind here anyway?

(2) The "finite disjoint well ordered subsets" referred to are presumably meant to be subsets of $\mathbb{Q}$? If so there are strictly fewer finite subsets of $\mathbb{Q}$ than reals, so how could the reals be regarded as a collection taken from these?

(3) How is the transition from "a finite string of well ordered reals" to all reals meant to work?

 

[SW VandeCarr]

I'll attempt a reply to some of your points, though I'm still not clear what you have in mind.

As far as the first paragraph is concerned, you need a choice axiom or something similar to prove results in a formal system, otherwise you simply get stuck proving lots of standard mathematical results. The statement of the axiom would, with the usual interpretation, assert the existence of a set or function. The set or function could be thought of as a choice from an arbitrary collection of nonempty sets, but has not much to do with consciousness.

If you're not proving results in a formal system then you can follow practice prior to about 1900 (and probably mostly since) by taking AC as read, without losing too much - as you apparently do.

Incidentally you say in the first paragraph, "I understand you can index the elements of a set of [sic] with a bijective mapping from the set of natural numbers". This may be meant just as an example, but it's very relevant that you can't index the elements of the set of Dedekind cuts in $\mathbb{Q}$ with a bijective mapping from the set of natural numbers.

Regarding the second paragraph, you say that the reals are well ordered. I trust that you are aware that, as pointed out by CRGreathouse previously, with their usual ordering they are most definitely not (as neither are the rationals). It is more accurate to say that the reals may or may not be well ordered depending on how (and, of course, if) they are ordered.

I really don't understand how analytic continuation is relevant here, so I've assumed you intended the content of the following sentence to clarify this. Unfortunately I also have problems with this sentence.

(1) In the phrase, "finite string of well ordered reals", the term "well ordered" appears to apply to the reals rather than the finite string. Was this intentional? I can't assign any very plausible meaning to an individual well ordered real number, but then a finite string would be necessarily well ordered, so the phrase would be redundant if it applied to the finite string. But what string do you have in mind here anyway?

(2) The "finite disjoint well ordered subsets" referred to are presumably meant to be subsets of $\mathbb{Q}$? If so there are strictly fewer finite subsets of $\mathbb{Q}$ than reals, so how could the reals be regarded as a collection taken from these?

(3) How is the transition from "a finite string of well ordered reals" to all reals meant to work?

I did some editing of the second paragraph. Instead of "finite string of well ordered reals" I say a lower bound closed set [a.b). In terms of it working, I don't expect it to work since all my sources say we need some version of choice to prove the well ordering of the reals. Also, I just say "continuation".

A well ordered set is a totally ordered set with a minimal element. How can the reals be well ordered if the set of reals has no minimal element? Only by being viewed as an infinite set of subsets, each subset being totally ordered with a minimal element. Presumably, such subsets can be defined: so we have {...{[-1,0)},{[0,1)},{[1,2)}...} There's no appeal to choice here. I'm asking why this (or something like this) can't be done as proof.

 

[Martin Rattigan]

I'm still not following this, so it's probably best if someone else answers your main points.

One thing you seem to be missing (maybe I'm wrong) is that the well orders referred don't have to bear any particular relation to the natural order.

You ask, "How can the reals be well ordered if the set of reals has no minimal element?". The same would apply to the integers. With the natural order:

$\dots -2<-1<0<1<2 \dots$

the integers have no minimum element and the natural order is therefore not a well order. But in this case its easy to specify well orders e.g.:

$0\prec -1\prec -2\prec -3\dots 1\prec 2\prec 3\dots$

The second order is is a well order.

But obviously given that the natural order is not a well order, any well order is necessarily not the natural order.

 

[SW VandeCarr]

If I've been unclear, I apologize to those who responded to my question. I'll try to state my question again:

Given if:

1.A set is well ordered if it is totally ordered and every non empty subset has a minimal element.

2.The well ordering theorem states that every set can be well ordered.

3.It is possible to create a well ordered subset of the real numbers by means of Dedekind cuts.
http://math.andrej.com/wp-content/uploads/2008/08/abstract-cca2008.pdf

Then:

The set of reals can be well ordered such as {...;{[-1,0)};{[0,1)};{[1,2)}:...}.


My research indicates that the Axiom of Choice (AC) is necessary to prove the well ordering theorem applies to the real numbers.
http://books.google.com/books?id=TC...nepage&q=well ordering theorem and ZF&f=false. See: Sec 3 Definable Sets

Question:

Since I did not explicitly use AC, why is what I've shown not a demonstration that AC is not required to show that the real numbers can be well ordered? Please be specific.

EDIT: AC is known to be equivalent to the well ordering theorem(WOT). My point is that WOT could replace AC as an axiom, and AC is not needed, at least for this problem. Please show me where I'm wrong (as I surely must be).

 

[rasmhop]

3.It is possible to create a well ordered subset of the real numbers by means of Dedekind cuts.
http://math.andrej.com/wp-content/uploads/2008/08/abstract-cca2008.pdf

a) How exactly would that help you? There are many well-ordered subsets of the real numbers that are easy to construct. For instance the positive integers. What you need is a well-ordering of an uncountable subset of the reals, but this cannot be done without AC.
b) That paper never seems to mention well-ordering. In fact as far as I can see it just performs a construction of the real numbers with the usual order, which is NOT a well-order.

The set of reals can be well ordered such as {...;{[-1,0)};{[0,1)};{[1,2)}:...}.

No. What element of $\mathbb{R}$ would be minimal? If you could well-order [0,1), then you could well order it by: [0,1), [-1,0), [1,2), [-2,-1), ...
However you can not well-order [0,1) without the axiom of choice ([0,1) has the exact same size as the reals, so there is no difference in well-ordering [0,1) or the reals).

I admit I do not really understand the construction you're trying to undertake, but in all your attempts you seem to construct the usual order on the real numbers, but that doesn't work as (0,1) has no minimal element.

Since I did not explicitly use AC, why is what I've shown not a demonstration that AC is not required to show that the real numbers can be well ordered? Please be specific.

No. Because as far as I can see your construction doesn't work, and I know that it will never be able to work because we have proven that you CANNOT well-order the reals without the AC.

 

[CRGreathouse]

Given if:

1.A set is well ordered if it is totally ordered and every non empty subset has a minimal element.

2.The well ordering theorem states that every set can be well ordered.

3.It is possible to create a well ordered subset of the real numbers by means of Dedekind cuts.
http://math.andrej.com/wp-content/uploads/2008/08/abstract-cca2008.pdf

Then:

The set of reals can be well ordered such as {...;{[-1,0)};{[0,1)};{[1,2)}:...}.

#1 is a definition, you don't need to count that as an assumption. #2 requires (indeed, is equivalent to) the Axiom of Choice. #3 is unclear and not sufficient to well-order the reals.

 

[SW VandeCarr]

#1 is a definition, you don't need to count that as an assumption. #2 requires (indeed, is equivalent to) the Axiom of Choice. #3 is unclear and not sufficient to well-order the reals.

Thanks GR and others who responded. #3 was the weak premise. I thought that if Dedekind cuts could construct the reals (which apparently they can), the well ordering of the reals (as presumably proven by the AC) might be evident from construction alone.

All responders made the point that the natural order is not a well order, presumably because there is no minimal element for the integers, rationals and reals. However as I read the the first part of the definition of well ordering, a well ordered set must be totally ordered. Would this requirement be satisfied if for every n.e.subset [a,b) b>a ?

In addition, the definition states every subset of a well ordered set must have a minimal element. The set I constructed, using disjoint subsets of the form [a,b), b>a would seem to satisfy this part of the definition of well ordering if by every subset, it means every n.e. subset of a particular "well ordering" However, at least with respect to the reals, I'm thinking it means the power set of $$\aleph_{0}$$ (according to vici10). If so, it seems that subsets of the form [a,b) b>a would still be correct.

So, one flaw is that construction of the reals by Dedekind cuts does not prove that the reals can be well ordered without the AC.

Regarding the second point, I think I'm correct in saying all n.e. subsets of the reals in the form [a,b), b>a satisfies the requirement that every n.e. subset of the reals has a minimal element, but please correct me if I'm wrong.

 

[rasmhop]

Regarding the second point, I think I'm correct in saying all n.e. subsets of the reals in the form [a,b), b>a satisfies the requirement that every n.e. subset of the reals has a minimal element, but please correct me if I'm wrong.

This makes no sense. It's like saying all integers of the form 4n with n integer satisfies the requirement that every integer is even. It's true that every integer of the form 4n is even, but not that every integer is even. In the same way it's true that with the usual order [a,b) has a minimal element and the real numbers are well-ordered, but that's just not enough. Not every subset of the real numbers is of the form [a,b). I think you may have misunderstood the idea of a well-ordering. It's simply a total order for which every non-empty subset of the real numbers has a minimal element.

Can you tell me what element of the integers is minimal? If not, then your order is not a well-ordering because the integers is a non-empty subset of the real numbers so it must have a minimal element. No matter what non-empty subset of the real numbers I throw at your order it must be possible to point out a minimal element.

The set I constructed, using disjoint subsets of the form [a,b), b>a would seem to satisfy this part of the definition of well ordering if by every subset, it means every n.e. subset of a particular "well ordering

It does not mean that. A well-ordering is an order, not a collection of subsets of the reals. By non-empty subset of the reals, it means exactly that: ANY non-empty subset of the reals. Including the open intervals like (0,1). The subsets of the reals are independent of any ordering on the reals.

 

[vici10]

SW VandeCarr,

I think that your main problem is in thinking of well-ordered reals as usual real numbers. The word reals is maybe what mislead you. Well-ordered reals are just a set of size 2^{\aleph_0} with well-order on it. It is more correct in my opinion to think about it as one of the alephs (think of aleph_1 aleph_2 etc). Of course we do not know which aleph it is since it is independent of ZFC (axioms of set theory).

 

[CRGreathouse]

All responders made the point that the natural order is not a well order, presumably because there is no minimal element for the integers, rationals and reals. However as I read the the first part of the definition of well ordering, a well ordered set must be totally ordered. Would this requirement be satisfied if for every n.e.subset [a,b) b>a ?

I don't know what you mean by "n.e.subset". But I'll say this: the natural order < does not well-order any uncountable subset of the reals. If you want to well-order something big like [0, 1) you'll need to use a different order than <.

Regarding the second point, I think I'm correct in saying all n.e. subsets of the reals in the form [a,b), b>a satisfies the requirement that every n.e. subset of the reals has a minimal element, but please correct me if I'm wrong.

Every nonempty half-open interval [a, b) has a minimal element with respect to <. But that doesn't help you make a well-order, since each such interval contains subsets which do not have minimal elements with respect to <.

If you're trying to construct a foo rather than a well-order, where:
A well-order is a total order ≺ on S with the property that every non-empty subset of S has a ≺-minimal element.
A foo is a total order ≺ on S with the property that every non-empty half-open interval [a, b) has a ≺-minimal element.
then setting ≺ = < and S = R does indeed give you a foo. But if you're trying to get a well-order, this won't work.

 

[CRGreathouse]

It is more correct in my opinion to think about it as one of the alephs (think of aleph_1 aleph_2 etc).

Would you expand on this? I don't see why it would be better to say it's some (the unique!) $$\aleph_\kappa$$ with $$\aleph_\kappa=\beth_1$$ rather than just biting the bullet and saying it's $$\beth_1$$.

 

[SW VandeCarr]

foo[/i] is a total order ≺ on S with the property that every non-empty half-open interval [a, b) has a ≺-minimal element.
then setting ≺ = < and S = R does indeed give you a foo. But if you're trying to get a well-order, this won't work.

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 http://en.wikipedia.org/wiki/Well-ordering_theorem" [Broken] 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]

Would you expand on this? I don't see why it would be better to say it's some (the unique!) $$\aleph_\kappa$$ with $$\aleph_\kappa=\beth_1$$ rather than just biting the bullet and saying it's $$\beth_1$$.

You can think about it as about $$\beth_1$$, since $$\beth_1=2^{\aleph_0}$$ 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 $$2^{\aleph_0}$$

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

To SW VandeCarr,

AC equivalent to well-ordering theorem, and from it every set can be well-ordered, hence set of cardinality $$2^{\aleph_0}$$ 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 $$\emptyset \not \in S$$ then a choice function for S is f on S such that $$f(X) \in X$$ for every $$X \in S$$.

THM: AC -> every set can be well-ordered.
Proof: Let A be a set. For every $$\alpha$$ we can define
$$a_{\alpha} = f(A - \{a_{\xi}: \xi < \alpha\})$$ if $$A - \{a_{\xi}: \xi < \alpha\}$$ is not empty, by induction. let $$\theta$$ be the least ordinal such that $$A = \{a_{\xi} : \xi < \theta\}$$. 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 $$\cup S$$ and f(X) will be defined as the least element of X for every $$X \in S$$.

Now since reals is $$2^{\aleph_0}$$ then it is can be well-ordered and hence be one of alephs.

 

[SW VandeCarr]

THM: AC -> every set can be well-ordered.
Proof: Let A be a set. For every $$\alpha$$ we can define
$$a_{\alpha} = f(A - \{a_{\xi}: \xi < \alpha\})$$ if $$A - \{a_{\xi}: \xi < \alpha\}$$ is not empty, by induction. let $$\theta$$ be the least ordinal such that $$A = \{a_{\xi} : \xi < \theta\}$$. 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 $$\cup S$$ and f(X) will be defined as the least element of X for every $$X \in S$$.

Now since reals is $$2^{\aleph_0}$$ 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 $$\forall a_{\xi}:a_{\xi}\in A$$. What exactly do $$\xi$$ and $$\alpha$$ represent?

 

[vici10]

I assume $$\forall\a_{xi}:a_{\xi}\in A$$. What exactly do $$\xi$$ and $$\alpha$$ represent?

The proof is based on induction over ordinal numbers, so $$\xi$$ and $$\alpha$$ are ordinal numbers. $$a_{\xi} \in A$$ 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 $$f(X) \in X$$ for any $$X \subseteq A$$. Therefore $$f(A-\{a_{\xi} : \xi < \alpha\})$$ 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]

The proof is based on induction over ordinal numbers, so $$\xi$$ and $$\alpha$$ are ordinal numbers. $$a_{\xi} \in A$$ 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 $$f(X) \in X$$ for any $$X \subseteq A$$. Therefore $$f(A-\{a_{\xi} : \xi < \alpha\})$$ 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 anyone 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.