Greatest element and least element: Difference between revisions
Reworded {{short description|}} |
m Fix |
||
Line 1: | Line 1: | ||
{{Use American English|date = March 2019}} |
{{Use American English|date = March 2019}} |
||
{{Short description|An element of a preordered set that is |
{{Short description|An element of a preordered set that is ≥ (respectively, ≤) to all other elements (in contrast, it is maximal if it is the ''only'' element ≥ to itself)}}[[File:Lattice of the divisibility of 60 narrow 1,2,3,4.svg|thumb|[[Hasse diagram]] of the set {{mvar|P}} of [[divisor]]s of 60, partially ordered by the relation "{{mvar|x}} divides {{mvar|y}}". The red subset {{math|1=''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.]] |
||
In [[mathematics]], especially in [[order theory]], the '''greatest element''' of a subset {{mvar|S}} of a [[partially ordered set]] (poset) is an element of {{mvar|S}} that is greater than every other element of {{mvar|S}}. |
In [[mathematics]], especially in [[order theory]], the '''greatest element''' of a subset {{mvar|S}} of a [[partially ordered set]] (poset) is an element of {{mvar|S}} that is greater than every other element of {{mvar|S}}. |
||
The term '''least element''' is defined [[duality (order theory)|dually]], that is, it is an element of ''S'' that is smaller than every other element of {{mvar|S}}. |
The term '''least element''' is defined [[duality (order theory)|dually]], that is, it is an element of ''S'' that is smaller than every other element of {{mvar|S}}. |
Revision as of 09:14, 5 November 2020
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.
Definition
Throughout, let (P, ≤) be a partially ordered set and let S ⊆ P.
Definition: An element g of a subset S of P is said to be a greatest element of S if it satisfiesIf S has a greatest element then it is necessarily unique so we may speak of the greatest element of S.
- s ≤ g, for all s ∈ S.
By using ≥ instead of ≤ in the above definition, one defines the least element of S.
Contrast to maximal elements, upper bounds, and local/absolute maximums
The greatest element of a partially ordered subset must not be confused with maximal elements of the set, which are elements that are not 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.
Definitions:
- An element m ∈ S is said to be a maximal element of S if there does not exist any s ∈ S such that m ≤ s and s ≠ m.
- An upper bound of S in P is an element u such that u ∈ P and s ≤ u for all s ∈ 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.
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 plays a special role and is also called bottom and top, or zero (0) and unit (1), or ⊥ and ⊤, respectively. If both exists, the poset is called a bounded poset. The notation of 0 and 1 is used preferably when the poset is even 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.