Order relations and partially ordered sets

One kit can contain another without every pair being comparable

There are two tools: a key labelled a and a lamp labelled b. The possible kits are ∅, {a}, {b} and {a,b}. Say that kit X comes before kit Y when every tool in X is also in Y. Then ∅ comes before every kit, and both single-tool kits come before {a,b}.

The kits {a} and {b} cannot be compared by this rule: each has a tool the other lacks. Neither comes before the other. Equal kit sizes do not make one a subset of the other, and their left-to-right positions in a drawing do not create an ordering.

Write P = {∅, {a}, {b}, {a,b}} and X ⪯ Y when X ⊆ Y. The symbol ⪯ names this rule; it does not mean ordinary numerical size. The adjacent diagram places an earlier kit below a later kit and keeps every allowed kit visible.

Read the objects and the rule before the diagram

Revisit the published lesson Symbols, definitions and mathematical language to keep an object, its label and a statement about it separate. Revisit Number lines, order and comparison for the familiar ≤ example, and Multiplication and division for the whole-number multiple meaning used by the divisibility example.

The sets and relations lessons explain subsets and ordered pairs in more detail. Here X ⊆ Y means every member of X is a member of Y, and a relation on P tells which ordered pairs (x,y) with x,y ∈ P satisfy a rule. You can start with the four kits and the finite tables, then return to the quantified proofs after those meanings are secure.

On a first reading, finish comparability, Hasse paths and finite extrema before the final real-interval and empty-subset cases. The optional interval case uses the published lesson Inequalities, intervals and absolute value. Return to it after you can distinguish an interval’s endpoint from an element of the interval.

Three conditions make a non-strict partial order

A non-strict partial order ⪯ on P is reflexive, antisymmetric and transitive. The pair (P, ⪯) is a partially ordered set, or poset. These conditions concern all elements of P, not only the pairs you happened to draw.

Reflexivity says x ⪯ x for every x ∈ P. Antisymmetry says that if x ⪯ y and y ⪯ x, then x = y. Transitivity says that if x ⪯ y and y ⪯ z, then x ⪯ z. An implication asks for its conclusion only when its whole stated assumption holds.

Subset inclusion satisfies these rules. Each kit includes all its own tools. If X ⊆ Y and Y ⊆ X, they have exactly the same tools and are equal. If X ⊆ Y and Y ⊆ Z, every tool of X passes through Y into Z, so X ⊆ Z. These arguments apply to arbitrary sets, not just our four kits.

Antisymmetry permits self-relations

Symmetry says xRy implies yRx. Antisymmetry allows two-way relations only when the two elements are equal. It does not ban xRx: every non-strict partial order requires all those self-relations. Asymmetry is a different condition, xRy implies that yRx is false; it also forbids self-relations.

The equality relation is both symmetric and antisymmetric. Its only pairs have equal entries. Conversely, a relation can be not symmetric and still fail antisymmetry: on distinct a,b,c, take exactly (a,b), (b,a) and (a,c). The missing (c,a) refutes symmetry, while (a,b) and (b,a) refute antisymmetry.

Therefore, “not symmetric” is not a definition of antisymmetric. Check the implication about two-way relations directly. Nor does reflexivity plus antisymmetry guarantee transitivity: self-relations together with (a,b) and (b,c), but not (a,c), provide a counterexample on three distinct elements.

The same-looking rule can change when its domain changes

On positive integers, define x ⪯ y by x | y: there is an integer k with y = kx. Each x divides itself. If y = kx and z = ly, then z = (lk)x, proving transitivity. If positive x,y divide each other, their positive integer multipliers have product 1, so both multipliers are 1 and x = y. Thus divisibility is a partial order on the positive integers.

It is not total: neither 2 divides 3 nor 3 divides 2. In the finite poset D = {1,2,3,6,12} under divisibility, 2 ⪯ 6 ⪯ 12 and 3 ⪯ 6, but 2 and 3 remain incomparable. A larger printed numeral is not automatically above every smaller numeral in this order.

On all integers, the same divisibility rule fails antisymmetry: 2 divides −2 and −2 divides 2, but 2 ≠ −2. Always name the set and the rule together. Ordinary ≤ on integers is a different relation and remains a total order.

Total order adds comparison for every pair

Elements x,y of a poset are comparable when x ⪯ y or y ⪯ x. They are incomparable when neither relation holds. The “or” is inclusive: an element is comparable with itself by reflexivity.

A total, or linear, order is a partial order in which every pair is comparable. Ordinary ≤ on the real numbers is total. Inclusion on the four kits is partial but not total because {a} and {b} are incomparable. Calling an order partial does not require an incomparable pair: every total order also meets the partial-order conditions.

