Greatest element and least element
In mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set (poset) is an element of S that is greater than every other element of S. The term least element is defined dually, that is, it is an element of S that is smaller than every other element of S.
Definitions
Let (P, ≤) be a preordered set and let S ⊆ P. An element g ∈ P is said to be a greatest element of S if g ∈ S and if it also satisfies
- s ≤ g for all s ∈ S.
If S has a greatest element and if (P, ≤) is a partially ordered set then it is necessarily unique and so it is called the greatest element of S.
By using instead of in the above definition, one defines the least element of S. Explicitly, an element l ∈ P is said to be a least element of S if l ∈ S and if it also satisfies
- l ≤ s for all s ∈ S.
If (P, ≤) has a greatest element (resp. a least element) then this element is also called a top (resp. a bottom) of (P, ≤).
Relationship to upper/lower bounds
Greatest elements are closely related to upper bounds.
Let (P, ≤) be a preordered set and let S ⊆ P. An upper bound of S in (P, ≤) is an element u such that u ∈ P and s ≤ u for all s ∈ S. Importantly, an upper bound of S in P is not required to be an element of S.
If g ∈ P then g is a greatest element of S if and only if g is an upper bound of S in (P, ≤) and g ∈ S. In particular, any greatest element of S is also an upper bounded of S (in P) but an upper bound of S in P is a greatest element of S if and only if it belongs to S. In the particular case where P = S, the definition of "u is an upper bound of S in S" becomes: u is an element such that u ∈ S and s ≤ u for all s ∈ S, which is 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 in S.
If u is an upper bound of S in P that is not an upper bound of S in S (which can happen if and only if u ∉ S) then u can not be a greatest element of S (however, it may be possible that some other element is a greatest element of S). In particular, it is possible for S to simultaneously not have a greatest element and for there to exist some upper bound of S 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.
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 (P, ≤) be a partially ordered set and let S ⊆ P. An element m ∈ S is said to be a maximal element of S if whenever s ∈ S satisfies m ≤ s, then necessarily s ≤ m. If (P, ≤) is a partially ordered set then m ∈ S is a maximal element of S if and only if there does not exist any s ∈ S such that m ≤ s and s ≠ 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 (P, ≤) be a partially ordered set and let S ⊆ P.
- A set 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 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[note 2] and moreover, any other maximal element of S will necessarily be equal to g.[note 3]
- 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.[note 4]
- When the restriction of ≤ to S is a total order (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 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 ≤ is a total order on 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
- The subset of integers has no upper bound in the set ℝ of real numbers.
- Let the relation ≤ on { a, b, c, d } be given by a ≤ c, a ≤ d, b ≤ c, b ≤ d. The set { a, b } 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 ℝ, the set of numbers less than 1 has a least upper bound, viz. 1, but no greatest element.
- In ℝ, the set of numbers less than or equal to 1 has a greatest element, viz. 1, which is also its least upper bound.
- In ℝ² with the product order, the set of pairs (x, y) with 0 < x < 1 has no upper bound.
- In ℝ² with the lexicographical order, this set has upper bounds, e.g. (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
- ^ If g1 and g2 are both greatest, then g1 ≤ g2 and g2 ≤ g1, and hence g1 = g2 by antisymmetry.
- ^ If g is the greatest element of S and s ∈ S, then s ≤ g. By antisymmetry, this renders (g ≤ s and g ≠ s) impossible.
- ^ If m ' is a maximal element, then m ' ≤ g since g is greatest, hence m ' = g since m ' is maximal.
- ^ 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 s1 ∈ S must exist that is incomparable to m. Hence s1 ∈ S cannot be maximal, that is, s1 < s2 must hold for some s2 ∈ S. The latter must be incomparable to m, too, since m < s2 contradicts m's maximality while s2 ≤ m contradicts the incomparability of m and s1. Repeating this argument, an infinite ascending chain s1 < s2 < ⋅⋅⋅ < sn < ⋅⋅⋅ can be found (such that each si is incomparable to m and not maximal). This contradicts the ascending chain condition.
- ^ Let m ∈ S be a maximal element, for any s ∈ S either s ≤ m or m ≤ s. In the second case, the definition of maximal element requires that m = s, so it follows that s ≤ m. In other words, m is a greatest element.
- ^ If a, b ∈ P were incomparable, then S = { a, b } would have two maximal, but no greatest element, contradicting the coincidence.
References
- ^ 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.