Partial order Proof

Question

Suppose that $<$ is a partial order on a set $A$. Prove that there exists a linear order $<'$ on $A$ such that for all $x,y \in A$, if $x < y$ then $x <' y$.

Please someone give me a simple proof.

Answer 1

Morally, what you want to do is just add strong inequalities between elements that are not distinguishable by $<$, and leave everything else as it is.

Formally, things might get a little less pleasant, and some application of the axiom of choice cannot be avoided, I think. You could use Kuratowski-Zorn lemma to mimic an inductive construction. Let $Ord$ be the family of partial orders $<'$ on $A$ that for any $x,y$, if $x < y$ then $x <' y$ (but it might happen that the partial order $<$ does not distinguish $x$ and $y$, i.e. $x \not < y$ and $y \not < x$ --- but $x <' y$). Now, establish order on $Ord$ (yes, it is order on a set orders...) by declaring $<''$ to be larger than $<'$ iff for any $x,y$, from $x <' y$ it follows that $x <'' y$. If you think of orders as sets of pairs, this is just the inclusion order. You can check that the assumptions of Kuratowski-Zorn lemma are satisfied (i.e. each chain has an upper bound), so by the lemma, there exists a largest element, say $<_{max}$. I claim that this maximal element is in fact a total order. For suppose it is not. Then, there are $x$ and $y$ such that $x \not <_{max} y$ and $y \not <_{max} x$. Define an order $<'$ by defining $u <' v$ if and only if either $u <_{max} v$ or $u = x$ and $v = y$. Edit: This is not yet a partial order, but it can be extended to a partial order, which is larger that $<_{max}$ --- a contradiction. So, $<_{max}$ is really a total order, so we are done.

---

Many thanks to Julien for pointing out the gap in the original post. See other answers for more details

Answer 2

Hint: Apply Zorn's Lemma to the partially ordered set of all partial orders on $A$, ordered by declaring $\mathord{\prec}$ to be less than $\mathord{\prec^\prime}$ iff $x \prec y$ implies $x \prec^\prime y$ for all $x , y \in A$. (You will have to show that maximal elements of this partial order are linear orders on $A$.)

Answer 3

Edit: the result you want is known as the order-extension principle. The crux of the argument is to show that a maximal extension of the initial order is a total order. The verifications leading to the application of Zorn are routine.

The set of partial orders on $A$ is partially ordered by: $<$ is not greater than $<'$ if $x<y\Rightarrow x<'y$.

The set of partial orders on $A$ which extend (i.e. are not lower than) $<$ is non-empty, of course. If $(<_i)_i$ is a chain of such partial orders, then define $$ x<'y\qquad\mbox{if}\qquad \exists i\;\;x<_iy. $$ This is an upper bound for the chain, and again an extension of the initial $<$.

By Zorn, there is a maximal such partial order $<_m$. We will show that it is total.

Assume for a contradiction that $x_0\not<_m y_0$ and $y_0\not<_mx_0$. We define a binary relation on $A$ as follows: $$ x R y\qquad\mbox{if}\qquad x<_my\quad\mbox{or}\quad\{x<_mx_0\;\mbox{and}\;y_0<_my\}. $$ It is clearly reflexive. It is also transitive. There are four cases to consider, given $x Ry$ and $yRz$. The last one is not possible by $y_0\not<_mx_0$. By definition, $xRy$ whenever $x<_my$, and $x_0Ry_0$. If $R$ was an order relation (i.e. antisymmetric, which is the only thing we haven't checked), it would be a strict extension of $<_m$, contradicting the maximality of the latter. Therefore, $R$ is not antisymmetric, so there exist $a\neq b$ such that $aRb$ and $bRa$. Again, given the definition of $R$, there are four cases to consider:

1) $a<_mb$ and $b<_ma$: this implies $a=b$ by antisymmetry of $<_m$, impossible.

2) $a<_mb$ and $b<_mx_0$ and $y_0<_ma$: then $y_0<_ma<_mb<_mx_0$ hence $y_0<_mx_0$, impossible.

3) $a<_mx_0$ and $y_0<_mb$ and $b<_ma$: then $y_0<_mb<_ma<_mx_0$ hence $y_0<_mx_0$, impossible.

4) $a<_mx_0$ and $y_0<_mb$ and $b<_mx_0$ and $y_0<_ma$: then $y_0<_ma<_mx_0$ so $y_0<_mx_0$, impossible.

We have reached the desired contradiction, so $<_m$ is a total order on $A$ extending $<$.