How can I show every uncountable partial order is equal to the intersection of all its linear extensions?

137 Views Asked by At

Given an arbitrary partial order $P=(X,R)$ if for any $a,b\in X$ with $(a,b)\not\in R$ and $(b,a)\not\in R$ we define $R'=R\cup\{x\in X:(x,a)\in R\}\times \{x\in X:(b,x)\in R\}$ then I can show that $P'=(X,R')$ is an order extension of $P$ and by repeating this processes if $X$ is finite, I can then obtain all linear extensions, and show the intersection of them is equal to $P$. However my argument only works for finite partial orders, so with all of that said how can I prove every uncountable partial order is the intersection of all of its linear extenstions?

1

There are 1 best solutions below

1
On BEST ANSWER

"Uncountable" has nothning to do with it; every partial order, whether finite, uncountable, or countably infinite, is the intersection of all its linear intersections.

What you need to show, of course, is that if $a$ and $b$ are two incomparable elements in the poset $P=(X,R)$, then there is a linear order $T$ of $X$ such that $R\subseteq T$ and $(a,b)\in T$ (so that $(b,a)\notin T$). You can do this in two steps.

  1. Construct a partial order $S$ of $X$ such that $R\subseteq S$ and $(a,b)\in S$.

  2. Construct a linear order $T$ of $X$ such that $S\subseteq T$.

For step 1, let $S$ be the transitive closure of $S\cup\{(a,b)\}$ and prove that it's a partial order.

For step 2, if you haven't already proved that every partial order can be extended to a linear order, use Zorn's lemma to show that there is a maximal partial order extending $S$. Then show (as in step 1) that a maximal partial order on a set $X$ must be a linear order.