Let $le(X, \preceq)$ denote the number of linear extensions of a partially ordered set $(X, \preceq)$. Prove

  1. $le(X, \preceq) = 1$ iff $\preceq$ is a linear ordering
  2. $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$

  1. is the first proof correct?
  2. what does the second statement mean? I think there is a mistake in the textbook that it should be $|X|$ not $|x|$?

1 Answer 1


Your argument that if $\preceq$ is a linear order, then $le(X,\preceq)=1$ is correct; your argument in the other direction, however, is vague hand-waving, though it contains the germ of a good idea. Specifically, you should actually prove that if $\preceq$ is not a linear order, then $le(X,\preceq)>1$.

If $\preceq$ is not a linear order, then there are $x,y\in X$ such that $x\npreceq y$ and $y\npreceq x$. I'm assuming that you’ve already proved that every partial order has at least one linear extension, so let $\pi$ be a linear extension of $\preceq$. Without loss of generality assume that $x$ precedes $y$ in $\pi$. (There may of course be elements of $X$ between $x$ and $y$ in $\pi$.) Now prove that if you interchange $x$ and $y$ in $\pi$, the resulting permutation is still a linear extension of $\preceq$; this clearly implies that $le(X,\preceq)\ge 2$.

In the second statement $n$ should indeed be $|X|$, not $|x|$. Moreover, the relation should be equality, not some unspecified $\preceq$. In other words, you’re to prove that $le(X,=)=|X|!$ if $X$ is a finite set.

  • $\begingroup$ Your input is helpful as always. Thank you. However, I still cannot understand the second problem. In the Wolfram Alpha example, the total size (cardinality) of the set is P is 4. However, WA lists only 6 permutations. According to this definition shouldn't there be 4! linear extensions? $\endgroup$ Nov 2, 2014 at 19:36
  • $\begingroup$ @LearnToMath: The WA example deals with a particular relation on $P$, and that relation isn’t equality. The relation of equality on $P$ is $$\{\langle 1,1\rangle,\langle 2,2\rangle,\langle 3,3\rangle,\langle 4,4\rangle\}\;,$$ which does have $4!=24$ linear extensions: every permutation of $P$ extends the relation. $\endgroup$ Nov 2, 2014 at 19:42
  • $\begingroup$ How would one such permutation look like? Would the condition be $p_i = p_j \rightarrow i=j$ then? $\endgroup$ Nov 2, 2014 at 21:02
  • $\begingroup$ @LearnToMath: Technically it would be $p_i=p_j\to i\le j$, but it’s automatically true that $p_i=p_j\leftrightarrow i=j$ anyway. The point is that the partial order equality doesn’t actually impose any order conditions on the permutation, so every possible permutation extends it. $\endgroup$ Nov 2, 2014 at 21:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .