 # Applied Combinatorics

## 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{.}$$