# Every partial order can be extended to a linear ordering

How do I show that every partial order can be extended to a linear ordering?

I think that I manage to prove that claim for finite set, how can I prove it for infinite set?

Thank you.

You have to use the axiom of choice in the infinite case. And this usage is essential because it is consistent that there are sets which cannot be linearly ordered (in which the case the identity relation cannot be extended to a linear order).

Let $(P,R)$ be a partially ordered set. We define the collection $\{\leq\mid (P,\leq)\text{ is a poset and }R\subseteq\leq\}$, order this by $\subseteq$ and show it satisfies the conditions of Zorn's lemma. The maximal element has to be a linear order.

It should be remarked that simply requiring that every partially ordered set can be extended to a linear order is strictly weaker than the axiom of choice.

Here is a very neat trick using the Compactness Theorem of first-order logic (which is weaker than the axiom of choice). Although you probably didn't cover that in the course, it's a nice trick to know:

Let $(P,\leq)$ be a partially ordered set. Let $\cal L$ be the language with one binary relation $\preceq$ and a constant symbol $c_p$ for every $p\in P$. We write the following $T$:

1. $\preceq$ is a partial order;
2. whenever $p\leq q$ we add the axiom $c_p\preceq c_q$;
3. for every pair $p,q\in P$ we add the axiom $c_p\preceq c_q\lor c_q\preceq c_p$.

Now we will show that $T$ is finitely-satisfiable. If $S\subseteq T$ has only axioms of the form $1$ or from the schema described in $2$ then $(P,\leq)$ is a model for $S$. Otherwise it has a finite number of axioms from the schema in $3$. We can extend $\leq$ to some $\leq^\ast$ which satisfy these axioms.

We do this by induction: if there is only one axiom and it hasn't been satisfied then $p$ and $q$ are incomparable, and we can take $\leq^\ast=\leq\cup\{\langle p,q'\rangle\mid q\leq q'\}$.

Suppose we did this for $k$ axioms; simply repeat the argument for the $k+1$. This requires no axiom of choice because we only have to make finitely many choices.

(Alternatively one can replace schema $3$ by the axiom $3'$, $\forall x\forall y(x\preceq y\lor y\preceq x)$, now notice that any finite fragment talks only about finitely many constants, $c_{p_1},\ldots,c_{p_k}$. Restricting $\leq$ to $\{p_1,\ldots,p_k\}$ is a finite partially ordered set, and can be extended to a linear ordering which satisfies $3'$ as wanted.)

