# Does every countably infinite interval-finite partial order embed into the integers?

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?

• 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? Sep 24 '13 at 13:56
• Sep 24 '13 at 23:56


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

• Joel, thanks, that's terrific. I wonder if you know the origin of this result, since I need to cite it.
– Ben
Sep 24 '13 at 17:59
• I've never seen it before, but I'd expect that probably this has been known. Perhaps someone else can post a source? Sep 24 '13 at 18:07
• The link above discusses the source and gives a reference. Sep 24 '13 at 23:56
• (By the way, the question in the link is still unsolved without choice, in case you have some ideas.) Sep 25 '13 at 0:00
• @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. Sep 25 '13 at 0:07