Greatest element and least element

In mathematics, especially in order theory, the greatest element of a subset ${\displaystyle S}$ of a partially ordered set (poset) is an element of ${\displaystyle S}$ that is greater than every other element of ${\displaystyle S.}$ The term least element is defined dually, that is, it is an element of ${\displaystyle S}$ that is smaller than every other element of ${\displaystyle S.}$

Hasse diagram of the set ${\displaystyle P}$ of divisors of 60, partially ordered by the relation "${\displaystyle x}$ divides ${\displaystyle y}$". The red subset ${\displaystyle S=\{1,2,3,4\}}$ has two maximal elements, viz. 3 and 4, and one minimal element, viz. 1, which is also its least element.

Definitions

Let ${\displaystyle (P,\leq )}$ be a preordered set and let ${\displaystyle S\subseteq P.}$ An element ${\displaystyle g\in P}$ is said to be a greatest element of ${\displaystyle S}$ if ${\displaystyle g\in S}$ and if it also satisfies

${\displaystyle s\leq g}$ for all ${\displaystyle s\in S.}$

If ${\displaystyle S}$ has a greatest element and if ${\displaystyle (P,\leq )}$ is a partially ordered set then it is necessarily unique and so it is called the greatest element of ${\displaystyle S}$.

By using ${\displaystyle \,\geq \,}$ instead of ${\displaystyle \,\leq \,}$ in the above definition, one defines the least element of ${\displaystyle S.}$ Explicitly, an element ${\displaystyle l\in P}$ is said to be a least element of ${\displaystyle S}$ if ${\displaystyle l\in S}$ and if it also satisfies

${\displaystyle l\leq s}$ for all ${\displaystyle s\in S.}$

If ${\displaystyle (P,\leq )}$ has a greatest element (resp. a least element) then this element is also called a top (resp. a bottom) of ${\displaystyle (P,\leq ).}$

Relationship to upper/lower bounds

Greatest elements are closely related to upper bounds.

Let ${\displaystyle (P,\leq )}$ be a preordered set and let ${\displaystyle S\subseteq P.}$ An upper bound of ${\displaystyle S}$ in ${\displaystyle (P,\leq )}$ is an element ${\displaystyle u}$ such that ${\displaystyle u\in P}$ and ${\displaystyle s\leq u}$ for all ${\displaystyle s\in S.}$ Importantly, an upper bound of ${\displaystyle S}$ in ${\displaystyle P}$ is not required to be an element of ${\displaystyle S.}$

If ${\displaystyle g\in P}$ then ${\displaystyle g}$ is a greatest element of ${\displaystyle S}$ if and only if ${\displaystyle g}$ is an upper bound of ${\displaystyle S}$ in ${\displaystyle (P,\leq )}$ and ${\displaystyle g\in S.}$ In particular, any greatest element of ${\displaystyle S}$ is also an upper bound of ${\displaystyle S}$ (in ${\displaystyle P}$) but an upper bound of ${\displaystyle S}$ in ${\displaystyle P}$ is a greatest element of ${\displaystyle S}$ if and only if it belongs to ${\displaystyle S.}$ In the particular case where ${\displaystyle P=S,}$ the definition of "${\displaystyle u}$ is an upper bound of ${\displaystyle S}$ in ${\displaystyle S}$" becomes: ${\displaystyle u}$ is an element such that ${\displaystyle u\in S}$ and ${\displaystyle s\leq u}$ for all ${\displaystyle s\in S,}$ which is completely identical to the definition of a greatest element given before. Thus ${\displaystyle g}$ is a greatest element of ${\displaystyle S}$ if and only if ${\displaystyle g}$ is an upper bound of ${\displaystyle S}$ in ${\displaystyle S}$.

If ${\displaystyle u}$ is an upper bound of ${\displaystyle S}$ in ${\displaystyle P}$ that is not an upper bound of ${\displaystyle S}$ in ${\displaystyle S}$ (which can happen if and only if ${\displaystyle u\not \in S}$) then ${\displaystyle u}$ can not be a greatest element of ${\displaystyle S}$ (however, it may be possible that some other element is a greatest element of ${\displaystyle S}$). In particular, it is possible for ${\displaystyle S}$ to simultaneously not have a greatest element and for there to exist some upper bound of ${\displaystyle S}$ in ${\displaystyle P}$.