Therefore every finite fragment of $T$ has a model, and so by the compactness theorem $T$ itself has a model $(P',\leq')$. We define $\preceq$ on $P$ as follows: $p\preceq q\iff (P',\leq')\models c_p\preceq c_q$. The schema $2$ ensures this extends $\leq$, and schema $3$ (or axiom $3'$) ensures this is a linear ordering.

• I think that as an extension of $\leq$ we should take $\mathord{\leq^\ast}=\mathord{\leq}\cup\{\langle p,q'\rangle\mid q\leq q'\}\cup\{\langle p',q\rangle\mid p'\leq p\}$ to guarantee transitivity of $\leq^\ast$. Aug 20, 2020 at 11:54
• Yes, you're right. Aug 20, 2020 at 12:05
• When we have that p and q are incomparable what is the set $\leq^\ast=\leq\cup\{\langle p,q'\rangle\mid p\leq q'\}\cup\{\langle p',q\rangle\mid p'\leq q\}$. Does $\{\langle p,q'\rangle\mid p\leq q'\}$ represent all the elements less than or equal to $q$ ? Wouldn't we just have to append the tuple $(p, q)$ to the relation to fix it? Oct 27, 2021 at 21:55
• @cuppajoeman: Not necessarily. Consider the order which is two disjoint chains, each with three elements. Now say that $p$ and $q$ are the two middle ones. Say $p$ will be less than $q$. But we need to also add the minimal below $p$ to be less than $q$, and likewise the maximal above $q$ to be above $p$. Oct 27, 2021 at 21:59
• @cuppajoeman: That depends on how you write it out exactly. But yes, of course you need it in $\leq^*$. Oct 28, 2021 at 0:32

You will have to use the axiom of choice (or one of its consequences) in some form. One possibility is to use Zorn’s lemma. Let $$\langle P,\le\rangle$$ be a partial order. Let $$\mathscr{L}=\big\{\langle X,\preceq_X\rangle:X\subseteq P\text{ and }\preceq_X\text{ is a linear order on }X\\\text{ extending }\le\upharpoonright(X\times X)\}\;.$$

For $$\langle X,\preceq_X\rangle,\langle Y,\preceq_Y\rangle\in\mathscr{L}$$ define $$\langle X,\preceq_X\rangle\sqsubseteq\langle Y,\preceq_Y\rangle$$ iff $$X\subseteq Y$$ and $$\preceq_Y\upharpoonright(X\times X)=\preceq_X$$; clearly $$\langle\mathscr{L},\sqsubseteq\rangle$$ is a partial order. Let $$\mathscr{C}$$ be a chain in $$\langle\mathscr{L},\sqsubseteq\rangle$$.

• Show that $$\mathscr{C}$$ has an upper bound in $$\langle\mathscr{L},\sqsubseteq\rangle$$; the most obvious choice works.

• Use Zorn’s lemma to conclude that $$\langle\mathscr{L},\sqsubseteq\rangle$$ has a maximal element $$\langle M,\preceq_M\rangle$$.

• Show that $$M=P$$.

Added: However, it’s not necessary to use the full axiom of choice: the result follows, for instance, from the Boolean prime ideal theorem, which is strictly weaker than AC. For example, one of the equivalents of the BPI is the compactness theorem for first-order logic, which can be used to give a very simple proof. Let $$R$$ be a binary relation symbol, and for each $$p\in P$$ let $$c_p$$ be a constant symbol. Let $$\Phi$$ be the set of all sentences $$R(c_p,c_q)$$ such that $$p,q\in P$$ and $$p\le q$$, together with axioms making $$R$$ a linear order. Then $$\Phi$$ is finitely satisfiable, so by the compactness theorem $$\Phi$$ has a model. That model yields a linear extension of $$\le$$.

Added2: Okay, I like ultrafilters. For $$F\in[P]^{<\omega}$$ let $$U_F=\big\{G\in[P]^{<\omega}:F\subseteq G\big\}$$; clearly $$\big\{U_F:F\in[P]^{<\omega}\big\}$$ is centred (= has the finite intersection property), so it can be extended to an ultrafilter $$\mathscr{U}$$ on $$[P]^{<\omega}$$. This requires the ultrafilter extension theorem, which is equivalent to the BPI, but the next step uses AC itself: for each finite $$F\subseteq P$$ let $$\preceq_F$$ be a linear order on $$F$$ that extends $$\le\upharpoonright\!\!(F\times F)$$, let $$\le_F\,=\,\le\cup\preceq_F$$, and denote by $$P_F$$ the partial order $$\langle P,\le_F\rangle$$.

For $$p,q\in P$$ write $$p\preceq q$$ iff $$\big\{F\in[P]^{<\omega}:p\le_F q\big\}\in\mathscr{U}$$. If $$p\le q$$, then $$p\le_F q$$ for all $$F\in[P]^{<\omega}$$, so $$p\preceq q$$. Now let $$p,q\in P$$ with $$p\ne q$$. Then exactly one of the sets $$\big\{G\in U_{\{p,q\}}:p\le_G q\big\}$$ and $$\big\{G\in U_{\{p,q\}}:q\le_G p\big\}$$ belongs to $$\mathscr{U}$$, so exactly one of $$p\preceq q$$ and $$q\preceq p$$ holds. Finally, if $$p,q,r\in P$$ with $$p\preceq q\preceq r$$, then

$$\big\{G\in U_{\{p,q,r\}}:p\le_G r\big\}\supseteq\\\big\{G\in U_{\{p,q,r\}}:p\le_G q\big\}\cap\big\{G\in U_{\{p,q,r\}}:q\le_G r\big\}\in\mathscr{U}\;,$$

so $$p\preceq r$$. Thus, $$\preceq$$ is a linear order on $$P$$ extending $$\le$$.

• The last part is not necessarily true, you can write one axiom asserting that $R$ is a linear order. In order to use the compactness theorem you should add a schema writing explicitly for every pair of elements that they are comparable. Jan 5, 2013 at 16:14
• @Asaf: That’s part of the axiom making $R$ a linear order. (Or wasn’t it clear that I meant a linear order of the ‘universe’?) Jan 5, 2013 at 16:23
• $\forall x\forall y(x\mathrel{R}y\lor y\mathrel{R}x)$ is just one axiom. How can you show that the theory $T$ is finitely satisfiable if your original partial order is not linear? Jan 5, 2013 at 16:25
• (By the way, I found a very recent paper with an incredibly nice proof: well-order $P$, then embed $\leq$ in the usual way to the power set with inclusion, then show that the embedding respects the lexicographic ordering given from the well-order. Very nice.) Dec 12, 2020 at 19:34
• @Atom: No, it’s the restriction of $\le$ to $X\times X$. Jan 21 at 7:35