Let $le(X, \preceq)$ denote the number of linear extensions of a partially ordered set $(X, \preceq)$. Prove
- $le(X, \preceq) = 1$ iff $\preceq$ is a linear ordering
- $le(X,\preceq) = n!$ where $n = |x|$
I will use the definition from WolframAlpha:
A linear extension of a partially ordered set P is a permutation of the elements $p_1, p_2, \ldots$ of $P$ such that $p_i <p_j$ implies $i<j$. For example, the linear extensions of the partially ordered set $((1,2),(3,4))$ are $1234$, $1324$, $1342$, $3124$, $3142$, and $3412$, all of which have $1$ before $2$ and $3$ before $4$.
$le(X, \preceq) = 1 \rightarrow \preceq$ is a linear ordering
If there is only a single linear extension, it would mean that all of the elements should belong to a single partial order which would include all of the elements, if there were more, we could get more permutations. Therefore, there must be a linear order.
$\preceq$ is a linear ordering $\rightarrow le(X, \preceq) = 1$
If the elements already are linearly ordered, there is only a single permutation, the identity, which will preserve $p_i < p_j \rightarrow i <j$
- is the first proof correct?
- what does the second statement mean? I think there is a mistake in the textbook that it should be $|X|$ not $|x|$?