A partially ordered set $(S,\le)$ is called interval finite if the open intervals $(x,z):=\{y|x\le y\le z\}$ are finite for all choices of $x,z$ in $S$. An embedding $(S,\le)\rightarrow(S',\le')$ of partially ordered sets is an injective order-preserving map. Does every countably infinite interval finite partially ordered set admit an embedding into the integers? This is equivalent to extending the partial order to a linear suborder of the integers. If so, where can I find the proof? If not, can you give a counterexample?

  • 3
    $\begingroup$ I don't understand the votes to close, since this is an interesting problem, and I think it is trickier than it may seem at first. Could someone explain? $\endgroup$ Sep 24, 2013 at 13:56
  • $\begingroup$ Related. $\endgroup$ Sep 24, 2013 at 23:56

1 Answer 1


$\newcommand{\P}{\mathbb{P}} \newcommand{\Z}{\mathbb{Z}}$

The answer is yes. First, let's prove a lemma. By order preserving, I assume that you mean forward-preservation of the order: $p\leq q\implies f(p)\leq' f(q)$.

Lemma. Every countable interval-finite partial order $\P$ has a convex enumeration, an enumeration $\langle p_0,p_1,p_2,\ldots\rangle$ of $\P$, all of whose initial segments are convex sets in $\P$.

Proof. If we have a finite convex subset of $\P$, and new point $p$ to be added, then by convexity $p$ does not appear in any interval of points we already have. If $p$ is above some points we have already, then it is not below any point that we have already, and so we can look at the intervals $(q,p)$ determined by a point $q$ we have already and the new point $p$. By convexity, none of these new points can be below any point we already have, and so we can simply add them from the bottom while maintaining convexity. A similar argment works if the new point is only below points we already have. And if $p$ is incomparable to the points we already have, then we can simply add it to the list. QED

Now, we can prove the theorem.

Theorem. Every countable interval-finite partial order embeds into $\Z$.

Proof. Suppose that $\P$ is a countable interval-finite partial order. By the lemma, it has a convex enumeration $p_0,p_1,p_2,\ldots$. Suppose by induction that we have mapped $p_k\mapsto m_k$ in an injective order-preserving manner, for $k\lt n$. Consider the next point $p_n$. Since the order so far is convex and adding $p_n$ maintains convexity, it follows that either $p_n$ is above some points $p_k$ for $k\lt n$ and not below any, or below some such $p_k$ and not above any, or incomparable to them all. In any case, we can easily extend the map to define $p_n\mapsto m_n$ in such a way to still be order preserving and injective. QED

  • $\begingroup$ Joel, thanks, that's terrific. I wonder if you know the origin of this result, since I need to cite it. $\endgroup$
    – Ben
    Sep 24, 2013 at 17:59
  • $\begingroup$ I've never seen it before, but I'd expect that probably this has been known. Perhaps someone else can post a source? $\endgroup$ Sep 24, 2013 at 18:07
  • 1
    $\begingroup$ The link above discusses the source and gives a reference. $\endgroup$ Sep 24, 2013 at 23:56
  • $\begingroup$ (By the way, the question in the link is still unsolved without choice, in case you have some ideas.) $\endgroup$ Sep 25, 2013 at 0:00
  • $\begingroup$ @Andres, thanks for the reference! The OP on this question, however, insists on injective order-preserving maps, and so there can be no uncountable instances. So it seems that these are slightly different questions, although obviously closely connected. $\endgroup$ Sep 25, 2013 at 0:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .