Partial Orders and Hasse Diagrams

Introduction

• Focus on partially ordered sets (posets) and Hasse diagrams.
• Definition and examples of posets will be covered.
• Link to a dedicated lesson on Hasse diagrams in the description.

Definition of Partially Ordered Set (Poset)

• Definition: A relation R on a set A is a partial order if:
  • Reflexive: Every element relates to itself.
  • Anti-symmetric: If a relates to b and b relates to a, then a = b.
  • Transitive: If a relates to b and b relates to c, then a relates to c.
• The set A with the partial order R is called a partially ordered set (poset).

Example: Power Set

• Let S = {1, 2, 3}.
• Power Set: Set of all subsets of S, denoted as P(S).
• Relation R: Subset relation on P(S).
  • Example of pairs: (∅, {2}), ({2}, {1, 2, 3}), etc.
• Verification of Properties:
  • Reflexive: Every set is a subset of itself.
  • Anti-symmetric: Distinct elements cannot relate in both directions.
  • Transitive: If A ⊆ B and B ⊆ C, then A ⊆ C.
• Thus, P(S) forms a poset with the subset relation.

Hasse Diagram for Power Set

• No arrows to indicate direction; the diagram implies direction.
• Example demonstrates relationships:
  • ∅ ⊆ {2}; {2} ⊆ {2, 3}; etc.
• Reflexivity and transitivity do not clutter the diagram with arrows.

Example: Divisor Relationship

• Let A = {2, 3, 4, 6, 8, 12, 24, 35}.
• Relation R: Divides relation (x divides y).
• Properties of the divides relation:
  • Reflexive: Every number divides itself.
  • Anti-symmetric: If x divides y and y divides x, then x = y.
  • Transitive: If x divides y and y divides z, then x divides z.
• A with the divides relation forms a poset.

Hasse Diagram for Divisor Set

• Ordered from bottom to top (2 divides 4, etc.).
• No arrows for reflexivity and transitive relationships.
• Maximal Elements: Elements that relate to no other element except themselves:
  • Examples: 24, 35.
• Minimal Elements: Elements that are only related to themselves:
  • Examples: 2, 3, 7.
• Maximum Element: An element that every other element relates to:
  • 24 is not maximum due to disconnections.
• Minimum Element: An element that relates to every other element:
  • No minimum in this poset.

Summary of Key Concepts

• Partial Order: Relation that is reflexive, anti-symmetric, and transitive.
• Hasse Diagram: Representation of a poset that simplifies relationships and avoids clutter.
• The arrangement shows relationships based on the properties of posets.
• Maximal/Minimal Elements: Defined based on their relationships within the set.
• Maximum/Minimum Elements: Uniqueness in posets when they exist.