Every partial order can be extended to a linear ordering

Solution 1:

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.

Solution 2:

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

Added₂: 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$.