Notes on Partially Ordered Sets and Hasse Diagrams

Overview

• Focus on partially ordered sets (posets) and Hasse diagrams.
• Goal: Understand the definition of posets, view examples, and learn to create Hasse diagrams.
• Hasse diagrams simplify representation by omitting directional arrows.

Definition of Partially Ordered Set

• A partially ordered set (poset) is a set with a relation that is:
  • Reflexive: Every element is related to itself.
  • Anti-symmetric: If two elements relate to each other, they are equal.
  • Transitive: If element A relates to B and B relates to C, then A relates to C.

Example of a Poset

• Consider set S = {1, 2, 3}.
• Power set of S contains:
  • Empty set
  • {1}
  • {2}
  • {3}
  • {1, 2}
  • {1, 3}
  • {2, 3}
  • {1, 2, 3}
• Relation R: Subset relation (X ⊆ Y).
  • Forms the poset (P(S), R).

Properties of the Subset Relation

• Reflexive: Every set is a subset of itself.
• Anti-symmetric: If X ⊆ Y and Y ⊆ X, then X = Y.
• Transitive: If X ⊆ Y and Y ⊆ Z, then X ⊆ Z.

Hasse Diagram

• Represents the poset visually, without arrows.
• Direction is from bottom to top, indicating subset relations.
• Example:
  • Empty set (bottom) ⟶ {2} ⟶ {2, 3} ⟶ {1, 2, 3} (top).
• No arrows for reflexive relations or transitive relations to reduce clutter.

Second Example: Divisibility as a Poset

• Let A = {2, 3, 4, 6, 8, 12, 24}.
• Relation R: Divides relation (X divides Y).
• Each number divides itself (reflexive), and covers anti-symmetry and transitivity:
  • If X divides Y and Y divides X, then X = Y.

Hasse Diagram for Divisibility

• Ordered from bottom to top.
• Example of relations:
  • 2 ⟶ 4 ⟶ 24
  • 2 ⟶ 6 ⟶ 24
• Two disconnected components exist in the diagram.

Concepts of Maximal and Minimal Elements

• Maximal Element: An element Y is maximal if it relates to no element except itself.
  • Example: 24 and 35 are maximal.
• Minimal Element: An element X is minimal if it only relates to itself.
  • Example: 2, 3, and 7 are minimal.
• Maximum Element: An element that relates to every element in the poset.
  • Example: 24 is not maximum since 35 does not relate to it.
• Minimum Element: An element that relates to every other element.
  • No minimum exists in this example.

Key Takeaways

• A relation R on set A is a partial order if it is reflexive, anti-symmetric, and transitive.
• Hasse diagrams effectively visualize posets without unnecessary arrows for reflexive or transitive relations.
• Understanding maximal, minimal, maximum, and minimum elements is crucial for analyzing posets.

Conclusion

• A structured understanding of posets is foundational in set theory and serves as a stepping stone for more complex mathematical concepts.