Partial Orders and Strict Partial Orders on Sets

# Partial Orders and Strict Partial Orders on Sets

Recall from the Relations on Sets page that if $X$ is a set then $R$ is a relation on $X$ if $R \subseteq X \times X$ where $X \times X$ is The Cartesian Product of Set $X$ with itself. We also defined reflexive, irreflexive, antisymmetric, antisymmetric, and transitive relations.

We will now begin to look at partial orders and strict partial orders on sets.

 Definition: The relation $R$ on the set $X$ is said to be a Partial Order on $X$ if $R$ is reflexive, antisymmetric, and transitive. If $R$ is a partial order on $X$ then $X$ is said to be a Partially Ordered Set with $R$. The $R$ is said to be a Strict Partial Order on $X$ if $R$ is irreflexive, antisymmetric, and transitive. If $R$ is a strict partial order on $X$ then $X$ is said to be a Strict Partially Ordered Set with $R$.

If $X$ is a set and $R$ is a partial order of elements in $X$ then sometimes we use the notation "$\preceq$" instead of "$R$". Similarly, if $R$ is a strict partial order of elements in $X$ then sometimes we use the notation "$\prec$".

Recall the relation $\subseteq$ of containment on the set $X$ of subsets of $E = \{ x, y, z \}$. We've noted that $R$ is reflexive (since for all $A \in X$ we have that $A \subseteq A$), antisymmetric (since for all $A, B \in X$ where $A \neq B$ we have that $A \subseteq B$ implies that $B \not \subseteq A$), and transitive (since for all $A, B, C \in X$ if $A \subseteq B$ and $B \subseteq C$ then $A \subseteq C$). Therefore $\subseteq$ is a partial order on $X$.

Also recall the relation $<$ of strict inequality on the set of integers between $1$ and $10$ inclusive, i.e., $X = \{1, 2, ..., 10 \}$. We've already noted that $R$ is irreflexive (since for all $x \in X$ we have that $x \not < x$), antisymmetric (since for all $x, y \in X$ we have that if $x < y$ then $y \neq x$), and transitive (since for all $x, y, z \in X$ we have that if $x < y$ and $y < z$ then $x < z$). Therefore $<$ is a strict partial order on $A$.