Hasse Diagrams
So far we have looked at:
- Partial Orders - Relations $R$ on a set $X$ that are reflexive, antisymmetric, and transitive.
- Strict Partial Orders - Relations $R$ on a set $X$ that are irreflexive, antisymmetric, and transitive.
- Total Orders - Relations $R$ that are partial orders and such all $x, y \in X$ are comparable.
- Equivalence Relations - Relations $R$ that are reflexive, symmetric, and transitive.
For finite $n$-element sets $X$, if $n$ is relatively small then we can often describe a relation $R$ with what are known as Hasse diagrams. We first define what it means for an element in a set to cover another element under a relation $\leq$.
| Definition: Let $X$ be a finite $n$-element set and let $\leq$ be a relation on $X$. For $x, y \in X$ we say that the element $y$ Covers the element $x$ denoted $x <_C y$ if there exists no element $z \in X$ such that $x < z < y$. |
We are now ready to define what a Hasse diagram is.
| Definition: A Hasse Diagram of a finite $n$-element set $X$ is a graph representing a relation $R$ on $X$. Each element $x \in X$ is represented by a point. If $x <_C y$ then we place the point represent $x$ below the point representing $y$. |
For example, consider the set $X$ of positive integers between $1$ and $8$ inclusive, that is:
(1)Let $\mid$ be the partial order relation defined for all $x, y \in X$ to be $x \mid y$ means that $x$ is a divisor of $y$. The graph below depicts the Hasse diagram for this relation.
For another example, consider the finite $3$-element set $A = \{0, 1, 2 \}$. Consider the power set $\mathcal P(A)$ and consider the relation partial order $\subseteq$ on $\mathcal P(A)$. The Hasse diagram for this relation is:
For a final example, consider the finite $n$-element set $X = \{x_1, x_2, ..., x_n \}$. Suppose that $\leq$ is a total order on $X$. Then $x_1 < x_2 < ... < x_n$ and we can represent this total order $\leq$ with the following Hasse diagram:
