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
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
that is greater than every other element of
. 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
that is smaller than every other element of
Definitions
Let
be a
preordered set and let
An element
is said to be if
and if it also satisfies:
:
for all
By using
instead of
in the above definition, the definition of a least element of
is obtained. Explicitly, an element
is said to be if
and if it also satisfies:
:
for all
If
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
can have at most one greatest element and it can have at most one least element. Whenever a greatest element of
exists and is unique then this element is called greatest element of
. The terminology least element of
is defined similarly.
If
has a greatest element (resp. a least element) then this element is also called (resp. ) of
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
be a
preordered set and let
An is an element
such that
and
for all
Importantly, an upper bound of
in
is required to be an element of
If
then
is a greatest element of
if and only if
is an upper bound of
in
In particular, any greatest element of
is also an upper bound of
(in
) but an upper bound of
in
is a greatest element of
if and only if it to
In the particular case where
the definition of "
is an upper bound of
" becomes:
is an element such that
and
for all
which is to the definition of a greatest element given before.
Thus
is a greatest element of
if and only if
is an upper bound of
.
If
is an upper bound of
that is not an upper bound of
(which can happen if and only if
) then
can be a greatest element of
(however, it may be possible that some other element a greatest element of
).
In particular, it is possible for
to simultaneously have a greatest element for there to exist some upper bound of
.
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
be a
preordered set and let
An element
is said to be a if the following condition is satisfied:
:whenever
satisfies
then necessarily
If
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
is a maximal element of
if and only if there does exist any
such that
and
A is defined to mean a maximal element of the subset
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
and a maximal element
of a preordered set
has to do with what elements they are comparable to.
Two elements
are said to be if
or
; they are called if they are not comparable.
Because preorders are
reflexive (which means that
is true for all elements
), every element
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
is a greatest element of
if
for every
; so by its very definition, a greatest element of
must, in particular, be comparable to element in
This is not required of maximal elements.
Maximal elements of
are required to be comparable to every element in
This is because unlike the definition of "greatest element", the definition of "maximal element" includes an important statement.
The defining condition for
to be a maximal element of
can be reworded as:
:For all
(so elements that are incomparable to
are ignored) then
;Example where all elements are maximal but none are greatest
Suppose that
is a set containing (distinct) elements and define a partial order
on
by declaring that
if and only if
If
belong to
then neither
nor
holds, which shows that all pairs of distinct (i.e. non-equal) elements in
are comparable.
Consequently,
can not possibly have a greatest element (because a greatest element of
would, in particular, have to be comparable to element of
but
has no such element).
However, element
is a maximal element of
because there is exactly one element in
that is both comparable to
and
that element being
itself (which of course, is
).
[Of course, in this particular example, there exists only one element in that is comparable to which is necessarily itself, so the second condition "and " was redundant.]
In contrast, if a
preordered set does happen to have a greatest element
then
will necessarily be a maximal element of
and moreover, as a consequence of the greatest element
being comparable to element of
if
is also partially ordered then it is possible to conclude that
is the maximal element of
However, the uniqueness conclusion is no longer guaranteed if the preordered set
is also partially ordered.
For example, suppose that
is a non-empty set and define a preorder
on
by declaring that
holds for all
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
is partially ordered if and only if
has exactly one element. All pairs of elements from
are comparable and element of
is a greatest element (and thus also a maximal element) of
So in particular, if
has at least two elements then
has multiple greatest elements.
Properties
Throughout, let
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
* A set
can have at most greatest element.
[If and are both greatest, then and and hence 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
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
that is also contained in
* If
is the greatest element of
then
is also a maximal element of
[If is the greatest element of and then 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 ( and ) impossible. and moreover, any other maximal element of
will necessarily be equal to
[If is a maximal element, then since is greatest, hence since is maximal.]
** Thus if a set
has several maximal elements then it cannot have a greatest element.
* If
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
of
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 has just one maximal element, but no greatest element. Since is not greatest, some must exist that is incomparable to Hence cannot be maximal, that is, must hold for some The latter must be incomparable to too, since contradicts 's maximality while contradicts the incomparability of and Repeating this argument, an infinite ascending chain can be found (such that each is incomparable to and not maximal). This contradicts the ascending chain condition.]
* When the restriction of
to
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 ...
(
in the topmost picture is an example), then the notions of maximal element and greatest element coincide.
[Let be a maximal element, for any either or In the second case, the definition of maximal element requires that so it follows that In other words, is a greatest element.]
** However, this is not a necessary condition for whenever
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
of
then
is a total order on
[If were incomparable, then 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
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
on
be given by
The set
has upper bounds
and
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
the set of numbers less than 1 has a least upper bound, viz. 1, but no greatest element.
* In
the set of numbers less than or equal to 1 has a greatest element, viz. 1, which is also its least upper bound.
* In
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
with
has no upper bound.
* In
with the
lexicographical order, this set has upper bounds, e.g.
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