25
$\begingroup$

We know without any doubt that the axiom of choice implies (in fact is equivalent to) the well ordering principle.

The well ordering principle can't be true! If we take the open interval $(0,1)$ for example, there can't be a least (or most) element. If you give me any element of this set, I could always find one that is greater than or smaller than the one you give me.

Isn't this enough to conclude that the axiom of choice - though intuitive - should be viewed as untrue?

Thanks.

$\endgroup$
  • 17
    $\begingroup$ The standard ordering ≤ of any real interval is not a well ordering; this is why $(0,1)$ lacks a least element. The well-ordering principle simply states that there exists a well-order. $\endgroup$ – MathematicsStudent1122 May 8 '16 at 3:07
  • 20
    $\begingroup$ Why the downvotes? OP has put some thought into this. Though his reasoning is incorrect, the question, in my opinion, is certainly not bad. $\endgroup$ – MathematicsStudent1122 May 8 '16 at 3:11
  • 18
    $\begingroup$ @MathematicsStudent1122 I suppose that one might downvote because of the style of the question; rather than starting with "Wow, there are many mathematicians that think something, perhaps I've misunderstood," they rather start off with a statement that's as wrong as it is emphatic. $\endgroup$ – user296602 May 8 '16 at 3:14
  • 9
    $\begingroup$ @KennyLau No. That is trivial. The axiom of choice says that you can simultaneously choose an element from any (set-sized) collection of nonempty sets. $\endgroup$ – Andrés E. Caicedo May 8 '16 at 3:31
  • 8
    $\begingroup$ "The axiom of choice is clearly true, the well ordering principle is clearly false, and who can say about Zorn's Lemma" $\endgroup$ – Lonidard May 8 '16 at 7:02
53
$\begingroup$

The well-ordering principle does not say, "Every linear order is a well-ordering." It says, "Every set can be well-ordered."

For instance, the set of integers is usually ordered as: $. . . -3<-2<-1<0<1<2<3<. . .$. This is clearly not a well-ordering. However, we can define a new ordering, $\prec$, as follows: $$0\prec -1\prec 1\prec -2\prec 2\prec -3\prec 3\prec . . .$$ This is a well-ordering of the set $\mathbb{Z}$.

So, in order to show that e.g. $(0,1 )$ is not well-orderable, you need to not only show that the usual ordering is not a well-ordering, but that no possible ordering is a well-ordering. This is not something you can do, using only the axioms of ZF: it is consistent with ZF that $(0, 1)$ can be well-ordered. Indeed (assuming ZF is consistent in the first place), Godel showed that ZF + "Every set can be well-ordered" is consistent.

One thing we can show is that any possible well-ordering of $(0, 1)$ would have to be extremely complicated - e.g., not Borel. This is one of the subjects of descriptive set theory, and (depending on your philosophical outlook) you might think that results like this provide evidence that the well-ordering principle is false. But they're far from a proof of its falsehood.


It also seems like you might have some confusion over what a well-ordering is. Maximal elements don't enter into it - a linear order $L$ is a well-order if every (nonempty :P) subset of $L$ has a least element. Alternatively (in the presence of a small amount of the axiom of choice :P), a linear order $L$ is a well-order if there is no infinite descending sequence in $L$.


Let me add one important side note: that we can prove, without using the axiom of choice, that there are uncountable well-ordered sets. The standard example is the set of countable ordinals, but there are others. This is treated more in detail elsewhere on this site, so I won't touch on it further, but even without AC the well-orderable sets are many and rich.

$\endgroup$
  • 2
    $\begingroup$ @KennyLau What do you mean by "2-adic"? The 2-adics are not real numbers . . . Can you explain how exactly you intend to order $(0, 1)$? $\endgroup$ – Noah Schweber May 8 '16 at 3:16
  • 1
    $\begingroup$ Sorry I may be using the wrong term... $$0.5\prec0.25\prec0.75\prec0.125\prec0.375\prec0.625\prec0.875\prec\cdots$$ $\endgroup$ – Kenny Lau May 8 '16 at 3:17
  • 7
    $\begingroup$ @KennyLau OK, where do the irrationals show up? $\endgroup$ – Noah Schweber May 8 '16 at 3:18
  • 3
    $\begingroup$ @Andrew Well, it is one that is "less than or equal to" all the others, if you don't have to use the normal definition of "less than or equal to". $\endgroup$ – immibis May 8 '16 at 5:44
  • 2
    $\begingroup$ I think in the last sentence of your second-last paragraph, instead of "L is a linear order if..." you mean "L is a well-order if...". $\endgroup$ – Ari Brodsky May 8 '16 at 14:42
