Editing Greatest element and least element

{{Use American English|date = March 2019}}
{{Short description|Element ≥ (or ≤) each other element}}

[[File:Lattice of the divisors of 60, ordered by divisibility; with divisors of 30 in red.svg|thumb|[[Hasse diagram]] of the set <math>P</math> of [[divisor]]s of 60, partially ordered by the relation "<math>x</math> divides <math>y</math>". The red subset <math>S = \{ 1, 2, 3, 5, 6, 10, 15, 30 \}</math> has one greatest element, viz. 30, and one least element, viz. 1. These elements are also [[maximal and minimal elements]], respectively, of the red subset.]]

In [[mathematics]], especially in [[order theory]], the '''greatest element''' of a subset <math>S</math> of a [[partially ordered set]] (poset) is an element of <math>S</math> that is greater than every other element of <math>S</math>. The term '''least element''' is defined [[duality (order theory)|dually]], that is, it is an element of <math>S</math> that is smaller than every other element of <math>S.</math>

== Definitions ==

Let <math>(P, \leq)</math> be a [[preordered set]] and let <math>S \subseteq P.</math> 
An element <math>g \in P</math> is said to be {{em|a '''greatest element of <math>S</math>'''}} if <math>g \in S</math> and if it also satisfies: 
:<math>s \leq g</math> for all <math>s \in S.</math>

By switching the side of the relation that <math>s</math> is on in the above definition, the definition of a least element of <math>S</math> is obtained. Explicitly, an element <math>l \in P</math> is said to be {{em|a '''least element of <math>S</math>'''}} if <math>l \in S</math> and if it also satisfies: 
:<math>l \leq s</math> for all <math>s \in S.</math> 

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

If <math>(P, \leq)</math> has a greatest element (resp. a least element) then this element is also called {{em|a '''top'''}} (resp. {{em|a '''bottom'''}}) of <math>(P, \leq).</math> 

=== Relationship to upper/lower bounds ===

Greatest elements are closely related to [[upper bound]]s. 

Let <math>(P, \leq)</math> be a [[preordered set]] and let <math>S \subseteq P.</math> 
An '''{{em|[[Upper and lower bounds|upper bound]] of <math>S</math> in <math>(P, \leq)</math>}}''' is an element <math>u</math> such that <math>u \in P</math> and  <math>s \leq u</math> for all <math>s \in S.</math> Importantly, an upper bound of <math>S</math> in <math>P</math> is {{em|not}} required to be an element of <math>S.</math> 

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

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

Even if a set has some upper bounds, it need not have a greatest element, as shown by the example of the negative [[real number]]s. 
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 ===
[[File:Lattice of the divisibility of 60 narrow 1,2,3,4.svg|thumb|In the above divisibility order, the red subset <math>S = \{ 1, 2, 3, 4 \}</math> has two maximal elements, viz. 3 and 4, none of which is greatest. It has one minimal element, viz. 1, which is also its least element.]]

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 <math>(P, \leq)</math> be a [[preordered set]] and let <math>S \subseteq P.</math> 
An element <math>m \in S</math> is said to be a '''{{em|[[maximal element]] of <math>S</math>}}''' if the following condition is satisfied:

:whenever <math>s \in S</math> satisfies <math>m \leq s,</math> then necessarily <math>s \leq m.</math> 

