Section B.10 Partial 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:
- reflexive if \((x,x)\in R\) for all \(x\in X\text{.}\)
- antisymmetric if \(x=y\) whenever \((x,y)\in R\) and \((y,x)\in R\text{,}\) for all \(x,y\in X\text{.}\)
- 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{.}\)
You have attempted of activities on this page.