24
$\begingroup$

Noah wrote an excellent answer. But let me make one of his points even clearer.

Sets do not carry any structure. Some sets, however, arise in a very natural way from structure, that when we write them we implicitly think about them as structured sets. $\Bbb R$ is just a set, but we think about it as an ordered field. $\ell^2$ is just a set, but we think about it as a vector space. In fact, it might as well be the same set as $\Bbb R$, as they are both equipotent.

So when you say something like $(0,1)$ can be well-ordered, you mean that the set $(0,1)$ can be well-ordered. Not that the ordered set $(0,1)$ is well-ordered.

If you are able to accept that the rational numbers are countable, they clearly they can be well-ordered. And this is the main and most important thing to remember. There can be no well-ordering of the rationals which agrees with the usual ordering of the rationals "for too long". In particular, any enumeration of the rational numbers can only agree with the usual ordering on some finite subsets.

The axiom of choice, if so, implies that there is an ordering on the set $(0,1)$ which is a well-ordering. But even without the axiom of choice, here's a neat trick to confuse you a little bit.

Instead of $(0,1)$ let's consider $\Bbb R$. They are order isomorphic, it's just going to be more natural on $\Bbb R$.

Note that every real number can be uniquely written as an ordered pair $(k,r)$ where $k\in\Bbb Z$ and $r\in[0,1)$. Namely, $x\mapsto(\lfloor x\rfloor,x-\lfloor x\rfloor)$ is a bijection. And it is not hard to see that this is in fact an order isomorphism between $\Bbb R$ with its usual ordering, and the lexicographic order of $\Bbb Z\times[0,1)$.

Now reverse this product, and consider the lexicographic ordering on $[0,1)\times\Bbb Z$. Of course there is a bijection between this set and $\Bbb R$, so this induces an ordering on the real numbers. But in this ordering every real number has a successor. In this ordering there is a smallest positive real number (that's $1$, by the way).

How could this be? Well. We didn't postulate that the usual ordering of $\Bbb R$ is such that every element has an immediate successor and predecessor. We showed that there is an ordering which satisfies that. And the axiom of choice does not suggest that the usual ordering of any set which you have an implicit structure on is a well-order, it just says that there exists some ordering which is likely to ignore that implicit structure, and well-order that set.

(By the way, the above trick can be replaced by recalling that $\Bbb{R\times N}$ is also equipotent with $\Bbb R$, so you can write $\Bbb R$ as a bunch of sequences. But this equipollence is slightly less natural than the decomposition to $\Bbb Z\times[0,1)$.)

$\endgroup$
  • $\begingroup$ (Any enumeration of $\mathbb Q$ agrees with the usual ordering on an infinite set.) $\endgroup$ – Andrés E. Caicedo May 8 '16 at 5:03
  • 3
    $\begingroup$ But not consecutively, which is what I meant. $\endgroup$ – Asaf Karagila May 8 '16 at 5:15
  • $\begingroup$ Good point! The rationals on (0,1) with usual order are clearly not well ordered by precisely the op's argument. Yet the the set can clearly be well ordered by a lexigraphic order: 1/2 < 1/3 < 2/3 < 1/4 < 3/4 < 1/5 < 2/5 <3/5 ...etc. $\endgroup$ – fleablood May 8 '16 at 6:24
  • $\begingroup$ @fleablood Doesn't you ordering suffer from the same problem that Kenny Lau's comment has in the other answer; it never touches the irrationals? $\endgroup$ – Guntram Blohm May 9 '16 at 6:15
  • 1
    $\begingroup$ What I liked very much about @AsafKaragila's post was that as well as explaining the OPs misunderstanding of well-ordered principal not being restricted to the normative order and pointing that there could be a well ordering of the Reals (although no-ones discovered it yet) he points out that a well ordering of the rationals is easy but is not the normative order. I was merely pointing out that OPs argument that (0,1) can't be well-ordered because the normative order isn't fails when you consider just the rationals. $\endgroup$ – fleablood May 9 '16 at 15:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.