Countability of a certain set

Question

Suppose $S$ is a totally ordered set such that for any $x,y\in S$ there are finitely many elements between them. Does it follow that $S$ is (at most) countable?

It seems like the answer should be yes, but I can't think of a proof.

Answer 1

Even more can be said, in fact. Exactly one of the following must hold:

• $S$ is finite.
• $S$ is order-isomorphic to the positive integers.
• $S$ is order-isomorphic to the negative integers.
• $S$ is order-isomorphic to the integers.

To prove this, you'll want to proceed by cases. If $S$ is finite, then we're done, so we may suppose that $S$ is infinite. If $S$ has a least element, say $x,$ then any $y\in S$ is uniquely determined by the number of elements of $S$ between $x$ and $y$ (inclusive). This readily lets us develop an isomorphism with the positive integers. If $S$ has no least element, but has a greatest element, say $x,$ then by similar reasoning, we find that $S$ is order-isomorphic with the negative integers. If $S$ has neither a least nor a greatest element, then fix any $x\in S.$ Reasoning as above, the set of $y\in S$ less than $x$ can be shown to be order-isomorphic to the negative integers; those greater than $x,$ to the positive integers, and so $S$ is order-isomorphic to the integers. All that remains is to justify why $S$ cannot have a least and greatest element if it is infinite, which is simple.

Answer 2

Yes.

To see that, note that if we fix $x\in S$, then for every $y\in S$, the cardinality of the interval $[x,y]$ (if $x<y$) or $[y,x]$ (if $y<x$) uniquely determines $y$. Using this fact we can easily construct an embedding of $S$ into $\Bbb Z$.

Moreover, if $S$ is infinite, then either it is isomorphic to the positive integers, or the negative integers, or the integers.