Hasse Diagrams
Table of Contents

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:

\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:

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License