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.
Formally, given a partially ordered set (P, ≤), an element g of a subset S of P is the greatest element of S if
- s ≤ g, for all elements s of S.
Hence, the greatest element of S is an upper bound of S that is contained within this subset. It is necessarily unique. By using ≥ instead of ≤ in the above definition, one defines the least element of S.
Like upper bounds, greatest elements may fail to exist. 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. Similar conclusions hold for least elements. A finite chain always has a greatest and a least element.
Maximal and minimal elements
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 elements. A set can have several maximal elements without having a greatest element. However, if it has a greatest element, it can't have any other maximal element.
In a totally ordered set both terms coincide; 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.
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
Notes
- The notion of locality requires the function's domain to be at least a topological space.
References
- Davey, B. A.; Priestley, H. A. (2002). Introduction to Lattices and Order (2nd ed.). Cambridge University Press. ISBN 978-0-521-78451-1.