Can a well-founded partial order always be extended to a well-founded total order

Question

A partial order can always be extended to a total order (order-extension theorem, follows from axiom of choice). Furthermore any set has a well-founded order (well-ordering theorem, also follows from AC). But is it true that any well-founded partial order can be extended to a well-founded total order?

Answer 1

Every well-founded partial order can indeed be extended to a well-founded total order (= a well-order). This is one of many variants of Szpilrajn's theorem. In general, say that a linear order $L$ is extendible (or enforceable, sometimes) iff whenever $P$ is a partial order not containing a copy of $L$, $P$ has a linearization which also doesn't contain a copy of $L$. So the result above says that $\omega^*$ is extendible, since the ill-founded partial orders are exactly those not containing a copy of $\omega^*$.

(Yes, that terminology is horrible. C'est la vie.)

The extendibility of $\omega^*$ is stated without attribution in the introduction to this paper by Downey/Hirschfeldt/Lempp/Solomon (page $5$); I suspect it is folklore.

Answer 2

This is indeed possible using an argument that is inspired by topological sorting.

Let $(A, R)$ be a well-founded poset, and take a choice function $f : \{U \subseteq A | U \neq \emptyset\} \to A$ such that $f(U)$ is an $R$-minimal element of $U$ for all $U$ in the domain.

Designate a special value $UNDEF \notin A$ (perhaps pick the canonical $UNDEF = \{a \in A | a \notin a\}$).

Now define by ordinal induction, for every ordinal $\alpha$, $g(\alpha) = UNDEF$ if $A \subseteq \{g(\beta) | \beta < \alpha\}$, otherwise $g(\alpha) = f(A \setminus \{g(\beta) | \beta < \alpha\}$.

Note that for all $\alpha$, $g(\alpha) \in A \cup \{UNDEF\}$.

Suppose there is no $\alpha$ such that $g(\alpha) = UNDEF$. Then note that if $\beta < \alpha$ we have $g(\alpha) = f(A \setminus \{g(\beta) | \beta < \alpha\}) \in A \setminus \{g(\beta) | \beta < \alpha\}$, and so $g(\alpha) \neq g(\beta)$. Then $g$ is a 1-1 function from the class of ordinals to $A$, which is impossible since it implies the class of ordinals is a set.

Now let $\kappa$ be the smallest ordinal such that $g(\kappa) = UNDEF$. Then consider $g : \kappa \to A$. We see that by the above argument, $g$ is a 1-1 function. And we know that $g$ is surjective because $g(\kappa) = UNDEF$ and therefore $A \subseteq \{g(x) | x \in \kappa\}$. So $g : \kappa \to A$ is a bijection.

Now, suppose we have $g(\alpha) R g(\beta)$. Then $g(\alpha) \neq g(\beta)$, and hence $\alpha \neq \beta$ since $g$ is a function. Suppose that $\beta < \alpha$. Then in that case, we would have $g(\beta) = f(A \setminus \{g(\gamma) | \gamma < \beta\})$. And we would have $g(\alpha) \in A \setminus \{g(\gamma) | \gamma < \beta\}$. Thus, by $R$-minimality, we cannot have $g(\alpha) R g(\beta)$: contradiction. Then it must be the case that $\alpha < \beta$.

Finally, define $R'$ by $R' = \{(g(\alpha), g(\beta)) | \alpha < \beta\} \subseteq A^2$. In other words, define $R'$ such that $g : \kappa \to A$ is an order-isomorphism. Then $R'$ is a well-order which is an extension of $R$.

Answer 3

Let $\operatorname{rk}_{\le} : P \to Ord$ be the rank function (which requires $\le$ to be well-founded in order to have ordinal values). Also, use the well-ordering principle to find a well-ordering $\le'$ on $P$ (which does not necessarily extend $\le$). Then we can define a well-ordering $\le''$ on $P$ which extends $\le$, as the inverse image of the lexicographic product of $\le_{Ord}$ and $\le'$ under the map $(P, \le) \to Ord \times (P, \le'), p \mapsto (\operatorname{rk}_{\le}(p), p)$. In other words: $$x \le'' y \Leftrightarrow \operatorname{rk}_{\le}(x) < \operatorname{rk}_{\le}(y) \lor (\operatorname{rk}_{\le}(x) = \operatorname{rk}_{\le}(y) \land x \le' y).$$