Relations / Partial Orders
Least You Need to Know: Partial Orders
A partial order is reflexive, antisymmetric, and transitive. Unlike equivalence relations, not every pair must be comparable.
The least you need to know
- A partial order is reflexive, antisymmetric, and transitive.
- Antisymmetric is different from asymmetric.
- A partial order does not require every pair to be comparable.
- Divisibility and subset are standard examples of partial orders.
- Hasse diagrams omit reflexive and transitive edges.
Key notation
≤
typical partial-order notation
a | b
a divides b
A ⊆ B
A is a subset of B
Tiny worked example
- On the power set of `{1,2}`, use subset inclusion.\n- Every set is a subset of itself, so the relation is reflexive.\n- If `A⊆B` and `B⊆A`, then `A=B`, so it is antisymmetric.\n- Subset inclusion is also transitive, so it is a partial order.
Common mistakes
- Students often mix up antisymmetric and symmetric.
- A missing comparison does not break a partial order.
- Hasse diagrams keep only cover relations, not every implied edge.
How to recognize this kind of problem
- The prompt asks about comparability, maximal elements, or Hasse diagrams.
- The relation is based on inclusion or divisibility.
- The properties reflexive/antisymmetric/transitive appear together.