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\) satisfies reflexivity, antisymmetry, and transitivity, that is, \begin{align*}
& \left( O_{1}\right) \ \forall x\in A:\left( x,x\right) \in R\\
& \left( O_{2}\right) \ \forall x,y\in A:\left\{ \left[ \left(
x,y\right) \in R\wedge\left( y,x\right) \in R\right] \Rightarrow x=y\right\} \\
& \left( O_{3}\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 partial order, or simply an order. The three properties that characterize a partial order, namely reflexivity, antisymmetry, and transitivity, are collectively called the axioms of order.
The symbol \(\leq\) is often used to represent a partial order. Thus, when a partial order \(R\) on \(A\) is given, for arbitrary \(x,y\in A\) we define \[
x\leq y\Leftrightarrow\left( x,y\right) \in R.
\]In this case,
\[
\lnot\left( x\leq y\right) \Leftrightarrow\left( x,y\right) \not \in R
\]also holds for arbitrary \(x,y\in A\). Using the notation \(\leq\), the axioms of order 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*}
When a partial order \(\leq\) is defined on \(A\) and \(x\leq y\) holds for \(x,y\in A\), we say that \(x\) is less than or equal to \(y\), that \(y\) is greater than or equal to \(x\), or that \(x\) does not exceed \(y\).
If a partial order \(\leq\) is defined on \(A\), the pair \[
\left( A,\leq\right)
\]is called a partially ordered set or an ordered set. When it is clear from the context that a partially ordered set is being discussed, it may simply be denoted by
\[
A.
\]
Example of a Partial Order: The Inverse Relation of a Partial Order
Let \(\left( A,\leq\right) \) be a partially ordered set. Denote the inverse relation of \(\leq\) by \[
\geq\subset A\times A.
\]By the definition of an inverse relation, for arbitrary \(x,y\in A\), \[
x\geq y\Leftrightarrow y\leq x.
\]Thus, \(x\) is greater than or equal to \(y\) under the inverse relation \(\geq\) if and only if \(y\) is less than or equal to \(x\) under the original partial order \(\leq\).
The inverse relation \(\geq\) of the partial order \(\leq\) is also a partial order. That is, \begin{align*}
& \left( O_{1}\right) \ \forall x\in A:x\geq x\\
& \left( O_{2}\right) \ \forall x,y\in A:\left[ \left( x\geq y\wedge y\geq x\right) \Rightarrow x=y\right] \\
& \left( O_{3}\right) \ \forall x,y,z\in A:\left[ \left( x\geq y\wedge y\geq z\right) \Rightarrow x\geq z\right] .
\end{align*}
Example of a Partial Order: The Usual Order on the Real Numbers
The usual order relation \(\leq\) for comparing real numbers is a binary relation on the set of real numbers \(\mathbb{R} \) . Indeed, given the relation \(\leq\), for arbitrary real numbers \(x,y\in\mathbb{R} \), define a binary relation \(R\) on \(\mathbb{R} \) by requiring that \[
\left( x,y\right) \in R\Leftrightarrow x\leq y.
\]Thus, for \(x,y\in\mathbb{R} \), \(\left( x,y\right) \in R\) holds if and only if \(x\) is less than or equal to \(y\). Identifying this binary relation \(R\) with the usual order relation \(\leq\), we may regard \(\leq\) as a binary relation on \(\mathbb{R} \)
The usual order \(\leq\) on \(\mathbb{R} \), regarded as a binary relation on \(\mathbb{R} \), is a partial order. That is, \begin{align*}
& \left( O_{1}\right) \ \forall x\in\mathbb{R} :x\leq x\\
& \left( O_{2}\right) \ \forall x,y\in\mathbb{R} :\left[ \left( x\leq y\wedge y\leq x\right) \Rightarrow x=y\right] \\
& \left( O_{3}\right) \ \forall x,y,z\in\mathbb{R} :\left[ \left( x\leq y\wedge y\leq z\right) \Rightarrow x\leq z\right] .
\end{align*}
Example of a Partial Order: Set Inclusion
Fix an arbitrary universal set \(U\) and consider the inclusion relation among its subsets. For arbitrary \(A,B\in2^{U}\), define a binary relation \(R\) by \[
\left( A,B\right) \in R\Leftrightarrow A\subset B.
\]Here \(2^{U}\) denotes the power set of \(U\), that is, the family consisting of all subsets of \(U\). Thus, \(\left( A,B\right) \in R\) holds if and only if \(A\) is a subset of \(B\). Identifying \(R\) with the inclusion relation \(\subset\), we may regard \(\subset\) as a binary relation on \(2^{U}\).
The inclusion relation \(\subset\) on \(2^{U}\) is a partial order. That is, \begin{align*}
& \left( O_{1}\right) \ \forall A\in2^{U}:A\subset A\\
& \left( O_{2}\right) \ \forall A,B\in2^{U}:\left[ \left( A\subset B\wedge B\subset A\right) \Rightarrow A=B\right] \\
& \left( O_{3}\right) \ \forall A,B,C\in2^{U}:\left[ \left( A\subset B\wedge B\subset C\right) \Rightarrow A\subset C\right] .
\end{align*}
Example of a Partial Order: Divisibility on the Natural Numbers
For natural numbers \(m,n\in\mathbb{N} \), we write \[
n|m
\]when \(m\) is a multiple of \(n\) (equivalently, \(n\) is a divisor of \(m\)). This is called the divisibility relation on \(\mathbb{N} \). For arbitrary \(m,n\in\mathbb{N} \), define a binary relation \(R\) by requiring that \[
\left( n,m\right) \in R\Leftrightarrow n|m.
\]Thus, for \(m,n\in\mathbb{N} \), \(\left( n,m\right) \in R\) holds if and only if \(m\) is a multiple of \(n\). Identifying \(R\) with the divisibility relation \(|\) on \(\mathbb{N} \), we may regard \(|\) as a binary relation on \(\mathbb{N} \)
The divisibility relation \(|\) on \(\mathbb{N} \), regarded as a binary relation on \(\mathbb{N} \), is a partial order. That is, \begin{align*}
& \left( O_{1}\right) \ \forall m\in\mathbb{N} :m|m\\
& \left( O_{2}\right) \ \forall m,n\in\mathbb{N} :\left[ \left( n|m\wedge m|n\right) \Rightarrow m=n\right] \\
& \left( O_{3}\right) \ \forall l,m,n\in\mathbb{N} :\left[ \left( n|m\wedge m|l\right) \Rightarrow n|l\right] .
\end{align*}
Example of a Partial Order: The Identity Relation
Given a set \(A\), for arbitrary \(x,y\in A\), define a binary relation \(R\) by requiring that \[
\left( x,y\right) \in R\Leftrightarrow x=y.
\]Such a relation \(R\) is called the identity relation. Thus, \(\left( x,y\right) \in R\) holds if and only if \(x\) and \(y\) are equal. Identifying \(R\) with equality \(=\), we may regard equality as a binary relation on \(A\).
The identity relation \(=\) on \(A\) is a partial order. That is, \begin{align*}
& \left( O_{1}\right) \ \forall x\in A:x=x\\
& \left( O_{2}\right) \ \forall x,y\in A:\left[ \left( x=y\wedge y=x\right) \Rightarrow x=y\right] \\
& \left( O_{3}\right) \ \forall x,y,z\in A:\left[ \left( x=y\wedge y=z\right) \Rightarrow x=z\right] .
\end{align*}
Examples of Binary Relations That Are Not Partial Orders
If a binary relation \(R\) on a set \(A\) does not satisfy the axioms of order, that is, if it fails at least one of reflexivity, antisymmetry, and transitivity, then \(R\) is not a partial order.
\left( x,y\right) \in R\Leftrightarrow x\text{ and }y\text{ are in the same grade}.
\]Then \(R\) is not a partial order on \(A\) (Exercise).
\left( x,y\right) \in R\Leftrightarrow x<y.
\]Then \(R\) is not a partial order on \(\mathbb{R} \) (Exercise).
\left( x,y\right) \in R\Leftrightarrow x\text{ and }y\text{ are similar}.
\]Then \(R\) is not a partial order on \(A\) (Exercise).
\phi\subset A\times A.
\]Thus \(\phi\) is a binary relation on \(A\). When the empty set \(\phi\) is regarded as a binary relation, it is called the empty relation. The empty relation \(\phi\) is not a partial order on \(A\) (Exercise).
A\times A\subset A\times A.
\]Thus \(A\times A\) is a binary relation on \(A\). When the Cartesian product \(A\times A\) is regarded as a binary relation, it is called the universal relation. The universal relation \(A\times A\) is not a partial order on \(A\) (Exercise).
Exercises
\left( x,y\right) \in R\Leftrightarrow x\text{ and }y\text{ are in the same grade}.
\]Show that \(R\) is not a partial order on \(A\).
\left( x,y\right) \in R\Leftrightarrow x<y.
\]Show that \(R\) is not a partial order on \(\mathbb{R} \).
\left( x,y\right) \in R\Leftrightarrow x\text{ and }y\text{ are similar}.
\]Show that \(R\) is not a partial order on \(A\).
\phi\subset A\times A,
\]the empty set \(\phi\) can be regarded as a binary relation on \(A\). Show that the empty relation \(\phi\) is not a partial order on \(A\).
A\times A\subset A\times A,
\]the Cartesian product \(A\times A\) can be regarded as a binary relation on \(A\). Show that the universal relation \(A\times A\) is not a partial order on \(A\).
x\leq_{B}y\Leftrightarrow x\leq y
\]Show that \(\leq_{B}\) is a partial order on \(B\).
R\cap S
\]is also a partial order on \(A\).
R\cup S
\]also be a partial order on \(A\)? Prove the statement if it is true; otherwise, give a counterexample.
\left( a_{1},b_{1}\right) \preceq\left( a_{2},b_{2}\right) \Leftrightarrow
\left( a_{1}\leq_{A}a_{2}\wedge b_{1}\leq_{B}b_{2}\right) .
\]Show that \(\preceq\) is a partial order on \(A\times B\).
I_{A}=\left\{ \left( x,x\right) \ |\ x\in A\right\} .
\]
R\cap R^{-1}=I_{A}.
\]Here \(I_{A}\) is the identity relation on \(A\), defined by \[
I_{A}=\left\{ \left( x,x\right) \ |\ x\in A\right\} .
\]
