Hasse Diagrams: Visualizing Partial Orders in Discrete Mathematics

Learn about Hasse diagrams, a graphical way to represent partially ordered sets (posets). This guide explains how to construct Hasse diagrams from partial orders, highlighting their use in visualizing relationships between elements and simplifying the understanding of poset structures.

Hasse Diagrams and Partial Orders

What is a Hasse Diagram?

A Hasse diagram is a graphical way to represent a partially ordered set (poset). It's a simplified version of a directed graph that visually shows the relationships between elements in a set, making it easier to understand the structure of the partial order.

Key Points for Constructing Hasse Diagrams

  • Vertices are represented by dots (not circles).
  • The reflexive property (x ≤ x) is implied and not explicitly shown.
  • The transitive property is also implied: if a ≤ b and b ≤ c, then a ≤ c; the edge representing a ≤ c is omitted.
  • If a ≤ b, then b is placed above a in the diagram, and the arrow is omitted.

Example: Creating a Hasse Diagram

Let A = {4, 5, 6, 7} and R be the relation ≤ on A. R = {(4, 4), (4, 5), (4, 6), (4, 7), (5, 5), (5, 6), (5, 7), (6, 6), (6, 7), (7, 7)}.

(The directed graph representation of this relation would be included here.)

To create the Hasse diagram:

  1. Remove edges implied by reflexivity ((4,4), (5,5), (6,6), (7,7)).
  2. Remove edges implied by transitivity ((4, 7), (5, 7), (4, 6)).
  3. Represent vertices with dots, and omit arrowheads.

(The resulting Hasse diagram should be shown here.)

Upper and Lower Bounds

Let B be a subset of a partially ordered set A.

  • Upper Bound: An element x ∈ A is an upper bound of B if y ≤ x for all y ∈ B.
  • Lower Bound: An element z ∈ A is a lower bound of B if z ≤ x for all x ∈ B.

(An illustrative example showing upper and lower bounds of a subset is given in the original text and should be included here.)

Least Upper Bound (Supremum) and Greatest Lower Bound (Infimum)

Let A be a subset of a partially ordered set S.

  • Least Upper Bound (Supremum, Sup(A)): An upper bound of A that is less than or equal to all other upper bounds of A.
  • Greatest Lower Bound (Infimum, Inf(A)): A lower bound of A that is greater than or equal to all other lower bounds of A.

(An illustrative example using a Hasse diagram showing the least upper bound and greatest lower bound of a subset is given in the original text and should be included here.)

Conclusion

Hasse diagrams are valuable tools for visualizing and understanding partial orders. They provide a concise and intuitive way to represent the relationships between elements in a partially ordered set.