Which partial orders can be extended to a copy of $\omega$?

Question

It is a well-known result of ZFC that every partial order $\preccurlyeq$ can be extended to a total one (by adding pairs to $\preccurlyeq$), and similarly, that every well-founded partial order can be extended to a well-order.

I was wondering what conditions are needed on the partial order to guarantee it has a linear extension with order type $\omega$. Among infinite total orders, $\omega$ seems to be unique with the property $$\begin{equation} \text{every element has finitely many others below it}\tag{$*$} \end{equation}$$

In particular, $(*)$ implies well-foundedness, as well as no maximal element (for infinite orders). I'm not sure if this condition has a name, or has been studied before.

Now, is is true that any countably infinite partial order satisfying $(*)$ can be extended to a total order isomorphic to $\omega$? If not, is there another known (necessary and) sufficient condition?

Answer 1

The answer is yes: if $X$ is a countably infinite set and $\trianglelefteq$ is a partial order on $X$ such that $\{y\in X:y\trianglelefteq x\}$ is finite for each $x\in X$, then there is a total ordering $\trianglelefteq'$ on $X$ such that $\trianglelefteq\subseteq\trianglelefteq'$ and $(X,\trianglelefteq')\cong(\omega,<)$.

To see this, let $X,\trianglelefteq$ be as above and fix some enumeration $(x_i)_{i\in\omega}$ of $X$. We recursively build a sequence of elements of $X$ as follows. At stage $s$, having defined $y_t$ for all $t<s$, let $i$ be the least natural number such that $x_i\not\in\{y_t:t<s\}$ but $\{x\in X: x\triangleleft x_i\}\subseteq\{y_t:t<s\}$. We then let $y_s=x_i$.

It's easy to check that $(y_i)_{i\in\omega}$ gives a new enumeration of $X$, the key point being that the finite downward cone condition means that every element of $X$ eventually "becomes available." We now turn this into an ordering of $X$ of ordertype $\omega$ in the obvious way: letting $f:\omega\rightarrow\omega$ be the "reindexing" function $x_i=y_{f(i)}$, we set $$x_i\trianglelefteq'x_j\iff f(i)<f(j).$$

---

More generally, the same argument shows:

Let $\kappa$ be any infinite cardinal, and suppose $(X,\trianglelefteq)$ is a well-founded partial order such that $\vert X\vert=\kappa$ and $\vert\{y\in X: y\trianglelefteq x\}\vert<\kappa$ for each $x\in X$. Then there is a $\trianglelefteq'\subseteq X^2$ such that $\trianglelefteq\subseteq\trianglelefteq'$ and $(X,\trianglelefteq')\cong(\kappa,<)$.