I'm confused by the well-ordering principle . The proof is clear but I don't have any idea why is it true . It says that every non-empty set can be well-ordered but $C^{1}$ is a non-empty set but there's no linear order defined on it . Furthermore , I don't know how to define well-ordering relation on an open subset of $R^{1}$ e.g $(0,1)$

  • $\begingroup$ Does $C^1$ refer to the complex numbers? Because it is also the notation for all the continuously-differentiable functions (from $\Bbb R$ to itself). But the reference to a linear order seem to imply that you mean $\Bbb C$ which is the complex numbers rather than the functions. $\endgroup$
    – Asaf Karagila
    Apr 6 '13 at 14:49

The well-ordering principle is non-constructive, in the sense that it doesn't tell you how to well-order a certain set, but rather that some well-order exists.

This well-order is often completely incoherent with the natural structure of the set you will consider, for example in the case of $(0,1)$. The well-order will disagree with the $<$ order in most cases.

But that's fine. Note that we can define a dense order on $\Bbb N$ by taking a bijection with $\Bbb Q$ and "pulling back" the order of the rationals. Does this order agree with the usual order on the natural numbers? Hardly. But that's fine.

Note that you can find a bijection between $\Bbb C$ and $\Bbb R$, and this bijection does define a linear ordering of $\Bbb C$. Again, this linear ordering is completely incoherent with the structure of $\Bbb C$, but such order does in fact exist -- even if it doesn't respect other structure of the set.

For the case of $(0,1)$, or any other set of cardinality $2^{\aleph_0}$ we can even prove that without using the well-ordering principle (or the axiom of choice, or some other equivalent of course) we might not be able to well-order $(0,1)$. These proofs are rather technical and difficult, but the key point is that we can produce models of set theory where the axiom of choice fails and $(0,1)$ cannot be well-ordered.

  • $\begingroup$ That cleared my confusion , thanks . $\endgroup$
    – billy
    Apr 6 '13 at 15:08
  • $\begingroup$ It's surprising that there are models of set theory in which the axiom of choice fails . I think is axiom of choice is so natural that I can't imagine a situation in which it fails . $\endgroup$
    – billy
    Apr 6 '13 at 15:10
  • $\begingroup$ billy, yes the axiom of choice is very natural. In fact it is so natural that many of the advocates against it in the early 20th century were actually using weakened forms of it without noticing. But sure enough, it can fail. It is just one of the things that show how little our intuition holds for infinite sets (because it cannot fail for finite families of non-empty sets). $\endgroup$
    – Asaf Karagila
    Apr 6 '13 at 15:11
  • $\begingroup$ Can you give an example in which it fails ? My guess would be an uncountable collection of sets e.g If we consider $R^{1}$ and all of it's possible subsets "The power set of $R^{1}$ but I'm not sure. $\endgroup$
    – billy
    Apr 6 '13 at 18:42
  • $\begingroup$ billy, as my comment to your question - do you mean $\Bbb R$ (the real numbers) when you write $R^1$? If so, then there are models of set theory in which the axiom of choice fails and $\Bbb R$ cannot be well-ordered, so there is no choice function on non-empty sets of real numbers. In any case, no it is impossible to "give a model" because the construction of these models is quite technical and requires some heavy set theoretical machinery to work. There are tons of fine and delicate points to notice when discussing models of set theory. $\endgroup$
    – Asaf Karagila
    Apr 6 '13 at 18:50

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.