greatest_element

Search for "greatest element" on Ebay? Click here!

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

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 without having a 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.

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.

greatest_element: information

Examples

See also