1
Antisymmetry is what makes it an order
Distinct elements never relate both ways, so the relation cannot fold elements together. It separates rather than groups.
Lesson · Sets, Relations, and Functions · Relations
Partial Orders
Swap symmetry for antisymmetry and the structure changes completely: instead of grouping elements into classes, the relation ranks them. Some pairs stay incomparable, which is what makes it partial.
partial order = reflexive + antisymmetric + transitive
a and b incomparable ⟺ neither a ≼ b nor b ≼ a
total order = partial order with no incomparable pairs
Hasse diagram: drop loops, drop implied edges, point upward
The other structure a relation can carry
Core ideas
What this lesson establishes
Equivalence and order are the two structures a relation commonly has, and they differ in exactly one of the four properties.
2
Partial means some pairs are incomparable
Under ⊆, the sets {1} and {2} are incomparable. That is not a defect: most natural orders have incomparable pairs.
3
A Hasse diagram removes the redundancy
Loops are implied by reflexivity and long edges by transitivity, so both are omitted. What remains is the covering relation.
The material
Orders, comparability and diagrams
The definition, the special elements, and how to draw one.
Definition · Partial order
A relation ≼ on A is a partial order when it is reflexive, antisymmetric and transitive. The pair (A, ≼) is a poset.
Definition · Comparable, total order
a and b are comparable when a ≼ b or b ≼ a. A partial order in which every two elements are comparable is a total (or linear) order.
Example · Four posets
(ℤ, ≤) is total. (P(S), ⊆) is partial: {1} and {2} are incomparable. Divisibility on the positive integers is partial: 2 and 3 are incomparable. Alphabetical order on words is total.
Hasse diagrams
Drawing every pair of a partial order is unreadable, and most of the pairs are forced. A Hasse diagram draws only what is not: place b above a when a ≺ b, and draw an edge only when b covers a — that is, a ≺ b with nothing strictly between.
- No loops. Reflexivity is assumed, so (a,a) is never drawn.
- No arrowheads. Height encodes direction: higher is later.
- No implied edges. If a ≺ b ≺ c, the edge a to c is forced by transitivity and is omitted.
The full order is recovered from the diagram by taking the reflexive transitive closure of what is drawn: a ≼ b exactly when an upward path leads from a to b. The diagram is a compressed encoding, not a different relation.
Definition · Extremal elements
a is minimal if nothing is strictly below it, and maximal if nothing is strictly above. a is the least element if a ≼ x for every x, and the greatest if x ≼ a for every x.
Minimal and least are different, and the difference is the whole content of partiality. In ({2,3,4,6}, |) both 2 and 3 are minimal — nothing divides them within the set — and there is no least element, because neither divides the other. A least element is unique when it exists; minimal elements need not be.
Theorem · Uniqueness of least and greatest
A poset has at most one least element and at most one greatest.
Suppose a and b are both least. Then a ≼ b (since a is least) and b ≼ a (since b is least). Antisymmetry gives a = b. The greatest case is identical with the inequalities reversed.
□
That proof is where antisymmetry earns its place. Without it, two distinct elements could each precede the other and both count as least, and the notion would be useless.
Definition · Topological sort
A topological sort of a finite poset is a total order extending it: a listing of the elements in which every element appears after everything below it. Every finite poset has at least one, and “Breadth-First and Depth-First Search” in Graphs and Trees notes that a depth-first traversal of the directed graph produces one.
Interactive
Relation properties
Decided by checking, not by name
Method
Analysing a poset
Verify, then find the structure.
1
Verify the three properties
Reflexive, antisymmetric, transitive. Symmetry would collapse the order into an equivalence, so its absence is the point.
2
Find the incomparable pairs
These are what make it partial. If there are none, it is a total order and much of the subtlety disappears.
3
Identify minimal and maximal elements
Then ask separately whether a least or greatest exists. The two questions have different answers more often than not.
4
Draw the Hasse diagram
Only covering relations, only upward. If you have drawn an edge implied by transitivity, remove it.
Orders
Score 0 / 0Choose the answer you can justify.
Divisibility on {1, 2, 3, 4, 6, 12}
a ≼ b when a divides b.
Covering relations (nothing strictly between):
1 ≺ 2 1 ≺ 3 2 ≺ 4 2 ≺ 6 3 ≺ 6 4 ≺ 12 6 ≺ 12
Hasse diagram, bottom to top:
12
/ \
4 6
\ / \
2 3
\ /
1
least element: 1 (divides everything)
greatest element: 12 (everything divides it)
incomparable: 4 and 6, 3 and 4, 2 and 3
The edge from 1 to 4 is absent although 1 | 4: it is implied by 1 ≺ 2 ≺ 4, so it is not a covering relation. Drawing it would be redundant, and a diagram that includes implied edges is not a Hasse diagram.
Common mistakes
1
Confusing minimal with leastMinimal means nothing is below it; least means it is below everything. In a partial order these come apart, and that is the whole point of the word "partial".
2
Drawing implied edges in a Hasse diagramIf a ≺ b ≺ c, the edge from a to c is forced and must not be drawn. A diagram with it is just the relation, unreduced.
3
Assuming every poset is a total orderSubset, divisibility and task dependency are all partial. Incomparable pairs are the normal case, not an anomaly.
Check your understanding
✓
Finish when you can draw the Hasse diagram of the subsets of a three-element set.
Eight vertices in four levels, with edges only between sets differing by one element. Then identify the least, the greatest, and a pair of incomparable elements in the middle two levels.
Note: Topological sorting is the practical face of this lesson: build dependencies, course prerequisites and spreadsheet recalculation all extend a partial order to a total one. The depth-first search of “Breadth-First and Depth-First Search”, in Graphs and Trees, is where the algorithm comes from, and it fails exactly when the dependencies contain a cycle — which is to say, when they were not a partial order at all.