Is every discrete topological space orderable?

Question

I apologize for asking a question in topological terms when it's not really about topology, but here goes:

If $S$ is a set, is it always possible to totally order $S$ so that every non-minimal element has an immediate predecessor and every non-maximal element has an immediate successor?

This does not hold in ZF because the ordering principle is independent of ZF, but I wonder if it holds given AC (or some weakening thereof).

I believe it holds if every uncountable set can be partitioned into (uncountably many) countably infinite sets, but I don't know if this is true.

Answer 1

This is possible when assuming the axiom of choice.

Given an infinite cardinal $\kappa$, we replace each point by a copy of the integers. The result is an order of cardinality $\kappa$ (this is really just the set $\kappa\times\Bbb Z$ whose cardinality is always $\kappa$). Note that we don't really care that $\kappa$ is a well-order, any linear order would suffice.

Now suppose that $A$ is infinite, it can be put in bijection with such ordered set, and we are done. Every element has an immediate successor and an immediate predecessor. Since there are no minimal and maximal elements the rest is vacuous.

You are also correct that this cannot be proved without the axiom of choice, because it is consistent that there sets which cannot be linearly ordered at all. As for a "minimal" choice principle, I can't think of any, but it might be provable from the two assertions:

1. Every set can be linearly ordered.
2. For every infinite set $A$, $|A\times\Bbb N|=|A|$.

The conjunction of these two is not sufficient to prove the axiom of choice itself.