2
$\begingroup$

How is well-ordering in real line possible?

I know that the axiom of choice provides possible well-ordering, but intuitively, this does not seem to make sense.

How can you compare 1.111111.... and 1.111111... when we can never know the full digits of each number?

  • 6
    To paraphrase von Neumann, it's not supposed to make sense, you just get used to it.2012-05-29

3 Answers 3

10

First let us consider an example.

Consider the following order $\prec$ on $\mathbb N$:

$$m\prec n\iff\begin{cases} m\text{ is even},\ n\text{ is odd}\\ m,n\text{ are even },\ m

In simple terms we took all the odd numbers and declared them larger than all the even numbers, but between two even numbers (or two odd numbers) the relation is the same.

To see this is a well-order, first note that it is a (strict) linear order. Every two elements are comparable. Either both have the same parity and we know what to do, or one is odd and one is even and we know what to do.

Now consider $A\subseteq\mathbb N$ non-empty, if it contains even numbers then the smallest even number (in the usual ordering, $\lt$) is the minimal element of $A$. Otherwise $A$ contains only odd numbers, and therefore the minimal (again in the sense of $\lt$) is the minimal element of $A$.

Okay, so we have a well ordering of $\mathbb N$, big whoop. But wait, what is the successor of $0$ in this ordering? What is the number that comes right after $0$? It is no longer $1$, but now it is $2$. On the other hand, how many numbers are smaller (in the sense of $\prec$) than $1$? Well, all the even numbers are, so we have infinitely many of them. The order looks like this:$$0,2,4,6,8,10\ldots,1,3,5,7,9,\ldots$$

Right, what was that good for? Well, first it helps to understand that well ordering is not necessarily the usual order on the natural numbers. In fact there are so many different ways to well order $\mathbb N$ that we cannot describe each and every one of them. There are uncountably many ways, to be more accurate, to do so (even if we consider two the same if they are order isomorphic).

I think that we can now move to discuss a well order of the real numbers. The real numbers can be well ordered as a trivial consequence of the axiom of choice (well, every set can be well ordered using the axiom of choice and in particular the real numbers). However we cannot describe, as I did with $\prec$ above, any way to well order the real numbers. There are certain situations where we can give a nice definition of such well order, but generally speaking we can only prove the existence of this well order, and indeed we need the axiom of choice to prove this existence.

This is very much like that we can prove that there are numbers which are irrational, but we cannot name too many of them. In fact, most real numbers are transcendental and we cannot even describe them using $+,-,\times,/,\sqrt[n]{}$ and the integers. We can still prove that they exist though.

One last remark on the above, this does not mean that every uncountable set is so complicated that we cannot describe an explicit well ordering of it. There are uncountable sets whose order is rather simple, but this post is already long enough.

  • 0
    I think I'm missing something, but if there is an uncountable set $X$ whose order $<$ is simple, can't you just take $A\subseteq X, |A| = |\Bbb R|$, fix a bijection $f$, and define $(x,y)\in \prec$ iff $(f^{-1}(x), f^{-1}(y))\in <$ to get an explicit well ordering on the reals? I suppose the given bijection must be hard to describe, but I don't know for sure. Lastly, could you give an example of an uncountable set with a simple order?2016-07-16
  • 1
    An uncountable set with a simply described well-order is easy. $\omega_1$. If you want something more "tangible", then the set of isomorphism classes of well-orderings of $\Bbb N$, ordered using order-preserving injections (which can be lifted to an order between the isomorphism classes). But why do you suppose that there is a bijection of this set with $\Bbb R$? And even if there is, why do you such a bijection is describable in simple terms? Once you allow a parameter, *everything* is simple: take the well-order itself as the parameter. No, you have to appeal to AC here, which is not simple.2016-07-16
3

I'm not sure you understand what well-ordering is. It has very little to do with comparing, in the sense of the usual ordering a set may have. For example, the usual ordering of the rationals is not a well-ordering, but one can explicitly construct a well-ordering of the rationals which bears essentially no relation to the usual ordering.

  • 3
    Just in case, to complete, I show the well ordering of the rationals. We define the height of a rational number in irreducible form $p/q$ as being $|p|+|q|$. Then we order the rational numbers by increasing height, and in each height class, we class it by increasing denominator. That gives an well ordering that has nothing to do with the usual order.2012-05-29
  • 0
    So, my point is, respecting the order of real line, well-ordering is not possible, right?2012-05-29
  • 0
    Yes, that comes from the fact that between two different real numbers, there is always a third one between them. So there's nothing like a 'successor'. The problem is that there is a theorem that says that we can't 'show' a well ordering of the reals, so it exists, but we can't see.2012-05-29
  • 0
    The axiom of choice can have startling consequences. Try writing a basis for the reals over the rationals. Before beginning, realize such a thing is necessarily uncountable.2012-05-29
  • 0
    You can try also to describe a non measurable set using it. Once more, without the axiom of choice, you can't do it!2012-05-29
  • 1
    In fact, regardless of the cardinality of the continuum you can't exhibit an uncountable well-ordered sequence of reals that respects their usual order.2012-05-29
2

Using the axiom of choice there exists a well-ordering of the real numbers. The axiom of choice does not say anything about whether this well-ordering has any relation to the actually linear ordering on $\mathbb{R}$.

Also you don't need to know decimal representation. A real number is some object. In this well-ordering given by the axiom of choice, it could well happen that $\pi <_W \sqrt{2}$.

In fact the well-ordering is constructed intuitively as follows: Pick an element $a_0 \in \mathbb{R}$. Define $A_0 = \{a_0\}$. Pick an element $a_1 \in \mathbb{R} - A_0$. Define $A_1 = A_0 \cup \{a_1\}$. Defined $a_0 <_W a_1$. Continue this process. To formally do this in set theory requires the axiom of choice and some transfinite recursion.