Incomparability is not equality. It also does not imply that the elements have no common upper bound: {a,b} is above both single-tool kits. The question “can these two be compared?” differs from “is there an element above both?”

Remove equality deliberately when using a strict order

From a non-strict partial order define x ≺ y when x ⪯ y and x ≠ y. Then x ≺ x never holds: the strict order is irreflexive. It is transitive. If x ≺ y and y ≺ z, non-strict transitivity gives x ⪯ z; equality x = z would force y ⪯ x and x ⪯ y, contradicting x ≠ y by antisymmetry. Hence x ≺ z.

Conversely, a strict partial order is an irreflexive, transitive relation ≺. Define x ⪯ y when x = y or x ≺ y. Reflexivity follows from equality. Two distinct elements related both ways would give x ≺ y ≺ x, contradicting irreflexivity. For transitivity, equality cases simply substitute an equal element; when both comparisons are strict, use strict transitivity. This recovers a non-strict partial order.

A strict partial order is asymmetric: x ≺ y and y ≺ x would imply x ≺ x. The word “strict” does not add total comparability. Proper subset inclusion is strict but the two single-tool kits are still incomparable. State which convention is in use rather than testing < for reflexivity as though it were ≤.

A Hasse edge is a cover, not every related pair

For x ≺ y, say that y covers x when no z ∈ P satisfies x ≺ z ≺ y. A finite Hasse diagram draws one edge for each such cover, with x below y. It omits self-loops and direct edges already explained by intermediate elements. The omitted relations still belong to the non-strict order.

For the kits there are four covers: ∅ to {a}, ∅ to {b}, {a} to {a,b}, and {b} to {a,b}. There is no cover edge from ∅ straight to {a,b}: either singleton is an intermediate kit. Nevertheless ∅ ⪯ {a,b} is true, as both upward two-edge paths show.

In a finite poset, x ⪯ y exactly when x = y or there is a path of cover edges that keeps going upward from x to y. Finiteness allows intermediate elements to be inserted until the remaining steps are covers. A path that goes up and then down does not establish comparability. Height records order direction here, not a measured numerical distance.

The finite condition matters. In (ℚ, ≤), between any distinct x < y lies (x+y)/2, so there are no covers even though many strict comparisons hold. A cover-edge picture alone would not recover that infinite order.

A chain compares every pair; an antichain compares no distinct pair

A chain is a subset C of P whose members are pairwise comparable. For the kits, {∅, {a}, {a,b}} is a chain. A chain need not use every element of P, and successive members in a listed chain need not be covers. The two-element subset {∅, {a,b}} is also a chain.

The chain contains ∅, {a} and {a,b}, with every pair comparable. The antichain contains {a} and {b}, which are incomparable. Both are subsets of the same four-kit poset.

An antichain is a subset in which any two distinct members are incomparable. The subset {{a}, {b}} is an antichain. Distinctness is essential: each element is still comparable with itself. An empty subset and a singleton satisfy both definitions because they contain no distinct pair that could fail either test.

The adjacent two panels highlight a chain and an antichain in the same poset. Read comparability from upward paths, not from visual alignment. A row of nodes does not by itself define an antichain in an arbitrary drawing; the relation does.

Having nobody below you differs from being below everybody

For a subset S ⊆ P, a minimal element m belongs to S and has no distinct member of S strictly below it. A maximal element belongs to S and has no distinct member of S strictly above it. A least element l belongs to S and satisfies l ⪯ s for every s ∈ S; a greatest element g belongs to S and satisfies s ⪯ g for every s ∈ S.

In the whole fork poset a,b,c, the minimal members are a,b and the greatest member is c. There is no least member. For the selected pair {a,b}, c is an upper bound outside that pair and there is no lower bound.

The ambient order is restricted to S for these four questions. In S = {{a}, {b}} both members are minimal and maximal, but neither is least or greatest. For the whole four-kit P, ∅ is least and {a,b} is greatest. Naming S prevents us from confusing a subset’s extrema with the whole poset’s extrema.

In the three-element poset with a ≺ c and b ≺ c, but a and b incomparable, the minimal elements are a,b. The sole maximal element c is also greatest. There is no least element. Every least element is minimal, but a minimal element need not be least; the greatest/maximal statements are dual.

Use antisymmetry for uniqueness and finiteness for existence

If l and m are both least elements of S, then l ⪯ m because l is least, and m ⪯ l because m is least. Antisymmetry gives l = m. Thus a least element, when it exists, is unique. Reverse the inequalities to prove uniqueness of a greatest element. This proof does not show that either element exists.

Every nonempty finite S has a minimal element and a maximal element. Start from any member; if it is not minimal, move to a strictly smaller member of S. Distinct downward steps cannot repeat a member, and there are only finitely many, so the process stops at a minimal member. Moving upward proves the maximal statement. Several stopping points may remain incomparable.

