1
$\begingroup$

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|$?
$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\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$ – LearnToMath Nov 2 '14 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$ – Brian M. Scott Nov 2 '14 at 19:42
  • $\begingroup$ How would one such permutation look like? Would the condition be $p_i = p_j \rightarrow i=j$ then? $\endgroup$ – LearnToMath Nov 2 '14 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$ – Brian M. Scott Nov 2 '14 at 21:16

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.