I cannot understand the statement "every partial order is the intersection of its linear extensions. (See e.g. Davey and Priestley [DP]" here (page 6). The book Introduction to Lattices and Order on page 32 assumes that $P$ is finite, not infinite. So suppose that the poset $P$ is infinite.

Is the intersection of linear extensions now the infinite $P$?

  • $\begingroup$ Sorry, my bad... $\endgroup$ – Asaf Karagila Mar 13 '16 at 17:26

This result relies on Szpilrajn extension theorem: any partial order has a linear extension. Let $\leqslant$ be the partial order on $P$. I claim that ${\leqslant}$ is equal to the intersection $\preccurlyeq$ of all linear extensions of $\leqslant$.

For each pair $(a,b)$ of incomparable elements of $P$, define a new relation $\leqslant_{a,b}$ has follows: $$r \leqslant_{a,b} s\ \text{ if } \begin{cases} r \leqslant s\\ \text{ or}\\ \text{$r \leqslant a$ and $b \leqslant s$} \end{cases} $$ I let you verify that $\leqslant_{a,b}$ is also a partial order.

Let $(a,b) \in P^2$. Then $a \leqslant b$ implies $a \preccurlyeq b$ by construction. Suppose now that $a \preccurlyeq b$ but $a \not\leqslant b$. If $b \leqslant a$, then $b \preccurlyeq a$ and thus $a = b$. If $a$ and $b$ are incomparable for $\leqslant$, then $\leqslant_{b,a}$ is a preorder, which admits a linear extension $\leqslant^*_{b,a}$. Since $a \preccurlyeq b$, one gets $a \leqslant^*_{a,b} b$. But since $b \leqslant_{b,a} a$, one also gets $b \leqslant^*_{b,a} a$. Thus $a = b$, a contradiction.


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.