# Countability of a certain set

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.

-

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.

-
So, assuming that $S$ is infinite. Do we first suppose that it is infinite, or do we proceed directly without that second supposition? :-) –  Asaf Karagila Dec 28 '13 at 18:52
Derp. Not sure why I stated that assumption twice. –  Cameron Buie Dec 28 '13 at 19:00

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.

-
Or to the reverse order on $\mathbb{N}$. –  universalset Dec 28 '13 at 18:44
True dat.${}{}{}$ –  Asaf Karagila Dec 28 '13 at 18:46
Drat. Skunked me. +1 from me. –  Cameron Buie Dec 28 '13 at 18:49
@Cameron: I just wondered about that. Well, it's just that I gave my students a relatively similar problem some weeks ago, so I had all those hints prepared in my head. ;-) –  Asaf Karagila Dec 28 '13 at 18:49