greatest element and least element

Let $(P,\; \backslash leq)$ be a preordered set and let $S\; \backslash subseteq\; P.$

An element $g\; \backslash in\; P$ is said to be {{em|a greatest element of $S$}} if $g\; \backslash in\; S$ and if it also satisfies:

:$s\; \backslash leq\; g$ for all $s\; \backslash in\; S.$

By switching the side of the relation that $s$ is on in the above definition, the definition of a least element of $S$ is obtained. Explicitly, an element $l\; \backslash in\; P$ is said to be {{em|a least element of $S$}} if $l\; \backslash in\; S$ and if it also satisfies:

:$l\; \backslash leq\; s$ for all $s\; \backslash in\; S.$

If $(P,\; \backslash leq)$ is also a partially ordered set then $S$ can have at most one greatest element and it can have at most one least element. Whenever a greatest element of $S$ exists and is unique then this element is called {{em|the}} greatest element of $S$. The terminology {{em|the}} least element of $S$ is defined similarly.

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

Greatest elements are closely related to upper bounds.

Let $(P,\; \backslash leq)$ be a preordered set and let $S\; \backslash subseteq\; P.$

An {{em|upper bound of $S$ in $(P,\; \backslash leq)$}} is an element $u$ such that $u\; \backslash in\; P$ and $s\; \backslash leq\; u$ for all $s\; \backslash in\; S.$ Importantly, an upper bound of $S$ in $P$ is {{em|not}} required to be an element of $S.$

If $g\; \backslash in\; P$ then $g$ is a greatest element of $S$ if and only if $g$ is an upper bound of $S$ in $(P,\; \backslash leq)$ {{em|and}} $g\; \backslash in\; S.$ In particular, any greatest element of $S$ is also an upper bound of $S$ (in $P$) but an upper bound of $S$ in $P$ is a greatest element of $S$ if and only if it {{em|belongs}} to $S.$

In the particular case where $P\; =\; S,$ the definition of "$u$ is an upper bound of $S$ {{em|in $S$}}" becomes: $u$ is an element such that $u\; \backslash in\; S$ and $s\; \backslash leq\; u$ for all $s\; \backslash in\; S,$ which is {{em|completely identical}} to the definition of a greatest element given before.

Thus $g$ is a greatest element of $S$ if and only if $g$ is an upper bound of $S$ {{em|in $S$}}.

If $u$ is an upper bound of $S$ {{em|in $P$}} that is not an upper bound of $S$ {{em|in $S$}} (which can happen if and only if $u\; \backslash not\backslash in\; S$) then $u$ can {{em|not}} be a greatest element of $S$ (however, it may be possible that some other element {{em|is}} a greatest element of $S$).