Even if a set has some upper bounds, it need not have a greatest element, as shown by the example of the negative real numbers. This example also demonstrates that the existence of a least upper bound (the number 0 in this case) does not imply the existence of a greatest element either.

Contrast to maximal elements and local/absolute maximums

A greatest element of a subset of a preordered set should not be confused with a maximal element of the set, which are elements that are not strictly smaller than any other element in the set. A set can have several maximal elements without having a greatest element. Like upper bounds and maximal elements, greatest elements may fail to exist.

Let ${\displaystyle (P,\leq )}$ be a partially ordered set and let ${\displaystyle S\subseteq P.}$ An element ${\displaystyle m\in S}$ is said to be a maximal element of ${\displaystyle S}$ if whenever ${\displaystyle s\in S}$ satisfies ${\displaystyle m\leq s,}$ then necessarily ${\displaystyle s\leq m.}$ If ${\displaystyle (P,\leq )}$ is a partially ordered set then ${\displaystyle m\in S}$ is a maximal element of ${\displaystyle S}$ if and only if there does not exist any ${\displaystyle s\in S}$ such that ${\displaystyle m\leq s}$ and ${\displaystyle s\neq m.}$

In a totally ordered set the maximal element and the greatest element coincide; and it is also called maximum; in the case of function values it is also called the absolute maximum, to avoid confusion with a local maximum.[1] The dual terms are minimum and absolute minimum. Together they are called the absolute extrema.

Similar conclusions hold for least elements.

Properties

Throughout, let ${\displaystyle (P,\leq )}$ be a partially ordered set and let ${\displaystyle S\subseteq P.}$

• A set ${\displaystyle S}$ can have at most one greatest element.[note 1] Thus if a set has a greatest element then it is necessarily unique.
• If it exists, then the greatest element of ${\displaystyle S}$ is an upper bound of ${\displaystyle S}$ that is also contained in ${\displaystyle S.}$
• If ${\displaystyle g}$ is the greatest element of ${\displaystyle S}$ then ${\displaystyle g}$ is also a maximal element of ${\displaystyle S}$[note 2] and moreover, any other maximal element of ${\displaystyle S}$ will necessarily be equal to ${\displaystyle g.}$[note 3]
  • Thus if a set ${\displaystyle S}$ has several maximal elements then it cannot have a greatest element.
• If ${\displaystyle P}$ satisfies the ascending chain condition, a subset ${\displaystyle S}$ of ${\displaystyle P}$ has a greatest element if, and only if, it has one maximal element.[note 4]
• When the restriction of ${\displaystyle \,\leq \,}$ to ${\displaystyle S}$ is a total order (${\displaystyle S=\{1,2,4\}}$ in the topmost picture is an example), then the notions of maximal element and greatest element coincide.[note 5]
  • However, this is not a necessary condition for whenever ${\displaystyle S}$ has a greatest element, the notions coincide, too, as stated above.
• If the notions of maximal element and greatest element coincide on every two-element subset ${\displaystyle S}$ of ${\displaystyle P,}$ then ${\displaystyle \,\leq \,}$ is a total order on ${\displaystyle P.}$[note 6]

Sufficient conditions

• A finite chain always has a greatest and a least element.

Top and bottom

The least and greatest element of the whole partially ordered set play a special role and are also called bottom (⊥) and top (⊤), or zero (0) and unit (1), respectively. If both exist, the poset is called a bounded poset. The notation of 0 and 1 is used preferably when the poset is a complemented lattice, and when no confusion is likely, i.e. when one is not talking about partial orders of numbers that already contain elements 0 and 1 different from bottom and top. The existence of least and greatest elements is a special completeness property of a partial order.

Further introductory information is found in the article on order theory.

Examples

Hasse diagram of example 2

