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

Maximal and Minimal Elements

Let \(\require{AMSsymbols}{\left( {A, \preccurlyeq } \right)}\) be a partially ordered set (poset). An element \(a \in \left( {A, \preccurlyeq } \right)\) is called maximal if there is no other element \(b \in A\) such that \(a \prec 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 \in \left( {A, \preccurlyeq } \right)\) is called minimal if there is no other element \(b \in A\) such that \(b \prec 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:

\[b \preccurlyeq a \;\forall \; b \in A.\]

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:

\[a \preccurlyeq b \;\forall \; b \in A.\]

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

\[s \preccurlyeq u \;\forall\; s \in S,\]

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

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

\[\ell \preccurlyeq s \;\forall\; s \in S,\]

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.\)

Solved Problems

Click or tap a problem to see the solution.

Example 1

Given the set \[A = \left\{ {2,3,4,5,8,10,12,24,30} \right\}\] and the divisibility relation on it.

1. Find the maximal elements.
2. Find the minimal elements.
3. Is there a greatest element in the poset?
4. Is there a least element in the poset?
5. Find all upper bounds of \(\left\{ {8,12} \right\}.\)
6. Find all lower bounds of \(\left\{ {8,12} \right\}.\)
7. What is the least upper bound of \(\left\{ {4,8} \right\}?\)
8. What is the greatest lower bound of \(\left\{ {4,8} \right\}?\)

Example 2

Given the set \[B = \left\{ {2,4,6,8,10,30,60,120,240} \right\}\] and the divisibility relation on it.

1. Find the maximal elements.
2. Find the minimal elements.
3. Is there a greatest element in the poset?
4. Is there a least element in the poset?
5. Find all upper bounds of \(\left\{ {30,60} \right\}.\)
6. Find all lower bounds of \(\left\{ {30,60} \right\}.\)
7. What is the least upper bound of the subset \(\left\{ {8,30,60} \right\}?\)
8. What is the greatest lower bound of the subset \(\left\{ {8,30,60} \right\}?\)

Example 3

A poset is given by the Hasse diagram

Find the upper and lower bounds of the following subsets:

1. \(\left\{ {d,f} \right\}\)
2. \(\left\{ {e,f,g} \right\}\)
3. \(\left\{ {h,i} \right\}\)

Example 4

A poset is represented by the Hasse diagram

Find the upper and lower bounds of the following subsets:

1. \(\left\{ {e,f} \right\}\)
2. \(\left\{ {f,h} \right\}\)
3. \(\left\{ {e,h} \right\}\)

Example 5

The poset \(\left( {A,\subseteq} \right)\) includes the elements: \[\varnothing,\left\{ 2 \right\},\left\{ {3} \right\},\left\{ {4} \right\},\left\{ {1,3} \right\},\left\{ {2,3} \right\},\left\{ {2,4} \right\},\left\{ {1,2,3} \right\},\left\{ {2,3,4} \right\},\left\{ {1,2,3,4} \right\}.\] Find the greatest lower bound and the least upper bound of the following subsets of \(A:\)

1. \(\left\{ {\left\{ {1,3} \right\},\left\{ {2,4} \right\}} \right\}\)
2. \(\left\{ {\left\{ {1,2,3} \right\},\left\{ {2,3,4} \right\}} \right\}\)

Example 6

The poset \(\left( {B,\subseteq} \right)\) contains the elements: \[\left\{ 1 \right\},\left\{ {3} \right\},\left\{ {4} \right\},\left\{ {1,2} \right\},\left\{ {2,3} \right\},\left\{ {3,4} \right\},\left\{ {1,2,3} \right\},\left\{ {2,3,4} \right\},\left\{ {1,2,3,4} \right\}.\] Find the greatest lower bound and the least upper bound of the following subsets of \(B:\)

1. \(\left\{ {\left\{ {1,2} \right\},\left\{ {3,4} \right\}} \right\}\)
2. \(\left\{ {\left\{ {3} \right\},\left\{ {2,3} \right\}} \right\}\)

Solution.

We first draw the Hasse diagram for the poset \(\left( {A,\mid} \right):\)

Determine the extremal elements:

