HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, especially in
order theory Order theory is a branch of mathematics that investigates the 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 intr ...
, the greatest element of a subset S of a
partially ordered set In mathematics, especially order theory, a partially ordered set (also poset) 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 bina ...
(poset) is an element of S that is greater than every other element of S. The term least element is defined
dually Dually may refer to: *Dualla, County Tipperary, a village in Ireland *A pickup truck with dual wheels on the rear axle * DUALLy, s platform for architectural languages interoperability * Dual-processor See also * Dual (disambiguation) Dual or ...
, that is, it is an element of S that is smaller than every other element of S.


Definitions

Let (P, \leq) be a preordered set and let S \subseteq P. An element g \in P is said to be if g \in S and if it also satisfies: :s \leq g for all s \in S. By using \,\geq\, instead of \,\leq\, in the above definition, the definition of a least element of S is obtained. Explicitly, an element l \in P is said to be if l \in S and if it also satisfies: :l \leq s for all s \in S. If (P, \leq) is even a
partially ordered set In mathematics, especially order theory, a partially ordered set (also poset) 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 bina ...
then S can have at most one greatest element and it can have at most one least element. Whenever a greatest element of S exists and is unique then this element is called greatest element of S. The terminology least element of S is defined similarly. If (P, \leq) has a greatest element (resp. a least element) then this element is also called (resp. ) of (P, \leq).


Relationship to upper/lower bounds

Greatest elements are closely related to
upper bound In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is greater than or equal to every element of . Dually, a lower bound or minorant of is defined to be an eleme ...
s. Let (P, \leq) be a preordered set and let S \subseteq P. An is an element u such that u \in P and s \leq u for all s \in S. Importantly, an upper bound of S in P is required to be an element of S. If g \in P then g is a greatest element of S if and only if g is an upper bound of S in (P, \leq) g \in S. In particular, any greatest element of S is also an upper bound of S (in P) but an upper bound of S in P is a greatest element of S if and only if it to S. In the particular case where P = S, the definition of "u is an upper bound of S " becomes: u is an element such that u \in S and s \leq u for all s \in S, which is to the definition of a greatest element given before. Thus g is a greatest element of S if and only if g is an upper bound of S . If u is an upper bound of S that is not an upper bound of S (which can happen if and only if u \not\in S) then u can be a greatest element of S (however, it may be possible that some other element a greatest element of S). In particular, it is possible for S to simultaneously have a greatest element for there to exist some upper bound of S . Even if a set has some upper bounds, it need not have a greatest element, as shown by the example of the negative
real number In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
s. This example also demonstrates that the existence of a
least upper bound In mathematics, the infimum (abbreviated inf; plural infima) of a subset S of a partially ordered set P is a greatest element in P that is less than or equal to each element of S, if such an element exists. Consequently, the term ''greatest lo ...
(the number 0 in this case) does not imply the existence of a greatest element either.


Contrast to maximal elements and local/absolute maximums

