Partial Orders and Strict Partial Orders
Let \(R\) be a binary relation on a set \(A\). Thus, \[
R\subset A\times A
\]and, for arbitrary \(x,y\in A\), we define \[
R\left( x,y\right) \Leftrightarrow\left( x,y\right) \in R.
\]Note that
\[
\lnot R\left( x,y\right) \Leftrightarrow\left( x,y\right) \not \in R
\]also holds.
A binary relation \(R\) on \(A\) is a partial order if it satisfies reflexivity, antisymmetry, and transitivity. In other words, \(R\) is a partial order if the following three conditions hold: \begin{align*}
& \left( O_{1}\right) \ \forall x\in A:R\left( x,x\right) \\
& \left( O_{2}\right) \ \forall x,y\in A:\left[ \left( R\left(
x,y\right) \wedge R\left( y,x\right) \right) \Rightarrow x=y\right] \\
& \left( O_{3}\right) \ \forall x,y,z\in A:\left[ \left( R\left(
x,y\right) \wedge R\left( y,z\right) \right) \Rightarrow R\left(
x,z\right) \right] .
\end{align*}The symbol \(\leq\) is often used for a partial order. Thus, when a partial order \(R\) on \(A\) is given, we define, for arbitrary \(x,y\in A\), \[
x\leq y\Leftrightarrow R\left( x,y\right) .
\]In this case,
\[
\lnot\left( x\leq y\right) \Leftrightarrow\lnot R\left( x,y\right)
\]also holds. Using \(\leq\), the three axioms can be written as \begin{align*}
& \left( O_{1}\right) \ \forall x\in A:x\leq x\\
& \left( O_{2}\right) \ \forall x,y\in A:\left[ \left( x\leq y\wedge y\leq x\right) \Rightarrow x=y\right] \\
& \left( O_{3}\right) \ \forall x,y,z\in A:\left[ \left( x\leq y\wedge y\leq z\right) \Rightarrow x\leq z\right] .
\end{align*}
By contrast, a binary relation \(R\) on \(A\) is a strict partial order if it satisfies asymmetry and transitivity. In other words, \(R\) is a strict partial order if \begin{align*}
& \left( S_{1}\right) \ \forall x,y\in A:\left[ R\left( x,y\right)
\Rightarrow\lnot R\left( y,x\right) \right] \\
& \left( S_{2}\right) \ \forall x,y,z\in A:\left[ \left( R\left(
x,y\right) \wedge R\left( y,z\right) \right) \Rightarrow R\left(
x,z\right) \right]
\end{align*}hold. The symbol \(<\) is often used for a strict partial order. Thus, when a strict partial order \(R\) on \(A\) is given, we define \[
x<y\Leftrightarrow R\left( x,y\right) .
\]Then
\[
\lnot\left( x<y\right) \Leftrightarrow\lnot R\left( x,y\right)
\]also holds. Using \(<\), asymmetry and transitivity are written as \begin{align*}
& \left( S_{1}\right) \ \forall x,y\in A:\left[ x<y\Rightarrow\lnot\left(
y<x\right) \right] \\
& \left( S_{2}\right) \ \forall x,y,z\in A:\left[ \left( x<y\wedge y<z\right) \Rightarrow x<z\right] .
\end{align*}
Partial orders and strict partial orders are closely related. Given a partial order on \(A\), we can construct a strict partial order on \(A\). Conversely, given a strict partial order on \(A\), we can construct a partial order on \(A\). We discuss these constructions in turn.
A Strict Partial Order Generated from a Partial Order
Let \(\leq\) be a partial order on \(A\). Thus, \begin{align*}
& \left( O_{1}\right) \ \forall x\in A:x\leq x\\
& \left( O_{2}\right) \ \forall x,y\in A:\left[ \left( x\leq y\wedge y\leq x\right) \Rightarrow x=y\right] \\
& \left( O_{3}\right) \ \forall x,y,z\in A:\left[ \left( x\leq y\wedge y\leq z\right) \Rightarrow x\leq z\right] .
\end{align*}For arbitrary \(x,y\in A\), define a new binary relation \(R\) on \(A\) by \begin{equation}
R\left( x,y\right) \Leftrightarrow\left( x\leq y\wedge x\not =y\right)
.\quad \cdots (1)\end{equation}Thus, \(R\left( x,y\right) \) holds exactly when both \(x\leq y\) and \(x\not =y\) hold. We also have
\begin{align*}
\lnot R\left( x,y\right) & \Leftrightarrow\lnot\left( x\leq y\wedge x\not =y\right) \quad\because\left( 1\right) \\
& \Leftrightarrow\lnot\left( x\leq y\right) \vee\lnot\left( x\not =y\right) \quad\because\text{De Morgan’s law}\\
& \Leftrightarrow\lnot\left( x\leq y\right) \vee x=y.
\end{align*}Hence
\[
\lnot R\left( x,y\right) \Leftrightarrow\lnot\left( x\leq y\right) \vee x=y.
\]
The relation \(R\) defined from \(\leq\) in this way is guaranteed to be a strict partial order on \(A\).
R\left( x,y\right) \Leftrightarrow\left( x\leq y\wedge x\not =y\right) .
\]Then \(R\) is a strict partial order. That is, \begin{align*}
& \left( S_{1}\right) \ \forall x,y\in A:\left[ R\left( x,y\right)
\Rightarrow\lnot R\left( y,x\right) \right] \\
& \left( S_{2}\right) \ \forall x,y,z\in A:\left[ \left( R\left(
x,y\right) \wedge R\left( y,z\right) \right) \Rightarrow R\left(
x,z\right) \right] \end{align*}hold. In addition, for arbitrary \(x,y\in A\), \[
x\leq y\Leftrightarrow\left( R\left( x,y\right) \vee x=y\right) .
\]
x<y\Leftrightarrow\left( x\leq y\wedge x\not =y\right) .
\]Thus \(x<y\) holds if and only if both \(x\leq y\) and \(x\not =y\) hold. Since \(\leq\) is a partial order on \(\mathbb{R} \), the preceding proposition implies that \(<\) is a strict partial order on \(\mathbb{R} \).
A\varsubsetneq B\Leftrightarrow\left( A\subset B\wedge A\not =B\right) .
\]Since \(\subset\) is a partial order on \(2^{U}\), the preceding proposition implies that \(\varsubsetneq\) is a strict partial order on \(2^{U}\).
A Partial Order Generated from a Strict Partial Order
We have shown how to construct a strict partial order from a partial order. Conversely, a partial order can be constructed from a strict partial order.
Let \(<\) be a strict partial order on \(A\). Thus, \begin{align*}
& \left( S_{1}\right) \ \forall x,y\in A:\left[ x<y\Rightarrow\lnot\left(
y<x\right) \right] \\
& \left( S_{2}\right) \ \forall x,y,z\in A:\left[ \left( x<y\wedge y<z\right) \Rightarrow x<z\right] .
\end{align*}For arbitrary \(x,y\in A\), define a new binary relation \(R\) by \begin{equation}
R\left( x,y\right) \Leftrightarrow\left( x<y\vee x=y\right) .\quad \cdots (1)\end{equation}Then
\begin{align*}
\lnot R\left( x,y\right) & \Leftrightarrow\lnot\left( x<y\vee x=y\right)
\quad\because\left( 1\right) \\
& \Leftrightarrow\lnot\left( x<y\right) \wedge\lnot\left( x=y\right)
\quad\because\text{De Morgan’s law}\\
& \Leftrightarrow\lnot\left( x<y\right) \wedge x\not =y.
\end{align*}
The relation \(R\) defined in this way is guaranteed to be a partial order on \(A\).
R\left( x,y\right) \Leftrightarrow\left( x<y\vee x=y\right) .
\]Then \(R\) is a partial order. That is, \begin{align*}
& \left( O_{1}\right) \ \forall x\in A:R\left( x,x\right) \\
& \left( O_{2}\right) \ \forall x,y\in A:\left[ \left( R\left(
x,y\right) \wedge R\left( y,x\right) \right) \Rightarrow x=y\right] \\
& \left( O_{3}\right) \ \forall x,y,z\in A:\left[ \left( R\left(
x,y\right) \wedge R\left( y,z\right) \right) \Rightarrow R\left(
x,z\right) \right] \end{align*}hold. In addition,
\[
x<y\Leftrightarrow\left( R\left( x,y\right) \wedge x\not =y\right)
\]for arbitrary \(x,y\in A\).
x\leq y\Leftrightarrow\left( x<y\vee x=y\right) .
\]Since \(<\) is a strict partial order on \(\mathbb{R} \), the preceding proposition implies that \(\leq\) is a partial order on \(\mathbb{R} \).
A\subset B\Leftrightarrow\left( A\varsubsetneq B\vee A=B\right) .
\]Since \(\varsubsetneq\) is a strict partial order on \(2^{U}\), the preceding proposition implies that \(\subset\) is a partial order on \(2^{U}\).
Relationship Between Partial Orders and Strict Partial Orders
We have shown that a strict partial order can be constructed from a partial order and, conversely, that a partial order can be constructed from a strict partial order. Thus either relation may be taken as primitive. A common approach is to define a partial order \(\leq\) first and then define the associated strict partial order \(<\) by \[
x<y\Leftrightarrow\left( x\leq y\wedge x\not =y\right) .
\]As shown above,
\[
x\leq y\Leftrightarrow\left( x<y\vee x=y\right)
\]then also holds.
x<y\Leftrightarrow\left( x\leq y\wedge x\not =y\right) .
\]Then \(<\) is a strict partial order. For arbitrary \(x,y\in A\), the following truth table applies, where \(1\) denotes true and \(0\) denotes false: $$\begin{array}{cccccc}\hline \quad & x\leq y & y\leq x & x=y & x<y & y<x\\\hline \left( a\right) & 1 & 1 & 1 & 0 & 0\\\hline \left( b\right) & 1 & 0 & 0 & 1 & 0\\\hline \left( c\right) & 0 & 1 & 0 & 0 & 1\\\hline \left( d\right) & 0 & 0 & 0 & 0 & 0\\\hline \end{array}$$
For arbitrary \(x,y\in A\), the four cases in the table exhaust the logically possible combinations of truth values for \(x\leq y\) and \(y\leq x\). Case \(\left( a\right) \) corresponds to \(x=y\), case \(\left( b\right) \) to \(x<y\), and case \(\left( c\right) \) to \(y<x\). In case \(\left( d\right) \), neither relation holds, so \(x\) and \(y\) are incomparable.
Transitivity Relations Between Partial and Strict Partial Orders
Partial orders and strict partial orders each satisfy transitivity. In addition, the following mixed transitivity properties hold.
x<y\Leftrightarrow\left( x\leq y\wedge x\not =y\right) .
\]Then
\begin{align*}
& \left( a\right) \ \forall x,y,z\in A:\left[ \left( x\leq y\wedge y<z\right) \Rightarrow x<z\right] \\
& \left( b\right) \ \forall x,y,z\in A:\left[ \left( x<y\wedge y\leq z\right) \Rightarrow x<z\right] \end{align*}hold.
Exercises
x<y\Leftrightarrow\left( x\leq y\wedge x\not =y\right) .
\]Show that
\[
x<y\Rightarrow x\leq y
\]and
\[
x<y\Rightarrow\lnot\left( y<x\right) .
\]
x\leq y\Leftrightarrow\left( x<y\vee x=y\right) .
\]Show that \(\leq\) satisfies reflexivity and antisymmetry.
x<y\Leftrightarrow\left( x\leq y\wedge x\not =y\right) .
\]Show that
\begin{align*}
& \left( a\right) \ x\leq y\wedge y<z\Rightarrow x<z\\
& \left( b\right) \ x<y\wedge y\leq z\Rightarrow x<z.
\end{align*}
x<y\Leftrightarrow\left( x\leq y\wedge x\not =y\right) \quad \cdots (1)\end{equation}and then define
\begin{equation}
x\preceq y\Leftrightarrow\left( x<y\vee x=y\right) .\quad \cdots (2)\end{equation}Show that
\[
x\preceq y\Leftrightarrow x\leq y
\]for arbitrary \(x,y\in A\).
x<y\Leftrightarrow\left( x\leq y\wedge x\not =y\right) .
\]Show that, for arbitrary \(x,y\in A\), \[
x\leq y\vee y\leq x\Leftrightarrow x<y\vee x=y\vee y<x.
\]
x\leq y\Leftrightarrow\left( x<y\vee x=y\right) .
\]Using only asymmetry and transitivity of \(<\), prove by cases that \[
x\leq y\wedge y\leq z\Rightarrow x\leq z.
\]
