Course contentsShow
← Computer Science
Lesson 74 of 2,8722. Discrete Mathematics for CSFree lesson

Partial Orders

Define partial order relations as reflexive, antisymmetric, and transitive; introduce Hasse diagrams.

Partial Orders

What you'll learn: You'll discover what partial order relations are and how Hasse diagrams visualize them.

What is a Partial Order?

A partial order is a special type of relation that lets us compare some (but not necessarily all) elements in a set according to a consistent ordering. Think of it like organizing files in folders by "contains" — some files clearly belong in one folder or another, but two unrelated files in different folders can't be compared.

For a relation R on set A to be a partial order, it must satisfy three properties you've already learned:

  1. Reflexive: Every element relates to itself (a R a for all a)
  2. Antisymmetric: If a R b and b R a, then a = b
  3. Transitive: If a R b and b R c, then a R c

Common examples include:

  • "≤" (less than or equal to) on numbers
  • "⊆" (subset) on sets
  • "divides" on positive integers (3 divides 6, 6 divides 12, so 3 divides 12)

Hasse Diagrams

A Hasse diagram is a visual way to represent partial orders. It's a simplified graph where:

  • Elements are shown as dots (vertices)
  • If a < b (and nothing between), draw a line with b above a
  • We remove reflexive loops and transitive connections to keep it clean

For the divisibility relation on {1, 2, 3, 6}, the Hasse diagram shows 6 at top, 2 and 3 in the middle, and 1 at bottom — because 1 divides everything, while 2 and 3 are incomparable to each other.

Key Takeaway: A partial order is a reflexive, antisymmetric, and transitive relation that orders elements consistently; Hasse diagrams visualize these orderings by showing only the essential direct relationships.