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 binary ...
(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 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 binary ...
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 bounds. 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 ...
s. 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.


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 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 defin ...
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 binary ...
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 ran ...
.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 poin ...
.
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 binary ...
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. 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 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, 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 c ...
, 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 ( reflexive ...
(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 A chain is a serial assembly of connected pieces, called links, typically made of metal, with an overall character similar to that of a rope in that it is flexible and curved in compression but linear, rigid, and load-bearing in tension. ...
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, 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 languag ...
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 ...
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 ra ...
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, the set of pairs (x, y) with 0 < x < 1 has no upper bound. * In \mathbb^2 with the
lexicographical order In mathematics, the lexicographic or lexicographical order (also known as lexical order, or dictionary order) is a generalization of the alphabetical order of the dictionaries to sequences of ordered symbols or, more generally, of elements of ...
, this set has upper bounds, e.g. (1, 0). It has no least upper bound.


See also

* Essential supremum and essential infimum * Initial and terminal objects *
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 King Henry VIII in 1534, it is the oldest university press in the world. It is also the King's Printer. Cambridge University Pr ...
, isbn = 978-0-521-78451-1 Order theory Superlatives