In a nonempty finite poset, a unique minimal element is least: for each x, descending inside the members at or below x reaches a minimal element of the whole poset, which must be the unique one. This implication needs finiteness. For example, take all integers in their usual order and a new element a comparable only with itself. Then a is the unique minimal element, but it is not least because it is incomparable with every integer.

For an empty S there is no element to be minimal, maximal, least or greatest. In (ℤ, ≤) there is no minimal or maximal element at all: n−1 and n+1 are available for every integer n. A finite diagram cannot justify these infinite existence conclusions.

A bound must be in P, but need not be in S

Let S ⊆ P. An upper bound u is an element of P with s ⪯ u for every s ∈ S. A lower bound l is an element of P with l ⪯ s for every s ∈ S. Bounds are sought in the declared ambient poset P, while least and greatest elements must belong to S itself.

The selected subset is the same pair of single-tool kits in both panels. The full kit bounds them only in the first poset. The empty kit remains their lower bound in both.

For the four kits and S = {{a}, {b}}, the only upper bound is {a,b} and the only lower bound is ∅. Neither is a member of S. Now remove {a,b} from the ambient poset, leaving P′ = {∅, {a}, {b}} under the same inclusion rule. The same S has no upper bound in P′, although {a,b} is still a perfectly meaningful set outside P′.

In D = {1,2,3,6,12} under divisibility, S = {2,3} has upper bounds 6,12 and lower bound 1. They are not found by comparing numerical height alone: an upper bound must be divisible by both selected integers. The table checks every candidate of the finite D.

A best bound must itself be a bound

A supremum, or least upper bound, supₚ S belongs to P, is an upper bound of S, and is at or below every upper bound of S. An infimum, or greatest lower bound, infₚ S belongs to P, is a lower bound of S, and is at or above every lower bound of S. The subscript reminds us which poset supplies the candidates.

For S = {p,q}, the upper bounds are u,v and the sole lower bound is 0. The two upper bounds are incomparable, so neither is a supremum. An intersecting pair of drawn lines adds no element between p,q and u,v.

For the kits, supₚ {{a},{b}} = {a,b} and infₚ {{a},{b}} = ∅. For D under divisibility, supᴅ {2,3} = 6 because 6 is a common upper bound and divides every other upper bound in D; infᴅ {2,3} = 1. Supremum means least among upper bounds in the order, not the smallest printed label or a guessed average.

Upper bounds can exist without a least one. Consider P = {0,p,q,u,v} whose strict comparisons are 0 ≺ p, 0 ≺ q, p ≺ u, p ≺ v, q ≺ u, q ≺ v, and the transitive comparisons 0 ≺ u, 0 ≺ v. For S = {p,q}, the upper bounds are u,v. Neither is below the other, so there is no supremum. Their minimality inside the upper-bound set does not make either one its least element. The only lower bound is 0, so the infimum is 0.

If two suprema existed, each would be at or below the other because both are upper bounds; antisymmetry makes them equal. The same reasoning proves uniqueness of an infimum. A greatest member of S, when it exists, is its supremum in P: it bounds S, and every upper bound lies above it because it belongs to S. Reverse the reasoning for a least member and its infimum.

Empty and infinite subsets expose the conditions

For S = ∅, every element of P is both an upper and a lower bound: there is no member of S that could violate either condition. Hence supₚ ∅ exists exactly when P has a least element, and it is that least element. Likewise infₚ ∅ exists exactly when P has a greatest element, and it is that greatest element. If P is empty, there is no candidate bound and neither exists.

For an empty selected subset in the four-kit poset, every displayed node has both bound markers. The least node ∅ is its supremum; the greatest node {a,b} is its infimum. These bounds are elements of P, not members of the empty selected subset.

In the four-kit P this gives supₚ ∅ = ∅, the empty kit, and infₚ ∅ = {a,b}, the full kit. The left-hand ∅ denotes an empty subset of the poset; the right-hand ∅ denotes the empty kit, which is one element of P. Read which level of objects each symbol names.

Optional real-interval case: in (ℝ, ≤), S = (0,1) has supremum 1 and infimum 0, though neither endpoint is in S. Every member lies below 1. Any candidate u < 1 fails to bound S: if u ≤ 0, use 1/2; if 0 < u < 1, use (u+1)/2, which lies in S and exceeds u. Thus 1 is an upper bound below every upper bound. The lower-bound argument is dual: any l > 0 fails, using 1/2 when l ≥ 1 and l/2 when 0 < l < 1.

The same S has no upper or lower bound when the ambient poset is ((0,1), ≤): every candidate belongs to S and can be improved within S. A total order need not have a supremum for every subset. Keep existence, membership in the ambient poset, and the best-bound comparison as separate checks.

