## SectionB.10Partial Orders and Total Orders

A binary relation $R$ on a set $X$ is just a subset of the cartesian product $X\times X\text{.}$ In discussions of binary relations, the notation $(x,y)\in R$ is sometimes written as $xRy\text{.}$

A binary relation $R$ is:

1. reflexive if $(x,x)\in R$ for all $x\in X\text{.}$
2. antisymmetric if $x=y$ whenever $(x,y)\in R$ and $(y,x)\in R\text{,}$ for all $x,y\in X\text{.}$
3. transitive if $(x,y)\in R$ and $(y,z)\in R$ imply $(x,z)\in R\text{,}$ for all $x,y,z\in X\text{.}$

A binary relation $R$ on a set $X$ is called a partial order on $X$ when it is reflexive, antisymmetric, and transitive. Traditionally, symbols like $\le$ and $\subseteq$ are used to denote partial orders. As an example, recall that if $X$ is a family of sets, we write $A\subseteq B$ when $A$ is a subset of $B\text{.}$

When using the ordered pair notation for binary relations, to indicate that a pair $(x,y)$ is not in the relation, we simply write $(x,y)\notin R\text{.}$ When using the alternate notation, this is usually denoted by using the negation symbol from logic and writing $\lnot (xRy)\text{.}$ Most of the special symbols used to denote partial orders come with negative versions, e.g., $x\not\le y\text{,}$ $x\nsubseteq y\text{.}$

A partial order is called a total order on $X$ when for all $x,y\in X\text{,}$ $(x,y)\in R$ or $(y,x)\in R\text{.}$ For example, if

\begin{equation*} X=\{\emptyset,\{\emptyset\},\{\emptyset,\{\emptyset\}\}\} \end{equation*}

then $\subseteq$ is a total order on $X\text{.}$

When $\le$ is a partial order on a set $X\text{,}$ we write $x\lt y$ when $x\le y$ and $x\neq y\text{.}$