# Is (total-)order a weak version of countability?

One can easily see that countability also imposes or enables an ordering of the set.

Now $\mathbb{R}$ is ordered but not countable.

Is this ordering a weaker version of countability (at least in some sense)? If so, what about sets that are both un-countable and not ordered (like $\mathbb{C}$)?

• every set is orderable. So I would say no. Ordering has nothing to do with countability. – user126154 Jun 18 '14 at 22:41
• More generally, every set can be well-ordered. Well-ordering can be though as a generalization of countability as indeed permits transfinite induction. But the cardinality has nothing to do with orderability – user126154 Jun 18 '14 at 22:43

Every set can be partially ordered. This is easy, just take $\leq_A=\{(a,a)\mid a\in A\}$ and verify that this is a partial order.

Being countable means that you can more than just partially ordered. You can be well-ordered. Namely, a linear ordering (which itself is a stronger requirement than just partial ordering) and that every non-empty set has a least element.

In fact, the real kicker about being countable is that you can well-order the set so that every element has only finitely many predecessors. Something might not be doable otherwise.

On the other hand, $\Bbb R$ is linearly ordered quite naturally. So every set which have the same size as $\Bbb R$ can be linearly ordered. In the case of $\Bbb C$ you can even do that explicitly: $a+bi\leq c+di\iff a<c\lor (a=c\land b\leq d)$ where $a,b,c,d\in\Bbb R$ and $i$ is the square root of $-1$.

The generalization of countability, however, is well-orderability. Meaning that there is a linear ordering of the set that every non-empty subset has a minimum with respect to that order. The axiom of choice guarantees that every set can be well-ordered. But without it it is consistent that there are sets which cannot be well-ordered, for example it is consistent that $\Bbb R$ cannot be well-ordered.

Note, however that such well-ordering need not agree with other naturally occurring structure on the set. So if $\prec$ is a well-ordering on $\Bbb R$, and so $\Bbb R\setminus\{0\}$ has a minimum element with respect to $\prec$, but certainly this element is not the minimum with respect to the natural $<$ we have on $\Bbb R$.

• elegant analysis and to the point (at least as far as i'm concerned) – Nikos M. Jun 18 '14 at 22:51

Assuming the axiom of Choice, every set has an ordering (a well-ordering even!).

You can have an order on $\Bbb C$, just not one that respects the field operations. Lexicographic is a convenient one, or you can choose your favorite bijection with $\Bbb R$ and use that order. You can also have a partial order (or non-strict total order) based on the magnitudes of the points. I don't think I would call it a version of countability.