In particular, it is possible for $S$ to simultaneously {{em|not}} have a greatest element {{em|and}} for there to exist some upper bound of $S$ {{em|in $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.

File:Lattice of the divisibility of 60 narrow 1,2,3,4.svg

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.

Let $(P,\; \backslash leq)$ be a preordered set and let $S\; \backslash subseteq\; P.$

An element $m\; \backslash in\; S$ is said to be a {{em|maximal element of $S$}} if the following condition is satisfied:

:whenever $s\; \backslash in\; S$ satisfies $m\; \backslash leq\; s,$ then necessarily $s\; \backslash leq\; m.$

If $(P,\; \backslash leq)$ is a partially ordered set then $m\; \backslash in\; S$ is a maximal element of $S$ if and only if there does {{em|not}} exist any $s\; \backslash in\; S$ such that $m\; \backslash leq\; s$ and $s\; \backslash neq\; m.$

A {{em|maximal element of $(P,\; \backslash leq)$}} is defined to mean a maximal element of the subset $S\; :=\; P.$

A set can have several maximal elements without having a greatest element.

Like upper bounds and maximal elements, greatest elements may fail to exist.

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.The notion of locality requires the function's domain to be at least a topological space.

The dual terms are minimum and absolute minimum.

Together they are called the absolute extrema.

Similar conclusions hold for least elements.

;Role of (in)comparability in distinguishing greatest vs. maximal elements

One of the most important differences between a greatest element $g$ and a maximal element $m$ of a preordered set $(P,\; \backslash leq)$ has to do with what elements they are comparable to.

Two elements $x,\; y\; \backslash in\; P$ are said to be {{em|comparable}} if $x\; \backslash leq\; y$ or $y\; \backslash leq\; x$; they are called {{em|incomparable}} if they are not comparable.

Because preorders are reflexive (which means that $x\; \backslash leq\; x$ is true for all elements $x$), every element $x$ is always comparable to itself.

Consequently, the only pairs of elements that could possibly be incomparable are {{em|distinct}} pairs.

In general, however, preordered sets (and even directed partially ordered sets) may have elements that are incomparable.

By definition, an element $g\; \backslash in\; P$ is a greatest element of $(P,\; \backslash leq)$ if $s\; \backslash leq\; g,$ for every $s\; \backslash in\; P$; so by its very definition, a greatest element of $(P,\; \backslash leq)$ must, in particular, be comparable to {{em|every}} element in $P.$

This is not required of maximal elements.

Maximal elements of $(P,\; \backslash leq)$ are {{em|not}} required to be comparable to every element in $P.$

This is because unlike the definition of "greatest element", the definition of "maximal element" includes an important {{em|if}} statement.

The defining condition for $m\; \backslash in\; P$ to be a maximal element of $(P,\; \backslash leq)$ can be reworded as:

:For all $s\; \backslash in\; P,$ {{em|IF}} $m\; \backslash leq\; s$ (so elements that are incomparable to $m$ are ignored) then $s\; \backslash leq\; m.$

;Example where all elements are maximal but none are greatest

Suppose that $S$ is a set containing {{em|at least two}} (distinct) elements and define a partial order $\backslash ,\backslash leq\backslash ,$ on $S$ by declaring that $i\; \backslash leq\; j$ if and only if $i\; =\; j.$

If $i\; \backslash neq\; j$ belong to $S$ then neither $i\; \backslash leq\; j$ nor $j\; \backslash leq\; i$ holds, which shows that all pairs of distinct (i.e. non-equal) elements in $S$ are {{em|in}}comparable.

Consequently, $(S,\; \backslash leq)$ can not possibly have a greatest element (because a greatest element of $S$ would, in particular, have to be comparable to {{em|every}} element of $S$ but $S$ has no such element).

However, {{em|every}} element $m\; \backslash in\; S$ is a maximal element of $(S,\; \backslash leq)$ because there is exactly one element in $S$ that is both comparable to $m$ and $\backslash geq\; m,$ that element being $m$ itself (which of course, is $\backslash leq\; m$).Of course, in this particular example, there exists only one element in $S$ that is comparable to $m,$ which is necessarily $m$ itself, so the second condition "and $\backslash geq\; m,$" was redundant.

In contrast, if a preordered set $(P,\; \backslash leq)$ does happen to have a greatest element $g$ then $g$ will necessarily be a maximal element of $(P,\; \backslash leq)$ and moreover, as a consequence of the greatest element $g$ being comparable to {{em|every}} element of $P,$ if $(P,\; \backslash leq)$ is also partially ordered then it is possible to conclude that $g$ is the {{em|only}} maximal element of $(P,\; \backslash leq).$

However, the uniqueness conclusion is no longer guaranteed if the preordered set $(P,\; \backslash leq)$ is {{em|not}} also partially ordered.

For example, suppose that $R$ is a non-empty set and define a preorder $\backslash ,\backslash leq\backslash ,$ on $R$ by declaring that $i\; \backslash leq\; j$ {{em|always}} holds for all $i,\; j\; \backslash in\; R.$ The directed preordered set $(R,\; \backslash leq)$ is partially ordered if and only if $R$ has exactly one element. All pairs of elements from $R$ are comparable and {{em|every}} element of $R$ is a greatest element (and thus also a maximal element) of $(R,\; \backslash leq).$ So in particular, if $R$ has at least two elements then $(R,\; \backslash leq)$ has multiple {{em|distinct}} greatest elements.

Throughout, let $(P,\; \backslash leq)$ be a partially ordered set and let $S\; \backslash subseteq\; P.$

• A set $S$ can have at most {{em|one}} greatest element.If $g\_1$ and $g\_2$ are both greatest, then $g\_1\; \backslash leq\; g\_2$ and $g\_2\; \backslash leq\; g\_1,$ and hence $g\_1\; =\; g\_2$ by antisymmetry. Thus if a set has a greatest element then it is necessarily unique.
• If it exists, then the greatest element of $S$ is an upper bound of $S$ that is also contained in $S.$
• If $g$ is the greatest element of $S$ then $g$ is also a maximal element of $S$If $g$ is the greatest element of $S$ and $s\; \backslash in\; S,$ then $s\; \backslash leq\; g.$ By antisymmetry, this renders ($g\; \backslash leq\; s$ and $g\; \backslash neq\; s$) impossible. and moreover, any other maximal element of $S$ will necessarily be equal to $g.$If $M$ is a maximal element, then $M\; \backslash leq\; g$ since $g$ is greatest, hence $M\; =\; g$ since $M$ is maximal.
• Thus if a set $S$ has several maximal elements then it cannot have a greatest element.
• If $P$ satisfies the ascending chain condition, a subset $S$ of $P$ has a greatest element if, and only if, it has one maximal element.Only if: see above. — If: Assume for contradiction that $S$ has just one maximal element, $m,$ but no greatest element. Since $m$ is not greatest, some $s\_1\; \backslash in\; S$ must exist that is incomparable to $m.$ Hence $s\_1\; \backslash in\; S$ cannot be maximal, that is, must hold for some $s\_2\; \backslash in\; S.$ The latter must be incomparable to $m,$ too, since contradicts $m$'s maximality while $s\_2\; \backslash leq\; m$ contradicts the incomparability of $m$ and $s\_1.$ Repeating this argument, an infinite ascending chain can be found (such that each $s\_i$ is incomparable to $m$ and not maximal). This contradicts the ascending chain condition.
• When the restriction of $\backslash ,\backslash leq\backslash ,$ to $S$ is a total order ($S\; =\; \backslash \{\; 1,\; 2,\; 4\; \backslash \}$ in the topmost picture is an example), then the notions of maximal element and greatest element coincide.Let $m\; \backslash in\; S$ be a maximal element, for any $s\; \backslash in\; S$ either $s\; \backslash leq\; m$ or $m\; \backslash leq\; s.$ In the second case, the definition of maximal element requires that $m\; =\; s,$ so it follows that $s\; \backslash leq\; m.$ In other words, $m$ is a greatest element.
• However, this is not a necessary condition for whenever $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 $S$ of $P,$ then $\backslash ,\backslash leq\backslash ,$ is a total order on $P.$If $a,\; b\; \backslash in\; P$ were incomparable, then $S\; =\; \backslash \{\; a,\; b\; \backslash \}$ would have two maximal, but no greatest element, contradicting the coincidence.

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

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.

File:KeinVerband.svg of example 2]]

