Definition:Hasse Diagram

From ProofWiki
Jump to: navigation, search

Definition

Let $\left({S, \preceq}\right)$ be an ordered set.


A Hasse diagram is a method of representing $\left({S, \preceq}\right)$ as a graph $G$, in which:

  • If $x, y \in S: x \preceq y$ then the edge representing $x \preceq y$ is drawn so that $x$ is lower down the page than $y$, that is, the edge ascends (usually obliquely) from $x$ to $y$
  • If $x \preceq y$ and $y \preceq z$, then as an ordering is transitive it follows that $x \preceq z$. But in a Hasse diagram, the relation $x \preceq z$ is not shown. Transitivity is implicitly expressed by the fact that $z$ is higher up than $x$, and can be reached by tracing a path from $x$ to $z$ completely through ascending edges.


Some sources draw arrows on their edges, so as to make $G$ a directed graph, but this is usually considered unnecessary.


These are examples of Hasse diagrams:

Hasse-Diagram.png


The diagram on the left illustrates the "Divides" ordering on the set $S = \left\{{1, 2, 3, 4, 6, 8, 12, 24}\right\}$ where $S$ is the set of all elements of $\N_{>0}$ which divide $24$.


The diagram on the right illustrates the "Subset" relation on the power set $\mathcal P \left({S}\right)$ where $S = \left\{{1, 2, 3}\right\}$.


Also known as

Some sources refer to this as a nodal diagram.


Source of Name

This entry was named for Helmut Hasse.


Sources

The diagram is not named, and it is applied only to the subset relation
The diagram is not named