1. The maximal elements are \(24,30.\)
2. The minimal elements are \(2,3,5.\)
3. The greatest element does not exist.
4. The least element does not exist.
5. There is one upper bound for the subset \(\left\{ {8,12} \right\}:\) \(24.\)
6. The lower bounds of the subset \(\left\{ {8,12} \right\}\) are \(2,4.\)
7. The least upper bound of \(\left\{ {4,8} \right\}\) is \(4\) (the smallest element of the upper bounds \(8\) and \(24\)).
8. The greatest lower bound of \(\left\{ {4,8} \right\}\) is \(4\) (the largest element of the lower bounds \(2\) and \(4\)).

Solution.

The Hasse diagram of this poset is shown in Figure \(7.\)

Find the special elements in \(\left( {B, \mid } \right)\):

1. The maximal element is \(240.\)
2. The minimal element is \(2.\)
3. The greatest element exists and is equal to \(240.\)
4. The least element exists and is equal to \(2.\)
5. The upper bounds of the subset \(\left\{ {30,60} \right\}\) are \(120\) and \(240.\)
6. The lower bounds of \(\left\{ {30,60} \right\}\) are \(2,10.\)
7. The least upper bound of the subset \(\left\{ {8,30,60} \right\}\) is \(120\) (the smallest element among the upper bounds \(120\) and \(240\)).
8. The greatest lower bound of \(\left\{ {8,30,60} \right\}\) is \(2\) (this subset has only one lower bound).

Solution.

1. The upper bounds of \(\left\{ {d,f} \right\}\) are \(f,g,h,i,j,k.\) The lower bounds are \(a,b,d.\)
2. The subset \(\left\{ {e,f,g} \right\}\) does not have an upper bound. Its lower bound is \(b.\)
3. The upper bounds of \(\left\{ {h,i} \right\}\) are the elements \(i,k.\) The lower bounds are \(a,b,d,f.\)

Solution.

1. The upper bounds of the subset \(\left\{ {e,f} \right\}\) are \(g,i,j,k.\) The lower bound is \(c.\)
2. The upper bounds of \(\left\{ {f,h} \right\}\) are the elements \(h,\ell.\) The lower bounds are \(b,c,d,f.\)
3. The subset \(\left\{ {e,h} \right\}\) does not have an upper bound. The lower bound is the element \(c.\)

Solution.

We draw a Hasse diagram of the poset:

1. The greatest lower bound (glb) of \(\left\{ {\left\{ {1,3} \right\},\left\{ {2,4} \right\}} \right\}\) is \(\varnothing.\) The least upper bound (lub) of the subset is \(\left\{ {1,2,3,4} \right\}.\)
2. The glb of \(\left\{ {\left\{ {1,2,3} \right\},\left\{ {2,3,4} \right\}} \right\}\) is the element \(\left\{ {2,3} \right\}\) (the largest element among the lower bounds \(\varnothing,\) \(\left\{ {2} \right\},\) \(\left\{ {3} \right\},\) and \(\left\{ {2,3} \right\}.\) The lub of \(\left\{ {\left\{ {1,2,3} \right\},\left\{ {2,3,4} \right\}} \right\}\) is \(\left\{ {1,2,3,4} \right\}.\)

Solution.

To determine the extremal elements, it is convenient to use a Hasse diagram of the poset:

1. The subset \(\left\{ {\left\{ {1,2} \right\},\left\{ {3,4} \right\}} \right\}\) does not have a greatest lower bound (glb). The least upper bound (lub) of the subset is the top element \(\left\{ {1,2,3,4} \right\}.\)
2. The glb of \(\left\{ {\left\{ {3} \right\},\left\{ {2,3} \right\}} \right\}\) is equal to \(3.\) The upper bounds of the subset are \(\left\{ {1,2,3} \right\},\) \(\left\{ {2,3,4} \right\},\) and \(\left\{ {1,2,3,4} \right\}.\) However, the subset \(\left\{ {\left\{ {3} \right\},\left\{ {2,3} \right\}} \right\}\) does not have a lub since the elements \(\left\{ {1,2,3} \right\}\) and \(\left\{ {2,3,4} \right\}\) are incomparable.