19.3: Graph for a partial order

Last updated
Save as PDF

Page ID: 83501

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Definition: Hasse diagram

a diagram for the graph for a partial order on a finite set \(A\text{,}\) omitting reflexive loops and transitive “composite” edges, and placing “smaller” elements lower on the diagram instead of using arrows

Example \(\PageIndex{1}\): Hasse diagram for division of integers.

Let \(A = \{2,4,6,8,10,12\}\text{.}\) The Hasse diagram of the partial order \(\mathord{\mid}\) (i.e. “divides”) on \(A\) appears in Figure \(\PageIndex{1}\). Notice that \(2\) is not joined directly to either \(8\) or \(12\text{,}\) since we can use transitivity and the facts that \(2 \mid 4\) and \(2 \mid 6\) to infer \(2 \mid 8\) and \(2 \mid 12\text{,}\) respectively, from the diagram.

Figure \(\PageIndex{1}\): The Hasse diagram for the “divides” partial order on a finite set of integers.

Remark \(\PageIndex{1}\)

See Example 14.4.2 for another example of a graph for the “divides” relation.

Example \(\PageIndex{2}\): Hasse diagram for subset order.

The graph from Example 14.4.1 has been reproduced in Figure \(\PageIndex{2}\) as a Hasse diagram, and represents the partial order \(\mathord{\subseteq}\) on \(\mathscr{P}(\{a,b,c\})\text{.}\)

Figure \(\PageIndex{2}\): The Hasse diagram for the subset partial order on the power set of a finite set.