Given a partial order $R$ on the set $A$, prove that there exists a total order $\leq$ on $A$ such that $R \subseteq {\le}$

Question

Let $A$ be a finite set, and $\langle A,R\rangle $ be partially ordered.

$\textbf{Prove}$ that there exists a total order $\leq$ over $A$ such that $R \subseteq {\le}$.

$\textbf{My Attempt:}$ Define $B \subseteq \mathbb{N}$ by $B = \{ k \in \mathbb{N}\mid$ there is a partial order $S$ on $A$ such that $ R \subseteq S$ and $|S| = k \}$.

Now, I tried to prove that $B \neq \emptyset$ and Bounded. I thought about using the maximum principle (the opposite of the Well-ordering principle).

Answer 1

I can’t follow your description of what you’re trying to do, I’m afraid. One straightforward approach is to prove the result by induction on $|A|$. If you know the result for sets of cardinality $n$, and $|A|=n+1$, fix $a_0\in A$, extend the restriction of $R$ to $A\setminus\{a_0\}$ to a linear order on $A\setminus\{a_0\}$, and then show that it’s always possible to insert $a_0$ into this linear order to get a linear extension of $R$.

Added: In more detail, $P(n)$ is the statement that if $\langle A,R\rangle$ is a partial order, and $|A|=n$, then there is a linear order $L$ on $A$ such that $R\subseteq L$. This is trivial for $n=1$. The induction argument is to assume that $P(n)$ is true and show that $P(n+1)$ is true. To do this, start with a partial order $\langle A,R\rangle$ such that $|A|=n+1$. Pick any $a_0\in A$, let $A_0=A\setminus\{a_0\}$, and let $R_0=R\cap(A_0\times A_0)$. Then $\langle A_0,R_0\rangle$ is a partial order, and $|A_0|=n$, so by the induction hypothesis there is a linear order $L_0$ on $A_0$ such that $R_0\subseteq L_0$. Now show that it is possible to insert $a_0$ into the linear order $L_0$ to get a linear order $L$ of all of $A$ such that $R\subseteq L$.

Answer 2

Suppose $x_0,y_0$ are not comparable. Let $X=\{x\in A:xRx_0\}$ and $Y=\{x\in A:y_0Rx\}$. Let $\le$ be the result of adding to the partial order $R$ all pairs $(x,y)$ where $x\in X,y\in Y$. We claim that $\le$ is also a partial order.

Note that $X\cap Y=\emptyset$, for if $x\in X\cap Y$, then $xRx_0$ and $y_0Rx$, so by transitivity $y_0Rx_0$, contradicting the fact that $y_0,x_0$ are not comparable. Moreover, if $x\in X,y\in Y$ we cannot have $yRx$ for then $y_0RyRxRx_0$, so $y_0Rx_0$, again contradicting the fact that $x_0,y_0$ are not comparable.

$\le$ is obviously reflexive. Suppose $x\le y\le x$. If $x\ne y$, then we must have $x\in X,y\in Y$ (or we would not have $x\le y$). So we must have $x\notin Y$, so $y\le x$ implies $yRx$. But $xRx_0$, so by transitivity of $R$ we have $yRx_0$ and hence $y\in X$. Contradiction. So $xRy$. Similarly, we get $yRx$, so $x=y$. Hence $\le$ is also antisymmetric.

Finally, suppose $x\le y\le z$. There are three cases:

(1) $xRy$ is false. So $x\in X,y\in Y$. Then $y\notin X$, so $y\le z$ implies $yRz$. But $y\in Y$, so $z\in Y$. But $z\in X,z\in Y$ implies $x\le z$.

(2) $xRyRz$. Then $xRz$ and so $x\le z$.

(3) $xRy$ and $y\in X,z\in Y$. But $xRy,y\in X$ implies $x\in X$. Now $x\in X,z\in Y$ implies $x\le z$.

So $\le$ is partial order. But $A$ is finite, so there are only finitely many pairs of elements. Hence repeating this process a finite number of times we get a total order which extends $R$.