# Calculus

## Set Theory # 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 $$\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\}$$

### 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\}?$$

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

### 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\}?$$

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

### 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\}$$

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.$$

### 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\}$$

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.$$

### 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\}$$

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\}.$$

### 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.

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.