STEP-BY-STEP LESSON · §8.5
Partial Order Relations
Check a partial order and understand incomparable elements.
Before you begin
Reflexivity, Symmetry, and Transitivity
Reflexivity requires aRa for every a∈A, including elements with no other arrows.
∀a∈A: aRa
Symmetry requires that whenever aRb holds, bRa also holds.
aRb ⇒ bRa
If aRb and bRc hold, transitivity requires aRc. The elements a,b,c need not be distinct.
aRb ∧ bRc ⇒ aRc
Set Theory: Definitions and the Element Method of Proof
The statement x∈A concerns one object. A⊆B says that every element of A belongs to B.
A⊆B ⇔ ∀x(x∈A ⇒ x∈B)
X=Y means X⊆Y and Y⊆X. One inclusion still allows extra elements in the second set.
X=Y ⇔ (X⊆Y ∧ Y⊆X)
Symbols
- ≼
- order relation
- a≼b ∧ b≼a ⇒ a=b
- antisymmetry
- a≺b
- a≼b and a≠b, the strict comparison associated with ≼
Definitions and notation for this topic
Antisymmetric
∀a,b∈A: ((aRb∧bRa)→a=b)
If aRb and bRa both hold, then a=b.
Antisymmetric does not mean “not symmetric.”
Antisymmetric does not mean asymmetric or “not symmetric”. Equality on a set is both symmetric and antisymmetric.
Separate glossary example
The relation ≤ is antisymmetric.
Partial order
a≼b
A relation that is reflexive, antisymmetric, and transitive.
Some pairs of elements may be incomparable.
A partial order need not compare every pair. Under subset inclusion, {1} and {2} are incomparable. A total order additionally compares every pair.
Separate glossary example
Set inclusion ⊆ is a partial order.
Strict comparison associated with an order
a≺b ⇔ (a≼b ∧ a≠b)
Given a partial order ≼ on A, its strict version ≺ compares related elements that are different.
The strict relation is irreflexive and transitive. “Not a≺b” does not imply b≺a, because a partial order may have incomparable pairs.
Separate glossary example
For subset inclusion, {1}⊊{1,2} is a strict comparison. The sets {1} and {2} remain incomparable.
Step by step
Step 1 / 6
Distinguish antisymmetry
If both directions hold, the endpoints must be equal. Loops are allowed; distinct elements cannot have arrows in both directions.
aRb ∧ bRa ⇒ a=b
Antisymmetry does not simply mean “not symmetric”.
Worked example
Consider ⊆ on the set of all subsets of {1,2}.
- Every set includes itself. If X⊆Y and Y⊆X, then X=Y: reflexivity and antisymmetry hold.
- If X⊆Y and Y⊆Z, every element of X belongs through Y to Z. This is transitivity.
- However, {1} is not a subset of {2}, nor vice versa. The order is partial but not total.
Optional self-check
Are ∅ and {1,2} comparable under ⊆?
Show answer
Yes: ∅⊆{1,2}. The empty set is a subset of every set.