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