Special Elements of Partially Ordered Sets

In this topic we consider elements of partially ordered set that have certain extremal properties.

Maximal and Minimal Elements

Let (A, ≼) be a partially ordered set (poset). An element a ∈ (A, ≼) is called maximal if there is no other element b ∈ A such that a ≺ b. That is, an element a is maximal if it has no immediate successor.

In a Hasse diagram, a vertex corresponds to a maximal element if there is no edge leaving the vertex.

Similarly, we define a minimal element in a poset A. An element a ∈ (A, ≼) is called minimal if there is no other element b ∈ A such that b ≺ a. In other words, an element a is minimal if it has no immediate predecessor.

In a Hasse diagram, a vertex corresponds to a minimal element if there is no edge entering the vertex.

A partially ordered set may have one or many maximal or minimal elements.

Greatest and Least Elements

An element \(a \in {\left( {A, \preccurlyeq } \right)}\) is called the greatest (maximum) element if it is greater than every other element of the poset:

An element \(a \in {\left( {A, \preccurlyeq } \right)}\) is called the least (minimum) element if it is less than every other element of the poset:

The greatest and least elements are unique when they exist.

In a Hasse diagram, a vertex corresponds to the greatest element if there is a downward path from this vertex to any other vertex. Respectively, a vertex corresponds to the least element if there is an upward path from this vertex to any other vertex.

As an example, the poset \(\left( {\mathcal{P}\left( {\left\{ {a,b,c} \right\}} \right),\subseteq} \right),\) where \(\mathcal{P}\) denotes the power set, the greatest element is \({\left\{ {a,b,c} \right\}}\) and the least element is \(\varnothing.\)

If \(A\) has a greatest element, it is also a maximal element of \(A.\) However, the converse if false: a set \(A\) can have a unique maximal element that is not the greatest element of \(A.\)

Upper and Lower Bounds

Let \(S\) be a non-empty subset of \(A\) in the partially ordered set \(\left( {A, \preccurlyeq } \right).\)

If there is an element \(u \in A\) such that

then \(u\) is called an upper bound (or majorant) of \(S.\)

Likewise, if there is an element \(\ell \in A\) such that

then \(\ell\) is called a lower bound (or minorant) of \(S.\)

In a Hasse diagram, the upper bounds of a subset \(S \subseteq A\) are all those vertices in \(A\) that have a downward path to all vertices in the subset \(S.\) Respectively, the lower bounds of a subset \(S \subseteq A\) are all those vertices in \(A\) that have an upward path to all vertices in \(S.\)

As an example, consider a poset \(\left( {A, \preccurlyeq } \right)\) with the following Hasse diagram:

For the subset \(S = \left\{ {d,f,g} \right\},\) the upper bounds are the elements \(h\) and \(k,\) and the lower bounds are the elements \(a, b, d.\)

This example shows that an upper or least bound of a subset may either belong to the subset or not belong to it.

Least Upper and Greatest Lower Bounds

Consider again a subset \(S \subseteq A\) of a poset \(\left( {A, \preccurlyeq } \right).\)

If there is a least element is the set of upper bounds of \(S,\) it is called the least upper bound or supremum of \(S,\) and is denoted by \(LUB\left( S \right)\) or \(\sup\left( S \right).\)

Similarly, if there is a greatest element amongst the lower bounds of \(S,\) it is called the greatest lower bound or infimum of \(S,\) and is denoted by \(GLB\left( S \right)\) or \(\inf\left( S \right).\)

The least upper bound and the greatest lower bound do not always exist. However, if they exist, they are unique.

For the poset \(\left( {A, {\preccurlyeq}_1 } \right)\) and subset \(S = \left\{ {c,d} \right\}\) shown in Figure \(4,\) the least upper bound is the element \(e,\) and the greatest lower bound is the element \(b.\)

In a similar poset \(\left( {A, {\preccurlyeq}_2 } \right),\) the subset \(S = \left\{ {c,d} \right\}\) has neither a least upper bound, nor a greatest lower bound (Figure \(5\)).

The elements \(e\) and \(f\) are the upper bounds of \(S\) in the poset \(\left( {A, {\preccurlyeq}_2 } \right).\) However, they are not comparable, so we cannot identify the least element among them. Similarly for the lower bounds \(a\) and \(b.\)