• The subset of integers has no upper bound in the set ${\displaystyle \mathbb {R} }$ of real numbers.
• Let the relation ${\displaystyle \,\leq \,}$ on ${\displaystyle \{a,b,c,d\}}$ be given by ${\displaystyle a\leq c,}$ ${\displaystyle a\leq d,}$ ${\displaystyle b\leq c,}$ ${\displaystyle b\leq d.}$ The set ${\displaystyle \{a,b\}}$ has upper bounds ${\displaystyle c}$ and ${\displaystyle d,}$ but no least upper bound, and no greatest element (cf. picture).
• In the rational numbers, the set of numbers with their square less than 2 has upper bounds but no greatest element and no least upper bound.
• In ${\displaystyle \mathbb {R} ,}$ the set of numbers less than 1 has a least upper bound, viz. 1, but no greatest element.
• In ${\displaystyle \mathbb {R} ,}$ the set of numbers less than or equal to 1 has a greatest element, viz. 1, which is also its least upper bound.
• In ${\displaystyle \mathbb {R} ^{2}}$ with the product order, the set of pairs ${\displaystyle (x,y)}$ with ${\displaystyle 0<x<1}$ has no upper bound.
• In ${\displaystyle \mathbb {R} ^{2}}$ with the lexicographical order, this set has upper bounds, e.g. ${\displaystyle (1,0).}$ It has no least upper bound.

See also

• Essential supremum and essential infimum
• Initial and terminal objects
• Maximal and minimal elements
• Limit superior and limit inferior (infimum limit)
• Upper and lower bounds

Notes

1. If ${\displaystyle g_{1}}$ and ${\displaystyle g_{2}}$ are both greatest, then ${\displaystyle g_{1}\leq g_{2}}$ and ${\displaystyle g_{2}\leq g_{1},}$ and hence ${\displaystyle g_{1}=g_{2}}$ by antisymmetry.
2. If ${\displaystyle g}$ is the greatest element of ${\displaystyle S}$ and ${\displaystyle s\in S,}$ then ${\displaystyle s\leq g.}$ By antisymmetry, this renders (${\displaystyle g\leq s}$ and ${\displaystyle g\neq s}$) impossible.
3. If ${\displaystyle M}$ is a maximal element, then ${\displaystyle M\leq g}$ since ${\displaystyle g}$ is greatest, hence ${\displaystyle M=g}$ since ${\displaystyle M}$ is maximal.
4. Only if: see above. — If: Assume for contradiction that ${\displaystyle S}$ has just one maximal element, ${\displaystyle m,}$ but no greatest element. Since ${\displaystyle m}$ is not greatest, some ${\displaystyle s_{1}\in S}$ must exist that is incomparable to ${\displaystyle m.}$ Hence ${\displaystyle s_{1}\in S}$ cannot be maximal, that is, ${\displaystyle s_{1}<s_{2}}$ must hold for some ${\displaystyle s_{2}\in S.}$ The latter must be incomparable to ${\displaystyle m,}$ too, since ${\displaystyle m<s_{2}}$ contradicts ${\displaystyle m}$'s maximality while ${\displaystyle s_{2}\leq m}$ contradicts the incomparability of ${\displaystyle m}$ and ${\displaystyle s_{1}.}$ Repeating this argument, an infinite ascending chain ${\displaystyle s_{1}<s_{2}<\cdots <s_{n}<\cdots }$ can be found (such that each ${\displaystyle s_{i}}$ is incomparable to ${\displaystyle m}$ and not maximal). This contradicts the ascending chain condition.
5. Let ${\displaystyle m\in S}$ be a maximal element, for any ${\displaystyle s\in S}$ either ${\displaystyle s\leq m}$ or ${\displaystyle m\leq s.}$ In the second case, the definition of maximal element requires that ${\displaystyle m=s,}$ so it follows that ${\displaystyle s\leq m.}$ In other words, ${\displaystyle m}$ is a greatest element.
6. If ${\displaystyle a,b\in P}$ were incomparable, then ${\displaystyle S=\{a,b\}}$ would have two maximal, but no greatest element, contradicting the coincidence.

References

1. The notion of locality requires the function's domain to be at least a topological space.

• Davey, B. A.; Priestley, H. A. (2002). Introduction to Lattices and Order (2nd ed.). Cambridge University Press. ISBN 978-0-521-78451-1.