A greatest element of a subset of a preordered set should not be confused with a maximal element of the set, which are elements that are not strictly smaller than any other element in the set. Let (P, \leq) be a preordered set and let S \subseteq P. An element m \in S is said to be a if the following condition is satisfied: :whenever s \in S satisfies m \leq s, then necessarily s \leq m. If (P, \leq) is a
partially ordered set In mathematics, especially order theory, a partially ordered set (also poset) 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 bina ...
then m \in S is a maximal element of S if and only if there does exist any s \in S such that m \leq s and s \neq m. A is defined to mean a maximal element of the subset S := P. A set can have several maximal elements without having a greatest element. Like upper bounds and maximal elements, greatest elements may fail to exist. In a
totally ordered set In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X: # a \leq a ( reflexive) ...
the maximal element and the greatest element coincide; and 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 In mathematical analysis, the maxima and minima (the respective plurals of maximum and minimum) of a function, known collectively as extrema (the plural of extremum), are the largest and smallest value of the function, either within a given ra ...
.The notion of locality requires the function's domain to be at least a
topological space In mathematics, a topological space is, roughly speaking, a geometrical space in which closeness is defined but cannot necessarily be measured by a numeric distance. More specifically, a topological space is a set whose elements are called points ...
.
The dual terms are minimum and absolute minimum. Together they are called the absolute extrema. Similar conclusions hold for least elements. ;Role of (in)comparability in distinguishing greatest vs. maximal elements One of the most important differences between a greatest element g and a maximal element m of a preordered set (P, \leq) has to do with what elements they are comparable to. Two elements x, y \in P are said to be if x \leq y or y \leq x; they are called if they are not comparable. Because preorders are reflexive (which means that x \leq x is true for all elements x), every element x is always comparable to itself. Consequently, the only pairs of elements that could possibly be incomparable are pairs. In general, however, preordered sets (and even
directed Director may refer to: Literature * ''Director'' (magazine), a British magazine * ''The Director'' (novel), a 1971 novel by Henry Denker * ''The Director'' (play), a 2000 play by Nancy Hasty Music * Director (band), an Irish rock band * ''D ...
partially ordered sets) may have elements that are incomparable. By definition, an element g \in P is a greatest element of (P, \leq) if s \leq g, for every s \in P; so by its very definition, a greatest element of (P, \leq) must, in particular, be comparable to element in P. This is not required of maximal elements. Maximal elements of (P, \leq) are required to be comparable to every element in P. This is because unlike the definition of "greatest element", the definition of "maximal element" includes an important statement. The defining condition for m \in P to be a maximal element of (P, \leq) can be reworded as: :For all s \in P, m \leq s (so elements that are incomparable to m are ignored) then s \leq m. ;Example where all elements are maximal but none are greatest Suppose that S is a set containing (distinct) elements and define a partial order \,\leq\, on S by declaring that i \leq j if and only if i = j. If i \neq j belong to S then neither i \leq j nor j \leq i holds, which shows that all pairs of distinct (i.e. non-equal) elements in S are comparable. Consequently, (S, \leq) can not possibly have a greatest element (because a greatest element of S would, in particular, have to be comparable to element of S but S has no such element). However, element m \in S is a maximal element of (S, \leq) because there is exactly one element in S that is both comparable to m and \geq m, that element being m itself (which of course, is \leq m).Of course, in this particular example, there exists only one element in S that is comparable to m, which is necessarily m itself, so the second condition "and \geq m," was redundant. In contrast, if a preordered set (P, \leq) does happen to have a greatest element g then g will necessarily be a maximal element of (P, \leq) and moreover, as a consequence of the greatest element g being comparable to element of P, if (P, \leq) is also partially ordered then it is possible to conclude that g is the maximal element of (P, \leq). However, the uniqueness conclusion is no longer guaranteed if the preordered set (P, \leq) is also partially ordered. For example, suppose that R is a non-empty set and define a preorder \,\leq\, on R by declaring that i \leq j holds for all i, j \in R. The
directed Director may refer to: Literature * ''Director'' (magazine), a British magazine * ''The Director'' (novel), a 1971 novel by Henry Denker * ''The Director'' (play), a 2000 play by Nancy Hasty Music * Director (band), an Irish rock band * ''D ...
preordered set (R, \leq) is partially ordered if and only if R has exactly one element. All pairs of elements from R are comparable and element of R is a greatest element (and thus also a maximal element) of (R, \leq). So in particular, if R has at least two elements then (R, \leq) has multiple greatest elements.


Properties

Throughout, let (P, \leq) be a
partially ordered set In mathematics, especially order theory, a partially ordered set (also poset) 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 bina ...
and let S \subseteq P. * A set S can have at most greatest element.If g_1 and g_2 are both greatest, then g_1 \leq g_2 and g_2 \leq g_1, and hence g_1 = g_2 by
antisymmetry In linguistics, antisymmetry is a syntactic theory presented in Richard S. Kayne's 1994 monograph ''The Antisymmetry of Syntax''. It asserts that grammatical hierarchies in natural language follow a universal order, namely specifier-head-comple ...
.
Thus if a set has a greatest element then it is necessarily unique. * If it exists, then the greatest element of S is an
upper bound In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is greater than or equal to every element of . Dually, a lower bound or minorant of is defined to be an eleme ...
of S that is also contained in S. * If g is the greatest element of S then g is also a maximal element of SIf g is the greatest element of S and s \in S, then s \leq g. By
antisymmetry In linguistics, antisymmetry is a syntactic theory presented in Richard S. Kayne's 1994 monograph ''The Antisymmetry of Syntax''. It asserts that grammatical hierarchies in natural language follow a universal order, namely specifier-head-comple ...
, this renders (g \leq s and g \neq s) impossible.
and moreover, any other maximal element of S will necessarily be equal to g.If M is a maximal element, then M \leq g since g is greatest, hence M = g since M is maximal. ** Thus if a set S has several maximal elements then it cannot have a greatest element. * If P satisfies the
ascending chain condition In mathematics, the ascending chain condition (ACC) and descending chain condition (DCC) are finiteness properties satisfied by some algebraic structures, most importantly ideals in certain commutative rings.Jacobson (2009), p. 142 and 147 These con ...
, a subset S of P has a greatest element
if, and only if In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bicon ...
, it has one maximal element.''Only if:'' see above. — ''If:'' Assume for contradiction that S has just one maximal element, m, but no greatest element. Since m is not greatest, some s_1 \in S must exist that is incomparable to m. Hence s_1 \in S cannot be maximal, that is, s_1 < s_2 must hold for some s_2 \in S. The latter must be incomparable to m, too, since m < s_2 contradicts m's maximality while s_2 \leq m contradicts the incomparability of m and s_1. Repeating this argument, an infinite ascending chain s_1 < s_2 < \cdots < s_n < \cdots can be found (such that each s_i is incomparable to m and not maximal). This contradicts the ascending chain condition. * When the restriction of \,\leq\, to S is a
total order In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X: # a \leq a ( reflex ...
(S = \ in the topmost picture is an example), then the notions of maximal element and greatest element coincide.Let m \in S be a maximal element, for any s \in S either s \leq m or m \leq s. In the second case, the definition of maximal element requires that m = s, so it follows that s \leq m. In other words, m is a greatest element. ** However, this is not a necessary condition for whenever S has a greatest element, the notions coincide, too, as stated above. * If the notions of maximal element and greatest element coincide on every two-element subset S of P, then \,\leq\, is a total order on P.If a, b \in P were incomparable, then S = \ would have two maximal, but no greatest element, contradicting the coincidence.


