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.

  • 1
    $\begingroup$ 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$. $\endgroup$ – Mad Hatter Aug 20 '20 at 11:54
  • $\begingroup$ Yes, you're right. $\endgroup$ – Asaf Karagila Aug 20 '20 at 12:05

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.) 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$.

  • $\begingroup$ 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. $\endgroup$ – Asaf Karagila Jan 5 '13 at 16:14
  • $\begingroup$ @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’?) $\endgroup$ – Brian M. Scott Jan 5 '13 at 16:23
  • $\begingroup$ $\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? $\endgroup$ – Asaf Karagila Jan 5 '13 at 16:25
  • $\begingroup$ @Asaf: That part’s trivial, since we already know that finite partial orders can be extended to linear orders. $\endgroup$ – Brian M. Scott Jan 5 '13 at 16:27
  • 1
    $\begingroup$ (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.) $\endgroup$ – Asaf Karagila Dec 12 '20 at 19:34

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.