Greatest and least elements

From Wikipedia, the free encyclopedia
  (Redirected from Least element)
Jump to navigation Jump to search

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

sg, 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.

A 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.

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[edit]

  • 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 ac, ad, bc, bd. The set {a, b} has upper bounds c and d, but no least upper bound, and no greatest element.
  • 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[edit]

References[edit]

  1. ^ 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.