Linear Extensions of Partial Orders on Finite Sets

Let $X$ be a finite $n$-element set and suppose that both $\leq$ and $\leq_*$ are both partial order relations on $X$. If we have that for all $x, y \in X$ that whenever $x \leq y$ that then $x \leq_* y$ then the partial order $\leq_*$ has the same or more comparable elements. Such a partial order is define below.

Definition: If $X$ is a finite $n$-element set then the partial order $\leq_*$ on $X$ is a Linear Extension of the partial order $\leq$ on $X$ if for all $x, y \in X$ we have that whenever $x \leq y$ that then $x \leq_* y$.

For example, consider the following set:

(1)

\begin{align} \quad X = \{ 1, 3, 9, 27, 30 \} \end{align}

Let $\leq$ be the partial order such that $x \leq y$ means that $x$ divides $y$. If $R$ is the set of ordered pairs $(x, y)$ such that $x \leq y$ then we have that:

(2)

\begin{align} \quad R = \{ (1, 3), (1, 9), (1, 27), (1, 30), (3, 9), (3, 27), (3, 30), (9, 27) \} \end{align}

Let $\leq_*$ be the partial order such that $x \leq_*$ means that the numerical value of $x$ is less than or equal to the numerical value of $y$. Then if $R_*$ is the set of ordered pairs $(x, y)$ such that $x \leq_* y$ then we have that:

(3)

\begin{align} \quad R_* = \{ (1, 3), (1, 9), (1, 27), (1, 30), (3, 9), (3, 27), (3, 30), (9, 27), (9, 30), (27, 30) \} \end{align}

Note that $R \subset R_*$. Furthermore, for all $x, y \in X$ we have that whenever $x \leq y$ that we then also have $x \leq_* y$. Therefore the partial order $\leq_*$ on $X$ is a linear extension of the partial order $\leq$ on $X$.

From the partial orders $\leq$ and $\leq_*$ we see that for all $x, y \in X$ that whenever a number $x$ divides $y$ we have that $x$ is less than or equal to $y$.

We will now look at a very important theorem which tells us that if $X$ is a finite set and $\leq$ is a partial order on $X$ then there exists a linear extension of the partial order $\leq$ on $X$.

Theorem 1 (Linear Extension Theorem): Let $X$ be a finite $n$-element set and let $\leq$ be a partial order on $X$. Then there exists a linear extension of the partial order $\leq$ on $X$.

• Proof: Let $X = \{ x_1, x_2, ..., x_n \}$ be a finite $n$-element set and define $\leq$ as a partial order on $X$. Since $X$ is a finite set there exists an element $x_1 \in X$ such that for all $j \in \{2, 3, ..., n \}$ we have that $x_1 \leq x_j$. Delete the element $x_1$ from $X$. Now since $X \setminus \{ x_1 \}$ is a finite set then there exists an element $x_2 \in X \setminus \{ x_1 \}$ such that for all $j \in \{3, 4, ..., n \}$ we have that $x_2 \leq x_j$. Delete the element $x_2$ from $X \setminus \{ x_1 \}$. We continue in this manner. We will have that $X \setminus \{ x_1, x_2, ..., x_{n-2} \}$ is a finite set and that there exists an element $x_{n-1} \in X \setminus \{ x_1, x_2, ..., x_{n-2} \}$ such that $x_{n-1} \leq x_n$. Delete the element $x_{n-1}$ from $X \setminus \{ x_1, x_2, ..., x_{n-2} \}$.

• Define the partial order (total order) $\leq_*$ by:

(4)

\begin{align} \quad x_1 \leq_* x_2 \leq_* ... \leq_* x_{n-1} \leq x_n \end{align}

• To prove that $\leq_*$ is a linear extension of the partial order $\leq$, suppose that for $i, j \in \{1, 2, ..., n \}$ we have that $j < i$ and $x_i < x_j$. Then this implies that $x_j$ was not a minimal element in $X \setminus \{ x_1, x_2, ..., x_{j-1} \} = \{ x_j, x_{j+1}, ..., x_i, ..., x_n \}$ which is a contradiction. Therefore $\leq_*$. Thus we have that whenever $x_i \not < x_j$ that then $x_i \not <_* x_j$, so $\leq_*$ is a linear extension of the partial order $\leq$. $\blacksquare$