Sufficient conditions

* A finite chain always has a greatest and a least element.


Top and bottom

The least and greatest element of the whole partially ordered set play a special role and are also called bottom (⊥) and top (⊤), or zero (0) and unit (1), respectively. If both exist, the poset is called a bounded poset. The notation of 0 and 1 is used preferably when the poset is a
complemented lattice In the mathematical discipline of order theory, a complemented lattice is a bounded lattice (with least element 0 and greatest element 1), in which every element ''a'' has a complement, i.e. an element ''b'' satisfying ''a'' ∨ ''b''& ...
, 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 Order theory is a branch of mathematics that investigates the 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 intr ...
.


Examples

* The subset of
integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
s has no upper bound in the set \mathbb of
real number In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
s. * Let the relation \,\leq\, on \ be given by a \leq c, a \leq d, b \leq c, b \leq d. The set \ has upper bounds c and d, but no least upper bound, and no greatest element (cf. picture). * In the
rational number In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all ration ...
s, the set of numbers with their square less than 2 has upper bounds but no greatest element and no least upper bound. * In \mathbb, the set of numbers less than 1 has a least upper bound, viz. 1, but no greatest element. * In \mathbb, the set of numbers less than or equal to 1 has a greatest element, viz. 1, which is also its least upper bound. * In \mathbb^2 with the
product order In mathematics, given two preordered sets A and B, the product order (also called the coordinatewise orderDavey & Priestley, ''Introduction to Lattices and Order'' (Second Edition), 2002, p. 18 or componentwise order) is a partial ordering o ...
, the set of pairs (x, y) with 0 < x < 1 has no upper bound. * In \mathbb^2 with the lexicographical order, this set has upper bounds, e.g. (1, 0). It has no least upper bound.


See also

*
Essential supremum and essential infimum In mathematics, the concepts of essential infimum and essential supremum are related to the notions of infimum and supremum, but adapted to measure theory and functional analysis, where one often deals with statements that are not valid for ''all' ...
*
Initial and terminal objects In category theory, a branch of mathematics, an initial object of a category is an object in such that for every object in , there exists precisely one morphism . The dual notion is that of a terminal object (also called terminal element) ...
*
Maximal and minimal elements In mathematics, especially in order theory, a maximal element of a subset ''S'' of some preordered set is an element of ''S'' that is not smaller than any other element in ''S''. A minimal element of a subset ''S'' of some preordered set is def ...
*
Limit superior and limit inferior In mathematics, the limit inferior and limit superior of a sequence can be thought of as limiting (that is, eventual and extreme) bounds on the sequence. They can be thought of in a similar fashion for a function (see limit of a function). For a ...
(infimum limit) *
Upper and lower bounds In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is greater than or equal to every element of . Dually, a lower bound or minorant of is defined to be an eleme ...


Notes


References

* {{cite book , last1=Davey , first1=B. A. , last2=Priestley , first2=H. A. , year = 2002 , title = Introduction to Lattices and Order , title-link= Introduction to Lattices and Order , edition = 2nd , publisher =
Cambridge University Press Cambridge University Press is the university press of the University of Cambridge. Granted letters patent by Henry VIII of England, King Henry VIII in 1534, it is the oldest university press A university press is an academic publishing hou ...
, isbn = 978-0-521-78451-1 Order theory Superlatives