Hasse Diagrams

# 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)
\begin{align} \quad X = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10 \} \end{align}

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: 