# Thread: partial ordering, linearization

1. ## partial ordering, linearization

Every partial ordering $\displaystyle \leq$ on a set $\displaystyle P$ has a linearization, i.e., some linear ordering $\displaystyle \leq'$ of $\displaystyle P$ exists such that $\displaystyle x \leq y \Rightarrow x \leq' y$.

This exercise indicates to use the axiom of choice. I do not see how to prove this. I know that a partial ordered set is reflexive, transitive, and antisymmetric. However, I don't see how this has a linearization. I need a few pointers. Thanks.

2. Hi

The form of the problem can suggest the use of Zorn's lemma. Now the point is to find a good set where to apply it, and I suggest you to try to find one before reading what follows!

But here may be a solution (I did not check it properly):
Consider $\displaystyle S:=\{(A,\leq^*)\ ;\ A\subseteq P,\ (\leq\cap A^2)\subseteq\leq^*\ \text{and}\ \leq^*\ \text{is a total order on}\ A\}$ ordered by $\displaystyle (A_1,\leq_1^*)R(A_2,\leq_2^*)$ iff $\displaystyle A_1\subseteq A_2$ and $\displaystyle \leq_1^*\subseteq\leq_2^*$
Prove $\displaystyle (S,R)$ is inductive, consider a maximal element $\displaystyle (M,\leq^*)$ and show we must have $\displaystyle M=P$ (for instance by contradiction, assume there is an $\displaystyle x\in P-M$ and extend $\displaystyle \leq^*$ into a total order of $\displaystyle M\cup\{x\}$)