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

Question

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?

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