Partially Ordered Sets — Mathematics Knowledge System

Overview

A partially ordered set, or poset, is a set P equipped with a relation ≤ that is reflexive, antisymmetric, and transitive. Unlike a total order, a poset need not compare every pair of elements — divisibility on the integers is a classic example, since neither 4 ≤ 6 nor 6 ≤ 4 holds under 'divides'. Posets are typically visualized with Hasse diagrams, which draw only the covering relations (direct successor edges) and omit both loops and redundant edges implied by transitivity. Central poset concepts include maximal/minimal elements, upper/lower bounds, chains (totally ordered subsets), and antichains (subsets of pairwise incomparable elements).

Intuition

Think of a company's org chart, or the divisibility relation among integers, or the subset relation among sets: some pairs clearly rank one above the other, but many pairs simply aren't comparable at all — a marketing VP and an engineering VP aren't 'above' or 'below' each other, and neither is 4 above or below 6 under divisibility. A poset formalizes exactly this: a consistent notion of 'at least as big/senior/inclusive' that respects transitivity and never contradicts itself, but stops short of forcing every pair into a strict ranking the way a total order (like ≤ on the real numbers) does.

Formal Definition

Definition

A relation ≤ on a set P is a partial order if it satisfies, for all a, b, c ∈ P:

a \le a \quad \text{(reflexivity)}

Reflexive

a \le b \text{ and } b \le a \implies a = b \quad \text{(antisymmetry)}

Antisymmetric

a \le b \text{ and } b \le c \implies a \le c \quad \text{(transitivity)}

Transitive

\exists a, b \in P: a \not\le b \text{ and } b \not\le a \quad \text{(incomparability allowed)}

Not necessarily total

Worked Examples

Check reflexivity: every n divides itself.
$n \mid n \ \forall n$
Check antisymmetry: if a | b and b | a for positive integers, then a = b.
$a \mid b \text{ and } b \mid a \implies a=b$
Check transitivity: if a | b and b | c then a | c. All three hold, so it's a poset. For 4 and 6: 4 does not divide 6, and 6 does not divide 4.
$4 \nmid 6, \ 6 \nmid 4$

Answer: Yes, (ℤ⁺, |) is a poset; 4 and 6 are incomparable.

Practice Problems

Difficulty 2/10

Is the relation ≤ (usual numeric order) on ℝ a total order, a partial order, or both?

Difficulty 3/10

Give an antichain of size 3 in the divisibility poset on {1,...,30}.

Difficulty 4/10

Prove that a finite nonempty poset always has at least one maximal element.

Quiz

Summary

A poset is a set with a reflexive, antisymmetric, transitive relation — comparability of every pair is NOT required.
Divisibility and subset-inclusion are canonical posets; chains are totally ordered subsets, antichains are pairwise incomparable subsets.
Hasse diagrams visualize posets by drawing only covering relations, and every finite nonempty poset has a maximal element.

References

WebsiteWikipedia — Partially ordered set