Worked examples

Try it yourself

1. On distinct a,b,c let R contain exactly (a,b), (b,a), (a,c). Is R symmetric? Is it antisymmetric? Give a witness for each answer.

   Show the answer and reasoning

   R is neither symmetric nor antisymmetric.

   The pair (a,c) has no reverse (c,a), so symmetry fails. The distinct a,b are related both ways, so antisymmetry fails. These are separate conditions; failure of one does not establish the other.

2. On P = {a,b,c}, a relation has every self-pair and the extra pairs (a,b),(b,c), but no other pairs. Is it a partial order?

   Show the answer and reasoning

   No. It is reflexive and antisymmetric, but not transitive.

   The two pairs (a,b) and (b,c) require (a,c) by transitivity, and that pair is absent. The listed distinct pairs have no reverses, so antisymmetry is satisfied. A relation with one missing required shortcut cannot be called a partial order.

3. For the four kits, does ∅ ≺ {a,b} hold? Does {a,b} cover ∅? Explain why the answers differ.

   Show the answer and reasoning

   The strict comparison is true, but the cover claim is false.

   The empty kit is a proper subset of the full kit. Both {a} and {b} are intermediate kits, so a cover edge would be redundant. Strict comparison permits intermediate elements; a cover does not.

4. Are C = {∅,{a,b}} and A = {{a},{b}} a chain or an antichain in the four-kit poset?

   Show the answer and reasoning

   C is a chain and is not an antichain. A is an antichain and is not a chain.

   The empty kit lies below the full kit, even without a direct cover edge. The two single-tool kits are incomparable. Pairwise comparability, rather than the existence of an edge between successive displayed members, defines a chain.

5. In P = {a,b,c} with a ≺ c, b ≺ c and a,b incomparable, find the minimal, maximal, least and greatest elements of the whole P.

   Show the answer and reasoning

   Minimal elements: a,b. Maximal element: c. No least element. Greatest element: c.

   Nothing in P is strictly below a or b. Nothing is strictly above c, and every member is at or below c. Neither a nor b is below the other, so neither is least; c cannot be least because it is above both.

6. For P′ = {∅,{a},{b}} under inclusion and S = {{a},{b}}, find lower and upper bounds in P′ and decide whether infₚ′ S and supₚ′ S exist.

   Show the answer and reasoning

   The lower-bound set is {∅}, with infimum ∅. There are no upper bounds, so no supremum.

   The empty kit is below both single-tool kits. Neither singleton contains the other, and the full kit is not an allowed element of P′. A candidate outside the ambient poset cannot supply a bound there.

7. In the five-node poset 0,p,q,u,v, what are the upper and lower bounds of the empty subset? Which of its supremum and infimum exists?

   Show the answer and reasoning

   Every node is both an upper and lower bound. The supremum of the empty subset is 0, and its infimum does not exist.

   Both bounding conditions quantify over no selected member. The poset’s least element is 0, so it is least among all upper bounds. There is no greatest element because u and v are incomparable maximal nodes, so there is no greatest lower bound of the empty subset.

8. Let S ⊆ P have a greatest member g. Prove that g is supₚ S, retaining both parts of the definition.

   Show the answer and reasoning

   Every s ∈ S satisfies s ⪯ g, so g is an upper bound in P. If u is any upper bound of S, then g ⪯ u because g ∈ S. Thus g is least among upper bounds.

   The second step uses membership g ∈ S, not just maximality. A merely maximal member may be incomparable with another member of S and fail even to be an upper bound. Antisymmetry ensures this supremum is unique.

9. Why is divisibility on all integers not a partial order even though divisibility on positive integers is one?

   Show the answer and reasoning

   Distinct integers 2 and −2 divide each other, violating antisymmetry on ℤ.

   Both −2 = (−1)·2 and 2 = (−1)·(−2) are integer-multiple equations. Positivity had forced the two multipliers in the positive-domain proof to be positive with product 1. Dropping that domain condition removes the antisymmetry conclusion.

What to carry forward

• A poset states both its elements and a reflexive, antisymmetric, transitive non-strict relation. Antisymmetric does not mean not symmetric.
• A total order compares every pair; incomparable elements can still have common bounds. Strict order removes equality and is irreflexive and transitive.
• A finite Hasse diagram displays covers. Equality and upward paths recover the full order; height is an ordering convention, not a numerical scale.
• Chains compare every pair; antichains compare no distinct pair. Extrema are taken in the specified subset, while bounds are sought in its ambient poset.
• Minimal means nobody strictly below; least means below everybody. Least and greatest elements are unique when they exist, but existence requires its own argument.
• A supremum is an upper bound below every upper bound; an infimum is a lower bound above every lower bound. Check the candidates, common poset and empty-subset case before asserting existence.