• The subset of integers has no upper bound in the set $\backslash mathbb\{R\}$ of real numbers.
• Let the relation $\backslash ,\backslash leq\backslash ,$ on $\backslash \{\; a,\; b,\; c,\; d\; \backslash \}$ be given by $a\; \backslash leq\; c,$ $a\; \backslash leq\; d,$ $b\; \backslash leq\; c,$ $b\; \backslash leq\; d.$ The set $\backslash \{\; a,\; b\; \backslash \}$ has upper bounds $c$ and $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 $\backslash mathbb\{R\},$ the set of numbers less than 1 has a least upper bound, viz. 1, but no greatest element.
• In $\backslash 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 $\backslash mathbb\{R\}^2$ with the product order, the set of pairs $(x,\; y)$ with has no upper bound.
• In $\backslash mathbb\{R\}^2$ with the lexicographical order, this set has upper bounds, e.g. $(1,\; 0).$ It has no least upper bound.

• Essential supremum and essential infimum
• Initial and terminal objects
• Maximal and minimal elements
• Limit superior and limit inferior (infimum limit)
• Upper and lower bounds
• Well-order — a non-strict order such that every non-empty set has a least element

{{reflist|group=note}}

{{reflist}}

• {{cite book | last1=Davey | first1=B. A. | last2=Priestley | first2=H. A. | year = 2002 | title = Introduction to Lattices and Order |title-link= Introduction to Lattices and Order | edition = 2nd | publisher = Cambridge University Press | isbn = 978-0-521-78451-1}}

Category:Order theory

Category:Superlatives