Greatest element

From Wikipedia, the free encyclopedia
  (Redirected from Least element)
Jump to: navigation, 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 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 has no upper bound in the poset .
  • 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 set of numbers with their square less than 2 has upper bounds but 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 (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.