Number of linear extensions

Question

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|$?

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.