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 '13 at 13:56
  • $\begingroup$ Related. $\endgroup$ Sep 24 '13 at 23:56

$\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 '13 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 '13 at 18:07
  • 1
    $\begingroup$ The link above discusses the source and gives a reference. $\endgroup$ Sep 24 '13 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 '13 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 '13 at 0:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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