Template:Use American English Template:Short description
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 dually, that is, it is an element of <math>S</math> that is smaller than every other element of <math>S.</math>
DefinitionsEdit
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 Template:Em 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 Template:Em 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 Template:Em greatest element of <math>S</math>. The terminology Template:Em 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 Template:Em (resp. Template:Em) of <math>(P, \leq).</math>
Relationship to upper/lower boundsEdit
Greatest elements are closely related to upper bounds.
Let <math>(P, \leq)</math> be a preordered set and let <math>S \subseteq P.</math> An Template:Em 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 Template:Em 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> Template:Em <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 Template:Em 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> Template:Em" 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 Template:Em 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> Template:Em.
If <math>u</math> is an upper bound of <math>S</math> Template:Em that is not an upper bound of <math>S</math> Template:Em (which can happen if and only if <math>u \not\in S</math>) then <math>u</math> can Template:Em be a greatest element of <math>S</math> (however, it may be possible that some other element Template:Em a greatest element of <math>S</math>). In particular, it is possible for <math>S</math> to simultaneously Template:Em have a greatest element Template:Em for there to exist some upper bound of <math>S</math> Template:Em.
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 maximumsEdit
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 Template:Em 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 Template:Em exist any <math>s \in S</math> such that <math>m \leq s</math> and <math>s \neq m.</math> A Template:Em 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 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 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 Template:Em if <math>x \leq y</math> or <math>y \leq x</math>; they are called Template:Em if they are not comparable. Because preorders are 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 Template:Em pairs. In general, however, preordered sets (and even 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 Template:Em element in <math>P.</math> This is not required of maximal elements. Maximal elements of <math>(P, \leq)</math> are Template:Em 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 Template:Em 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> Template:Em <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 Template:Em (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 Template:Emcomparable. 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 Template:Em element of <math>S</math> but <math>S</math> has no such element). However, Template:Em 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 Template:Em 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 Template:Em maximal element of <math>(P, \leq).</math> However, the uniqueness conclusion is no longer guaranteed if the preordered set <math>(P, \leq)</math> is Template:Em 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> Template:Em holds for all <math>i, j \in R.</math> The 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 Template:Em 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 Template:Em greatest elements.
PropertiesEdit
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 Template:Em 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. — 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 conditionsEdit
- A finite chain always has a greatest and a least element.
Top and bottomEdit
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.
ExamplesEdit
- The subset of integers has no upper bound in the set <math>\mathbb{R}</math> of real numbers.
- 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 numbers, 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 alsoEdit
- 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