What is a poset?
The term “poset” is short for “partially ordered set”, that is, a set whose elements
are ordered but not all pairs of elements are required to be comparable in the order.
Just as an order in the usual sense may be strict (as <) or non-strict (as ≤), there
are two versions of the definition of a partial order:
A strict partial order is a binary relation S on a set X satisfying the conditions
(R−) for no x ∈ X does (x, x) ∈ S hold;
(A−) if (x, y) ∈ S, then (y, x) ∈ S;
(T) if (x, y) ∈ S and (y, z) ∈ S, then (x, z) ∈ S.
A non-strict partial order is a binary relation R on a set X satisfying the conditions
(R+) for all x ∈ X we have (x, x) ∈ R;
(A) if (x, y) ∈ R and (y, x) ∈ R then x = y;
(T) if (x, y) ∈ R and (y, z) ∈ R then (x, z) ∈ R.
Condition (A−) appears stronger than (A), but in fact (R−) and (A) imply
(A−). So we can (as is usually done) replace (A−) by (A) in the definition of a
strict partial order. Conditions (R−), (R+), (A), (T) are called irreflexivity, reflex-
ivity, antisymmetry and transitivity respectively.
Properties of posets:
An element x of a poset (X, R) is called maximal if there is no element y ∈ X
satisfying x <R y. Dually, x is minimal if no element satisfies y <R x.
In a general poset there may be no maximal element, or there may be more
than one. But in a finite poset there is always at least one maximal element, which
can be found as follows: choose any element x; if it is not maximal, replace it
by an element y satisfying x <R y; repeat until a maximal element is found. The
process must terminate, since by the irreflexive and transitive laws the chain can
never revisit any element. Dually, a finite poset must contain minimal elements.
An element x is an upper bound for a subset Y of X if y ≤R x for all y ∈ Y .
Lower bounds are defined similarly. We say that x is a least upper bound or l.u.b.
of Y if it is an upper bound and satisfies x ≤R x for any upper bound x . The
concept of a greatest lower bound or g.l.b. is defined similarly.
A chain in a poset (X, R) is a subset C of X which is totally ordered by the
restriction of R (that is, a totally ordered subset of X). An antichain is a set A of
pairwise incomparable elements.
Infinite posets (such as Z), as we remarked, need not contain maximal ele-
ments. Zorn’s Lemma gives a sufficient condition for maximal elements to exist:
Let (X, R) be a poset in which every chain has an upper bound. Then
X contains a maximal element.
As well known, there is no “proof” of Zorn’s Lemma, since it is equivalent
to the Axiom of Choice (and so there are models of set theory in which it is
true, and models in which it is false). Our proof of the existence of maximal
elements in finite posets indicates why this should be so: the construction requires
(in general infinitely many) choices of upper bounds for the elements previously
chosen (which form a chain by construction).
The height of a poset is the largest cardinality of a chain, and its width is the
largest cardinality of an antichain. We denote the height and width of (X, R) by
h(X) and w(X) respectively (suppressing as usual the relation R in the notation).
In a finite poset (X, R), a chain C and an antichain A have at most one element
in common. Hence the least number of antichains whose union is X is not less
than the size h(X) of the largest chain in X. In fact there is a partition of X into
h(X) antichains. To see this, let A1 be the set of maximal elements; by definition
this is an antichain, and it meets every maximal chain. Then let A2 be the set of
maximal elements in X \ A1 , and iterate this procedure to find the other antichains.
