greatest and least elements
   HOME

TheInfoList



In
mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It has no generally ...
, especially in
order theory Order theory is a branch of mathematics which 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 intro ...
, the greatest element of a subset S of a
partially ordered set upright=1.15, Fig.1 The Hasse diagram of the Power set, set of all subsets of a three-element set \, ordered by set inclusion, inclusion. Sets connected by an upward path, like \emptyset and \, are comparable, while e.g. \ and \ are not. In mathem ...
(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 In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). ...
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 a
partially ordered set upright=1.15, Fig.1 The Hasse diagram of the Power set, set of all subsets of a three-element set \, ordered by set inclusion, inclusion. Sets connected by an upward path, like \emptyset and \, are comparable, while e.g. \ and \ are not. In mathem ...
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 Order theory is a branch of mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), s ...
s. Let (P, \leq) be a
preordered set In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). ...
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 Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). ...
s. This example also demonstrates that the existence of a
least upper bound are equal. Image:Supremum illustration.svg, 250px, A set ''A'' of real numbers (blue circles), a set of upper bounds of ''A'' (red diamond and circles), and the smallest such upper bound, that is, the supremum of ''A'' (red diamond). In mathematic ...
(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 Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It h ...
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 In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). ...
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 upright=1.15, Fig.1 The Hasse diagram of the Power set, set of all subsets of a three-element set \, ordered by set inclusion, inclusion. Sets connected by an upward path, like \emptyset and \, are comparable, while e.g. \ and \ are not. In mathem ...
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 Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...
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 ...

local maximum
.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 Geometry, geometrical space in which Closeness (mathematics), ''closeness'' is defined but cannot necessarily be measured by a numeric distance. More specifically, a topological space is a ...
.
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), ''Director'' (magazine), a British magazine * The Director (novel), ''The Director'' (novel), a 1971 novel by Henry Denker * The Director (play), ''The Director'' (play), a 2000 play by Nanc ...
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 In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). ...
(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), ''Director'' (magazine), a British magazine * The Director (novel), ''The Director'' (novel), a 1971 novel by Henry Denker * The Director (play), ''The Director'' (play), a 2000 play by Nanc ...
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 upright=1.15, Fig.1 The Hasse diagram of the Power set, set of all subsets of a three-element set \, ordered by set inclusion, inclusion. Sets connected by an upward path, like \emptyset and \, are comparable, while e.g. \ and \ are not. In mathem ...
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 theory of syntax, syntactic linearization presented in Richard Kayne's 1994 monograph ''The Antisymmetry of Syntax''. The crux of this theory is that hierarchical structure in natural language maps universally onto ...
.
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 Order theory is a branch of mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), s ...
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 theory of syntax, syntactic linearization presented in Richard Kayne's 1994 monograph ''The Antisymmetry of Syntax''. The crux of this theory is that hierarchical structure in natural language maps universally onto ...
, 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 conditionIn mathematics, the ascending chain condition (ACC) and descending chain condition (DCC) are finiteness properties satisfied by some algebraic structures, most importantly Ideal (ring theory), ideals in certain commutative rings.Jacobson (2009), p. 1 ...
, a subset S of P has a greatest element
if, and only if In logic Logic (from Ancient Greek, Greek: grc, wikt:λογική, λογική, label=none, lit=possessed of reason, intellectual, dialectical, argumentative, translit=logikḗ)Also related to (''logos''), "word, thought, idea, argumen ...
, 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 (mathematics), set X, which satisfies the following for all a, b and c in X: # a \ ...
(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 Image:Kettenvergleich.jpg, Roller chains A chain is a wikt:series#Noun, 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 compres ...
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 Order theory is a branch of mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), sp ...
, 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 which 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 intro ...
.


Examples

* The subset of
integer An integer (from the Latin Latin (, or , ) is a classical language belonging to the Italic languages, Italic branch of the Indo-European languages. Latin was originally spoken in the area around Rome, known as Latium. Through the power of t ...
s has no upper bound in the set \mathbb of
real number In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). ...
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 Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). ...
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 Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
, the set of pairs (x, y) with 0 < x < 1 has no upper bound. * In \mathbb^2 with the
lexicographical order In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
, 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 * Limit superior and limit inferior (infimum limit) * Upper and lower bounds


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 , isbn = 978-0-521-78451-1 Order theory Superlatives