Greatest element

From Wikipedia, the free encyclopedia

In mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set (poset) is an element of S which is greater than or equal to any other element of S. The term least element is defined dually. A bounded poset is a poset that has both a greatest element and a least element.

Formally, given a partially ordered set (P, ≤), then 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 the example of the real numbers strictly smaller than 1 shows. This also demonstrates that the existence of a least upper bound (the number 1 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.

Greatest elements of a partially ordered subset must not be confused with maximal elements of such a set which are elements that are not smaller than any other element. A poset can have several maximal elements but no greatest 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. The dual terms are minimum and absolute minimum. Together they are called the absolute extrema.

The least and greatest elements of the whole partially ordered set play a special role and are also called bottom and top or zero (0) and unit (1), respectively. The latter notation of 0 and 1 is only used when no confusion is likely, i.e. when one is not talking about partial orders of numbers that already contain elements 0 and 1. The existence of least and greatest elements is a special completeness property of a partial order. Bottom and top are often represented by the symbols ⊥ and ⊤, respectively.

Further introductory information is found in the article on order theory.

[edit] Examples

Z in R has no upper bound.
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.
In Q, the set of numbers with their square less than 2 has upper bounds but no least upper bound.
In R, the set of numbers less than 1 has a least upper bound, but no greatest element.
In R, the set of numbers less than or equal to 1 has a greatest element.
In R² with the product order, the set of (x, y) with 0 < x < 1 has no upper bound.
In R² with the lexicographical order, this set has upper bounds, e.g. (1, 0). It has no least upper bound.