Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer
    
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.

share|improve this answer
3  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.