1
$\begingroup$

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}$)?

$\endgroup$
  • 1
    $\begingroup$ every set is orderable. So I would say no. Ordering has nothing to do with countability. $\endgroup$ – user126154 Jun 18 '14 at 22:41
  • 1
    $\begingroup$ 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 $\endgroup$ – user126154 Jun 18 '14 at 22:43
2
$\begingroup$

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$.

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

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.