If <math>(P, \leq)</math> is a [[partially ordered set]] then <math>m \in S</math> is a maximal element of <math>S</math> if and only if there does {{em|not}} exist any <math>s \in S</math> such that <math>m \leq s</math> and <math>s \neq m.</math> 
A {{em|maximal element of <math>(P, \leq)</math>}} is defined to mean a maximal element of the subset <math>S := P.</math> 

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 [[Total order|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]].<ref>The notion of locality requires the function's domain to be at least a [[topological space]].</ref> 
The dual terms are '''minimum''' and '''absolute minimum'''. 
Together they are called the '''[[Extreme value|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 <math>g</math> and a maximal element <math>m</math> of a preordered set <math>(P, \leq)</math> has to do with what elements they are comparable to. 
Two elements <math>x, y \in P</math> are said to be {{em|comparable}} if <math>x \leq y</math> or <math>y \leq x</math>; they are called {{em|incomparable}} if they are not comparable. 
Because preorders are [[Reflexive relation|reflexive]] (which means that <math>x \leq x</math> is true for all elements <math>x</math>), every element <math>x</math> 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 set|directed]] partially ordered sets) may have elements that are incomparable. 

By definition, an element <math>g \in P</math> is a greatest element of <math>(P, \leq)</math> if <math>s \leq g,</math> for every <math>s \in P</math>; so by its very definition, a greatest element of <math>(P, \leq)</math> must, in particular, be comparable to {{em|every}} element in <math>P.</math> 
This is not required of maximal elements. 
Maximal elements of <math>(P, \leq)</math> are {{em|not}} required to be comparable to every element in <math>P.</math> 
This is because unlike the definition of "greatest element", the definition of "maximal element" includes an important {{em|if}} statement. 
The defining condition for <math>m \in P</math> to be a maximal element of <math>(P, \leq)</math> can be reworded as: 

:For all <math>s \in P,</math> '''{{em|IF}}''' <math>m \leq s</math> (so elements that are incomparable to <math>m</math> are ignored) then <math>s \leq m.</math> 

;Example where all elements are maximal but none are greatest

Suppose that <math>S</math> is a set containing {{em|at least two}} (distinct) elements and define a partial order <math>\,\leq\,</math> on <math>S</math> by declaring that <math>i \leq j</math> if and only if <math>i = j.</math> 
If <math>i \neq j</math> belong to <math>S</math> then neither <math>i \leq j</math> nor <math>j \leq i</math> holds, which shows that all pairs of distinct (i.e. non-equal) elements in <math>S</math> are {{em|in}}comparable. 
Consequently, <math>(S, \leq)</math> can not possibly have a greatest element (because a greatest element of <math>S</math> would, in particular, have to be comparable to {{em|every}} element of <math>S</math> but <math>S</math> has no such element). 
However, {{em|every}} element <math>m \in S</math> is a maximal element of <math>(S, \leq)</math> because there is exactly one element in <math>S</math> that is both comparable to <math>m</math> and <math>\geq m,</math> that element being <math>m</math> itself (which of course, is <math>\leq m</math>).<ref group=note>Of course, in this particular example, there exists only one element in <math>S</math> that is comparable to <math>m,</math> which is necessarily <math>m</math> itself, so the second condition "and <math>\geq m,</math>" was redundant.</ref>

In contrast, if a [[preordered set]] <math>(P, \leq)</math> does happen to have a greatest element <math>g</math> then <math>g</math> will necessarily be a maximal element of <math>(P, \leq)</math> and moreover, as a consequence of the greatest element <math>g</math> being comparable to {{em|every}} element of <math>P,</math> if <math>(P, \leq)</math> is also partially ordered then it is possible to conclude that <math>g</math> is the {{em|only}} maximal element of <math>(P, \leq).</math> 
However, the uniqueness conclusion is no longer guaranteed if the preordered set <math>(P, \leq)</math> is {{em|not}} also partially ordered. 
For example, suppose that <math>R</math> is a non-empty set and define a preorder <math>\,\leq\,</math> on <math>R</math> by declaring that <math>i \leq j</math> {{em|always}} holds for all <math>i, j \in R.</math> The [[Directed set|directed]] preordered set <math>(R, \leq)</math> is partially ordered if and only if <math>R</math> has exactly one element. All pairs of elements from <math>R</math> are comparable and {{em|every}} element of <math>R</math> is a greatest element (and thus also a maximal element) of <math>(R, \leq).</math> So in particular, if <math>R</math> has at least two elements then <math>(R, \leq)</math> has multiple {{em|distinct}} greatest elements.

== Properties ==

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

== Sufficient conditions ==
* A finite [[chain (order theory)|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 (order theory)|completeness property]] of a partial order.

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

== Examples ==

[[File:KeinVerband.svg|thumb|upright=0.5|[[Hasse diagram]] of example 2]]
* The subset of [[integer]]s has no upper bound in the set <math>\mathbb{R}</math> of [[real number]]s.
* Let the relation <math>\,\leq\,</math> on <math>\{ a, b, c, d \}</math> be given by <math>a \leq c,</math> <math>a \leq d,</math> <math>b \leq c,</math> <math>b \leq d.</math> The set <math>\{ a, b \}</math> has upper bounds <math>c</math> and <math>d,</math> but no least upper bound, and no greatest element (cf. picture).
* In the [[rational number]]s, the set of numbers with their square less than 2 has upper bounds but no greatest element and no least upper bound.
* In <math>\mathbb{R},</math> the set of numbers less than 1 has a least upper bound, viz. 1, but no greatest element.
* In <math>\mathbb{R},</math> the set of numbers less than or equal to 1 has a greatest element, viz. 1, which is also its least upper bound.
* In <math>\mathbb{R}^2</math> with the [[product order]], the set of pairs <math>(x, y)</math> with <math>0 < x < 1</math> has no upper bound.
* In <math>\mathbb{R}^2</math> with the [[lexicographical order]], this set has upper bounds, e.g. <math>(1, 0).</math> 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]]
* [[Well-order]] &mdash; a non-strict order such that every non-empty set has a least element

== Notes ==
{{reflist|group=note}}

== References ==
{{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]]