Greatest element
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
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 element
s 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
.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, especially in order theory
Order theory
Order theory is a branch of mathematics which investigates our intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and gives some basic definitions...
, the greatest element of a subset S of a partially ordered set
Partially ordered set
In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...
(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
Duality (order theory)
In the mathematical area of order theory, every partially ordered set P gives rise to a dual partially ordered set which is often denoted by Pop or Pd. This dual order Pop is defined to be the set with the inverse order, i.e. x ≤ y holds in Pop if and only if y ≤ x holds in P...
. 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
Upper bound
In mathematics, especially in order theory, an upper bound of a subset S of some partially ordered set is an element of P which is greater than or equal to every element of S. The term lower bound is defined dually as an element of P which is lesser than or equal to every element of S...
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 element
Maximal element
In mathematics, especially in order theory, a maximal element of a subset S of some partially ordered set is an element of S that is not smaller than any other element in S. The term minimal element is defined dually...
s 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
Total order
In set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...
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
Completeness (order theory)
In the mathematical area of order theory, completeness properties assert the existence of certain infima or suprema of a given partially ordered set . A special use of the term refers to complete partial orders or complete lattices...
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
Order theory
Order theory is a branch of mathematics which investigates our intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and gives some basic definitions...
.
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 orderProduct orderIn mathematics, given two ordered sets A and B, one can induce a partial ordering on the Cartesian product A × B. Giventwo pairs and in A × B, one sets ≤...
, the set of (x, y) with 0 < x < 1 has no upper bound. - In R² with the lexicographical orderLexicographical orderIn mathematics, the lexicographic or lexicographical order, , is a generalization of the way the alphabetical order of words is based on the alphabetical order of letters.-Definition:Given two partially ordered sets A and B, the lexicographical order on...
, this set has upper bounds, e.g. (1, 0). It has no least upper bound.