poset (GATE-2012)

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.