Strict Partial Orders (Strictly Partially Ordered Sets)

Strict Partial Order Relations

Let \(R\) be a binary relation on a set \(A\). That is, \[
R\subset A\times A
\]In particular, suppose that the binary relation \(R\) on \(A\) is assumed to satisfy asymmetry and transitivity, that is, \begin{align*}
& \left( S_{1}\right) \ \forall x,y\in A:\left[ \left( x,y\right) \in R\Rightarrow\left( y,x\right) \not \in R\right] \\
& \left( S_{2}\right) \ \forall x,y,z\in A:\left\{ \left[ \left(
x,y\right) \in R\wedge\left( y,z\right) \in R\right] \Rightarrow\left(
x,z\right) \in R\right\} .
\end{align*}Such a binary relation \(R\) is called a strict partial order or a strict order. The two properties that characterize a strict partial order, asymmetry and transitivity, are collectively called the axioms of strict order.

The symbol \(<\) is often used to represent a strict partial order. Thus, when a strict partial order \(R\) on \(A\) is given, for arbitrary \(x,y\in A\) we define \[
x<y\Leftrightarrow\left( x,y\right) \in R.
\]In this case, for arbitrary \(x,y\in A\), \[
\lnot\left( x<y\right) \Leftrightarrow\left( x,y\right) \not \in R
\]also holds. Using the symbol \(<\), the axioms of strict order can be 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*}

When a strict partial order \(<\) is defined on \(A\) and \(x<y\) holds for \(x,y\in A\), we say that \(x\) is less than \(y\), or that \(y\) is greater than \(x\).

If a strict partial order \(<\) is defined on \(A\), the pair \[
\left( A,<\right)
\]is called a strict partially ordered set or a strict ordered set. When it is clear from the context that a strict partially ordered set is being discussed, it may simply be denoted by
\[
A.
\]

Characterization of Strict Partial Orders

A binary relation \(R\) on a set \(A\) is said to be irreflexive if \[
\forall x\in A:\left( x,x\right) \not \in R
\]holds. A binary relation is a strict partial order if and only if it satisfies irreflexivity and transitivity.

Using the symbol \(<\) for a strict partial order, the preceding proposition states that the axioms of strict order are equivalent to \begin{align*}
& \left( a\right) \ \forall x\in A:\lnot\left( x<x\right) \\
& \left( b\right) \ \forall x,y,z\in A:\left[ \left( x<y\wedge y<z\right)
\Rightarrow x<z\right] .
\end{align*}

Example of a Strict Partial Order: The Strict Order on the Real Numbers

The usual strict order relation \(<\) for comparing real numbers is a binary relation on the set of real numbers \(\mathbb{R} \). Indeed, given the strict order relation \(<\), for arbitrary real numbers \(x,y\in\mathbb{R} \), we can define a binary relation \(R\) on \(\mathbb{R} \) by \[
\left( x,y\right) \in R\Leftrightarrow x<y.
\]Thus, for real numbers \(x,y\), \(\left( x,y\right) \in R\) holds if and only if \(x\) is less than \(y\). In other words, this defines \(R\) as a binary relation on \(\mathbb{R} \). Since this \(R\) can be identified with \(<\), we may regard \(<\) as a binary relation on \(\mathbb{R} \).

The strict order relation \(<\) on \(\mathbb{R} \) is a strict partial order on \(\mathbb{R} \). That is, \begin{align*}
& \left( S_{1}\right) \ \forall x,y\in\mathbb{R} :\left[ x<y\Rightarrow\lnot\left( y<x\right) \right] \\
& \left( S_{2}\right) \ \forall x,y,z\in\mathbb{R} :\left[ \left( x<y\wedge y<z\right) \Rightarrow x<z\right] .
\end{align*}

Example of a Strict Partial Order: Strict Set Inclusion

For two sets \(A\) and \(B\), if \(A\) is a subset of \(B\) and \(A\) is not equal to \(B\), that is, if \[
A\subset B\wedge A\not =B
\]holds, then \(A\) is called a proper subset of \(B\). We write \[
A\varsubsetneq B
\]to indicate that \(A\) is a proper subset of \(B\). This relation is called the strict inclusion relation.
Choose an arbitrary universal set \(U\) and consider strict inclusion among its subsets. For arbitrary \(A,B\in2^{U}\), define a binary relation \(R\) on \(2^{U}\) by
\[
\left( A,B\right) \in R\Leftrightarrow A\varsubsetneq B.
\]Here \(2^{U}\) denotes the power set of \(U\), that is, the family consisting of all subsets of \(U\). Thus, for subsets \(A,B\) of \(U\), \(\left( A,B\right) \in R\) holds if and only if \(A\) is a proper subset of \(B\). Since this \(R\) can be identified with \(\varsubsetneq\), we may regard \(\varsubsetneq\) as a binary relation on \(2^{U}\).

The strict inclusion relation \(\varsubsetneq\) on \(2^{U}\) is a strict partial order. That is, \begin{align*}
& \left( S_{1}\right) \ \forall A,B\in2^{U}:\left[ A\varsubsetneq B\Rightarrow\lnot\left( B\varsubsetneq A\right) \right] \\
& \left( S_{2}\right) \ \forall A,B,C\in2^{U}:\left[ \left( A\varsubsetneq B\wedge B\varsubsetneq C\right) \Rightarrow A\varsubsetneq C\right] .
\end{align*}

Examples of Binary Relations That Are Not Strict Partial Orders

If a binary relation \(R\) on a set \(A\) does not satisfy the axioms of strict order, that is, if \(R\) fails at least one of asymmetry and transitivity, then \(R\) is not a strict partial order.

Exercises