partial ordering, linearization

• Mar 24th 2010, 09:28 AM
poincare4223
partial ordering, linearization
Every partial ordering $\leq$ on a set $P$ has a linearization, i.e., some linear ordering $\leq'$ of $P$ exists such that $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.
• Mar 25th 2010, 06:13 AM
clic-clac
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 $S:=\{(A,\leq^*)\ ;\ A\subseteq P,\ (\leq\cap A^2)\subseteq\leq^*\ \text{and}\ \leq^*\ \text{is a total order on}\ A\}$ ordered by $(A_1,\leq_1^*)R(A_2,\leq_2^*)$ iff $A_1\subseteq A_2$ and $\leq_1^*\subseteq\leq_2^*$
Prove $(S,R)$ is inductive, consider a maximal element $(M,\leq^*)$ and show we must have $M=P$ (for instance by contradiction, assume there is an $x\in P-M$ and extend $\leq^*$ into a total order of $M\cup\{x\}$)