Total Orders from Permutations of a Set

Recall from the Total Orders on Sets page that if $X$ is a set and $R$ is a relation on $X$ then $R$ is said to be a total order on $X$ if for every pair of elements $x, y \in X$ we have that $x$ and $y$ are comparable, that is $x \: R \: y$ or $y \: R \: x$.

Now consider a finite $n$-element set $X$ with the relation $<$. As we have already seen, there exists exactly $n!$ many $n$-permutations $(x_1, x_2, ..., x_n)$ of elements in $X$. Suppose that we have the relation $\leq$ where for $i, j \in \{ 1, 2, ..., n \}$ and $i \neq j$ we have that $x_i < x_j$, or more generally since the elements $x_1, x_2, ..., x_n \in X$ are distinct:

(1)

\begin{align} \quad x_1 < x_2 < ... < x_n \end{align}

Then $\leq$ is actually a total order on $X$. To show this, we will first demonstrate that $\leq$ is reflexive, antisymmetric, and transitive. For all $i \in \{1, 2, ..., n \}$ we clearly have that $x_i \leq x_i$ so $\leq$ is reflexive. Furthermore, for all $i, j \in \{1, 2, ..., n \}$ where $i \neq j$ we have that $x_i < x_j$ (if $i < j$) and $x_j < x_i$ (if $j < i$) so $\leq$ is antisymmetric. Lastly, let $i, j, k \in \{1, 2, ..., n \}$. Suppose that $x_i < x_j$ and $x_j < x_k$. Then this implies that $i < j < k$ so $i < k$ and $x_i < x_j$, so $\leq$ is transitive.

Furthermore, for each element $x_i, x_j \in X$ we have $x_i \leq x_j$ or $x_j \leq x_i$, so $\leq$ is a total order on $X$.

In the following theorem we will see that every total order $\leq$ arises from a permutation of elements from $X$.

Theorem 1: If $X$ is a finite $n$-element set then the number of distinct total orders on $X$ is $n!$.

• Proof: Let $X$ be a finite $n$-element set. If $n = 1$ then the set $X$ contains only $1$ element and any relation is trivially a total order on $X$. Assume that $n > 1$ and that $X = \{ x_1, x_2, ..., x_n \}$. Suppose that $x \in X$. Since $\leq$ is a total order on $X$ we have that for $y \in X$ where $x \neq y$ that then $x < y$ or $y < x$. If $x < y$ for all $y \in X$ then we will define $x$ to be the minimum element in $X$. If $x \neq y$ for all $y \in X$ then there exists a $y \in X$ such that $y < x$. We continue in this process until we obtain this minimal element.

• Without loss of generality, say that $x_1$ is this minimal element. We then take the set $X \setminus \{ x_1 \}$ and use the reasoning above to find a minimal element $x_2$ of this set. We repeat this process and get:

(2)

\begin{align} \quad x_1 < x_2 < ... < x_n \end{align}

• Notice that the total ordering above is simply a permutation $(x_1, x_2, ..., x_n)$ of the $n$ elements in $X$. We know that there are $n!$-permutations of elements in an $n$-element set. Therefore the number of distinct total orders on $X$ is $n!$. $\blacksquare$

In Theorem 1 above, the first half of the proof shows that such total orders must be of the form $x_1 < x_2 < ... < x_n$ while the second half of the proof shows that there are $n!$ total orders.