In
mathematicsMathematics 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...
, given a subset
S of a
totallyIn 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...
or
partially ordered setIn 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...
T, the
supremum (sup) of
S, if it exists, is the
least elementIn mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set is an element of S which is greater than or equal to any other element of S. The term least element is defined dually...
of
T that is
greater than or equal to every element of
S. Consequently, the supremum is also referred to as the
least upper bound (
lub or
LUB). If the supremum exists, it is unique. If
S contains a
greatest elementIn mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set is an element of S which is greater than or equal to any other element of S. The term least element is defined dually...
, then that element is the supremum; otherwise, the supremum does not belong to
S (or does not exist). For instance, the negative real numbers do not have a greatest element, and their supremum is 0 (which is not a negative real number).
Suprema are often considered for subsets of
real numberIn mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
s,
rational numberIn mathematics, a rational number is any number that can be expressed as the quotient or fraction a/b of two integers, with the denominator b not equal to zero. Since b may be equal to 1, every integer is a rational number...
s, or any other well-known mathematical structure for which it is immediately clear what it means for an element to be "greater-than-or-equal-to" another element. The definition generalizes easily to the more abstract setting of
order theoryOrder 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...
, where one considers arbitrary
partially ordered setIn 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...
s.
The concept of supremum coincides with the concept of
leastIn mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set is an element of S which is greater than or equal to any other element of S. The term least element is defined dually...
upper boundIn 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...
, but not with the concepts of minimal upper bound,
maximal elementIn 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...
, or
greatest elementIn mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set is an element of S which is greater than or equal to any other element of S. The term least element is defined dually...
. The supremum is in a precise sense
dualIn 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...
to the concept of an
infimumIn mathematics, the infimum of a subset S of some partially ordered set T is the greatest element of T that is less than or equal to all elements of S. Consequently the term greatest lower bound is also commonly used...
.
Supremum of a set of real numbers
In
analysisMathematical analysis, which mathematicians refer to simply as analysis, has its beginnings in the rigorous formulation of infinitesimal calculus. It is a branch of pure mathematics that includes the theories of differentiation, integration and measure, limits, infinite series, and analytic functions...
, the
supremum or
least upper bound of a set
S of real numbers is denoted by sup(
S) and is defined to be the smallest real number that is greater than or equal to every number in
S. An important property of the real numbers is its
completenessIn 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...
: every nonempty subset of the set of real numbers that is bounded above has a supremum that is also a real number.
Examples
In the last example, the supremum of a set of
rationalsIn mathematics, a rational number is any number that can be expressed as the quotient or fraction a/b of two integers, with the denominator b not equal to zero. Since b may be equal to 1, every integer is a rational number...
is
irrationalIn mathematics, an irrational number is any real number that cannot be expressed as a ratio a/b, where a and b are integers, with b non-zero, and is therefore not a rational number....
, which means that the rationals are
incompleteIn mathematical analysis, a metric space M is called complete if every Cauchy sequence of points in M has a limit that is also in M or, alternatively, if every Cauchy sequence in M converges in M....
.
One basic property of the supremum is
for any
functionalsIn mathematics, and particularly in functional analysis, a functional is a map from a vector space into its underlying scalar field. In other words, it is a function that takes a vector as its input argument, and returns a scalar...
f and
g.
If, in addition, we define sup(
S) = −∞ when
S is
emptyIn mathematics, and more specifically set theory, the empty set is the unique set having no elements; its size or cardinality is zero. Some axiomatic set theories assure that the empty set exists by including an axiom of empty set; in other theories, its existence can be deduced...
and sup(
S) = +∞ when
S is not bounded above, then every set of real numbers has a supremum under the affinely extended real number system.
If the supremum belongs to the set, then it is the
greatest elementIn mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set is an element of S which is greater than or equal to any other element of S. The term least element is defined dually...
in the set. The term
maximal elementIn 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...
is synonymous as long as one deals with real numbers or any other totally ordered set.
To show that
a = sup(
S), one has to show that
a is an upper bound for
S and that any other upper bound for
S is greater than
a. Equivalently, one could alternatively show that
a is an upper bound for
S and that any number less than
a is not an upper bound for
S.
Suprema within partially ordered sets
Least upper bounds are important concepts in
order theoryOrder 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...
, where they are also called joins (especially in
lattice theoryIn mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...
). As in the special case treated above, a supremum of a given set is just the least element of the set of its
upper boundIn 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...
s, provided that such an element exists.
Formally, we have: For subsets
S of arbitrary
partially ordered setIn 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...
s (
P, ≤), a
supremum or
least upper bound of
S is an element
u in
P such that
- x ≤ u for all x in S, and
- for any v in P such that x ≤ v for all x in S it holds that u ≤ v.
Thus the supremum does not exist if there is no upper bound, or if the set of upper bounds has two or more elements of which none is a least element of that set.
It can easily be shown that, if
S has a supremum, then the supremum is unique (as the least element of any partially ordered set, if it exists, is unique): if
u1 and
u2 are both suprema of
S then it follows that
u1 ≤
u2 and
u2 ≤
u1, and since ≤ is antisymmetric, one finds that
u1 =
u2.
If the supremum exists it may or may not belong to
S. If
S contains a
greatest elementIn mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set is an element of S which is greater than or equal to any other element of S. The term least element is defined dually...
, then that element is the supremum; and if not, then the supremum does not belong to
S.
The
dualIn 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...
concept of supremum, the greatest lower bound, is called
infimumIn mathematics, the infimum of a subset S of some partially ordered set T is the greatest element of T that is less than or equal to all elements of S. Consequently the term greatest lower bound is also commonly used...
and is also known as
meetIn mathematics, join and meet are dual binary operations on the elements of a partially ordered set. A join on a set is defined as the supremum with respect to a partial order on the set, provided a supremum exists...
.
If the supremum of a set
S exists, it can be denoted as sup(
S) or, which is more common in order theory, by
S. Likewise, infima are denoted by inf(
S) or
S. In lattice theory it is common to use the infimum/meet and supremum/join as binary operators; in this case
(and similarly for infima).
A
complete latticeIn mathematics, a complete lattice is a partially ordered set in which all subsets have both a supremum and an infimum . Complete lattices appear in many applications in mathematics and computer science...
is a partially ordered set in which
all subsets have both a supremum (join) and an infimum (meet).
In the sections below the difference between suprema, maximal elements, and minimal upper bounds is stressed. As a consequence of the possible absence of suprema, classes of partially ordered sets for which certain types of subsets are guaranteed to have least upper bound become especially interesting. This leads to the consideration of so-called
completeness propertiesIn 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...
and to numerous definitions of special partially ordered sets.
Examples
The supremum of a subset
S of (ℤ
+, |), where | denotes "
dividesIn mathematics, a divisor of an integer n, also called a factor of n, is an integer which divides n without leaving a remainder.-Explanation:...
", is the lowest common multiple of the elements of
S.
The supremum of a subset
S of (
P, ⊆), where
P is the
power set of some set, is the supremum with respect to ⊆ (subset) of a subset
S of
P is the
unionIn set theory, the union of a collection of sets is the set of all distinct elements in the collection. The union of a collection of sets S_1, S_2, S_3, \dots , S_n\,\! gives a set S_1 \cup S_2 \cup S_3 \cup \dots \cup S_n.- Definition :...
of the elements of
S.
Greatest elements
The distinction between the supremum of a set and the
greatest elementIn mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set is an element of S which is greater than or equal to any other element of S. The term least element is defined dually...
of a set may not be immediately obvious. The difference is that the greatest element must be a member of the set, whereas the supremum need not. For example, consider the set of negative real numbers (excluding zero). This set has no greatest element, since for every element of the set, there is another, larger, element. For instance, for any negative real number
x, there is another negative real number
x/2, which is greater. On the other hand, every real number greater than or equal to zero is certainly an upper bound on this set. Hence, 0 is the least upper bound of the negative reals, so the supremum is 0. This set has a supremum but no greatest element.
In general, this situation occurs for all subsets that do not contain a greatest element. In contrast, if a set does contain a greatest element, then it also has a supremum given by the greatest element.
Maximal elements
For an example where there are no greatest but still some
maximal elementIn 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, consider the set of all subsets of the set of natural numbers (the powerset). We take the usual subset inclusion as an ordering, i.e. a set is greater than another set if it contains all elements of the other set. Now consider the set
S of all sets that contain at most ten natural numbers. The set
S has many maximal elements, i.e. elements for which there is no greater element. In fact, all sets with ten elements are maximal. However, the supremum of
S is the (only and therefore least) set which contains all natural numbers. One can compute the least upper bound of a subset
A of a powerset (i.e.
A is a set of sets) by just taking the union of the elements of
A.
Minimal upper bounds
Finally, a set may have many minimal upper bounds without having a least upper bound. Minimal upper bounds are those upper bounds for which there is no strictly smaller element that also is an upper bound. This does not say that each minimal upper bound is smaller than all other upper bounds, it merely is not greater. The distinction between "minimal" and "least" is only possible when the given order is not a total one. In a totally ordered set, like the real numbers mentioned above, the concepts are the same.
As an example, let
S be the set of all finite subsets of natural numbers and consider the partially ordered set obtained by taking all sets from
S together with the set of
integerThe integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s
Z and the set of positive real numbers
R+, ordered by subset inclusion as above. Then clearly both
Z and
R+ are greater than all finite sets of natural numbers. Yet, neither is
R+ smaller than
Z nor is the converse true: both sets are minimal upper bounds but none is a supremum.
Least-upper-bound property
The
least-upper-bound property is an example of the aforementioned
completeness propertiesIn 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...
which is typical for the set of real numbers. This property is sometimes called
Dedekind completeness.
If an ordered set
S has the property that every nonempty subset of
S having an upper bound also has a least upper bound, then
S is said to have the least-upper-bound property. As noted above, the set
R of all real numbers has the least-upper-bound property. Similarly, the set
Z of integers has the least-upper-bound property; if
S is a nonempty subset of
Z and there is some number
n such that every element
s of
S is less than or equal to
n, then there is a least upper bound
u for
S, an integer that is an upper bound for
S and is less than or equal to every other upper bound for
S. A
well-orderIn mathematics, a well-order relation on a set S is a strict total order on S with the property that every non-empty subset of S has a least element in this ordering. Equivalently, a well-ordering is a well-founded strict total order...
ed set also has the least-upper-bound property, and the empty subset has also a least upper bound: the minimum of the whole set.
An example of a set that
lacks the least-upper-bound property is
Q, the set of rational numbers. Let
S be the set of all rational numbers
q such that
q2 < 2. Then
S has an upper bound (1000, for example, or 6) but no least upper bound in
Q: If we suppose
p ∈
Q is the least upper bound, a contradiction is immediately deduced because between any two reals
x and
y (including
√
{{redirect|Suprema}}
{{redirect|LUB|the Uruguayan basketball competition|Liga Uruguaya de Basketball}}
{{Merge|Infimum|discuss=Talk:Infimum#Merge|date=July 2011}}
In mathematicsMathematics 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...
, given a subset
S of a
totallyIn 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...
or
partially ordered setIn 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...
T, the
supremum (sup) of
S, if it exists, is the
least elementIn mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set is an element of S which is greater than or equal to any other element of S. The term least element is defined dually...
of
T that is
greater than or equal to every element of
S. Consequently, the supremum is also referred to as the
least upper bound (
lub or
LUB). If the supremum exists, it is unique. If
S contains a
greatest elementIn mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set is an element of S which is greater than or equal to any other element of S. The term least element is defined dually...
, then that element is the supremum; otherwise, the supremum does not belong to
S (or does not exist). For instance, the negative real numbers do not have a greatest element, and their supremum is 0 (which is not a negative real number).
Suprema are often considered for subsets of
real numberIn mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
s,
rational numberIn mathematics, a rational number is any number that can be expressed as the quotient or fraction a/b of two integers, with the denominator b not equal to zero. Since b may be equal to 1, every integer is a rational number...
s, or any other well-known mathematical structure for which it is immediately clear what it means for an element to be "greater-than-or-equal-to" another element. The definition generalizes easily to the more abstract setting of
order theoryOrder 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...
, where one considers arbitrary
partially ordered setIn 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...
s.
The concept of supremum coincides with the concept of
leastIn mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set is an element of S which is greater than or equal to any other element of S. The term least element is defined dually...
upper boundIn 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...
, but not with the concepts of minimal upper bound,
maximal elementIn 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...
, or
greatest elementIn mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set is an element of S which is greater than or equal to any other element of S. The term least element is defined dually...
. The supremum is in a precise sense
dualIn 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...
to the concept of an
infimumIn mathematics, the infimum of a subset S of some partially ordered set T is the greatest element of T that is less than or equal to all elements of S. Consequently the term greatest lower bound is also commonly used...
.
Supremum of a set of real numbers
In
analysisMathematical analysis, which mathematicians refer to simply as analysis, has its beginnings in the rigorous formulation of infinitesimal calculus. It is a branch of pure mathematics that includes the theories of differentiation, integration and measure, limits, infinite series, and analytic functions...
, the
supremum or
least upper bound of a set
S of real numbers is denoted by sup(
S) and is defined to be the smallest real number that is greater than or equal to every number in
S. An important property of the real numbers is its
completenessIn 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...
: every nonempty subset of the set of real numbers that is bounded above has a supremum that is also a real number.
Examples
In the last example, the supremum of a set of
rationalsIn mathematics, a rational number is any number that can be expressed as the quotient or fraction a/b of two integers, with the denominator b not equal to zero. Since b may be equal to 1, every integer is a rational number...
is
irrationalIn mathematics, an irrational number is any real number that cannot be expressed as a ratio a/b, where a and b are integers, with b non-zero, and is therefore not a rational number....
, which means that the rationals are
incompleteIn mathematical analysis, a metric space M is called complete if every Cauchy sequence of points in M has a limit that is also in M or, alternatively, if every Cauchy sequence in M converges in M....
.
One basic property of the supremum is
for any
functionalsIn mathematics, and particularly in functional analysis, a functional is a map from a vector space into its underlying scalar field. In other words, it is a function that takes a vector as its input argument, and returns a scalar...
f and
g.
If, in addition, we define sup(
S) = −∞ when
S is
emptyIn mathematics, and more specifically set theory, the empty set is the unique set having no elements; its size or cardinality is zero. Some axiomatic set theories assure that the empty set exists by including an axiom of empty set; in other theories, its existence can be deduced...
and sup(
S) = +∞ when
S is not bounded above, then every set of real numbers has a supremum under the affinely extended real number system.
If the supremum belongs to the set, then it is the
greatest elementIn mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set is an element of S which is greater than or equal to any other element of S. The term least element is defined dually...
in the set. The term
maximal elementIn 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...
is synonymous as long as one deals with real numbers or any other totally ordered set.
To show that
a = sup(
S), one has to show that
a is an upper bound for
S and that any other upper bound for
S is greater than
a. Equivalently, one could alternatively show that
a is an upper bound for
S and that any number less than
a is not an upper bound for
S.
Suprema within partially ordered sets
Least upper bounds are important concepts in
order theoryOrder 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...
, where they are also called joins (especially in
lattice theoryIn mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...
). As in the special case treated above, a supremum of a given set is just the least element of the set of its
upper boundIn 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...
s, provided that such an element exists.
Formally, we have: For subsets
S of arbitrary
partially ordered setIn 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...
s (
P, ≤), a
supremum or
least upper bound of
S is an element
u in
P such that
- x ≤ u for all x in S, and
- for any v in P such that x ≤ v for all x in S it holds that u ≤ v.
Thus the supremum does not exist if there is no upper bound, or if the set of upper bounds has two or more elements of which none is a least element of that set.
It can easily be shown that, if
S has a supremum, then the supremum is unique (as the least element of any partially ordered set, if it exists, is unique): if
u1 and
u2 are both suprema of
S then it follows that
u1 ≤
u2 and
u2 ≤
u1, and since ≤ is antisymmetric, one finds that
u1 =
u2.
If the supremum exists it may or may not belong to
S. If
S contains a
greatest elementIn mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set is an element of S which is greater than or equal to any other element of S. The term least element is defined dually...
, then that element is the supremum; and if not, then the supremum does not belong to
S.
The
dualIn 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...
concept of supremum, the greatest lower bound, is called
infimumIn mathematics, the infimum of a subset S of some partially ordered set T is the greatest element of T that is less than or equal to all elements of S. Consequently the term greatest lower bound is also commonly used...
and is also known as
meetIn mathematics, join and meet are dual binary operations on the elements of a partially ordered set. A join on a set is defined as the supremum with respect to a partial order on the set, provided a supremum exists...
.
If the supremum of a set
S exists, it can be denoted as sup(
S) or, which is more common in order theory, by
S. Likewise, infima are denoted by inf(
S) or
S. In lattice theory it is common to use the infimum/meet and supremum/join as binary operators; in this case
(and similarly for infima).
A
complete latticeIn mathematics, a complete lattice is a partially ordered set in which all subsets have both a supremum and an infimum . Complete lattices appear in many applications in mathematics and computer science...
is a partially ordered set in which
all subsets have both a supremum (join) and an infimum (meet).
In the sections below the difference between suprema, maximal elements, and minimal upper bounds is stressed. As a consequence of the possible absence of suprema, classes of partially ordered sets for which certain types of subsets are guaranteed to have least upper bound become especially interesting. This leads to the consideration of so-called
completeness propertiesIn 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...
and to numerous definitions of special partially ordered sets.
Examples
The supremum of a subset
S of (ℤ
+, |), where | denotes "
dividesIn mathematics, a divisor of an integer n, also called a factor of n, is an integer which divides n without leaving a remainder.-Explanation:...
", is the lowest common multiple of the elements of
S.
The supremum of a subset
S of (
P, ⊆), where
P is the
power set of some set, is the supremum with respect to ⊆ (subset) of a subset
S of
P is the
unionIn set theory, the union of a collection of sets is the set of all distinct elements in the collection. The union of a collection of sets S_1, S_2, S_3, \dots , S_n\,\! gives a set S_1 \cup S_2 \cup S_3 \cup \dots \cup S_n.- Definition :...
of the elements of
S.
Greatest elements
The distinction between the supremum of a set and the
greatest elementIn mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set is an element of S which is greater than or equal to any other element of S. The term least element is defined dually...
of a set may not be immediately obvious. The difference is that the greatest element must be a member of the set, whereas the supremum need not. For example, consider the set of negative real numbers (excluding zero). This set has no greatest element, since for every element of the set, there is another, larger, element. For instance, for any negative real number
x, there is another negative real number
x/2, which is greater. On the other hand, every real number greater than or equal to zero is certainly an upper bound on this set. Hence, 0 is the least upper bound of the negative reals, so the supremum is 0. This set has a supremum but no greatest element.
In general, this situation occurs for all subsets that do not contain a greatest element. In contrast, if a set does contain a greatest element, then it also has a supremum given by the greatest element.
Maximal elements
For an example where there are no greatest but still some
maximal elementIn 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, consider the set of all subsets of the set of natural numbers (the powerset). We take the usual subset inclusion as an ordering, i.e. a set is greater than another set if it contains all elements of the other set. Now consider the set
S of all sets that contain at most ten natural numbers. The set
S has many maximal elements, i.e. elements for which there is no greater element. In fact, all sets with ten elements are maximal. However, the supremum of
S is the (only and therefore least) set which contains all natural numbers. One can compute the least upper bound of a subset
A of a powerset (i.e.
A is a set of sets) by just taking the union of the elements of
A.
Minimal upper bounds
Finally, a set may have many minimal upper bounds without having a least upper bound. Minimal upper bounds are those upper bounds for which there is no strictly smaller element that also is an upper bound. This does not say that each minimal upper bound is smaller than all other upper bounds, it merely is not greater. The distinction between "minimal" and "least" is only possible when the given order is not a total one. In a totally ordered set, like the real numbers mentioned above, the concepts are the same.
As an example, let
S be the set of all finite subsets of natural numbers and consider the partially ordered set obtained by taking all sets from
S together with the set of
integerThe integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s
Z and the set of positive real numbers
R+, ordered by subset inclusion as above. Then clearly both
Z and
R+ are greater than all finite sets of natural numbers. Yet, neither is
R+ smaller than
Z nor is the converse true: both sets are minimal upper bounds but none is a supremum.
Least-upper-bound property
{{main|Least-upper-bound property}}
The
least-upper-bound property is an example of the aforementioned
completeness propertiesIn 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...
which is typical for the set of real numbers. This property is sometimes called
Dedekind completeness.
If an ordered set
S has the property that every nonempty subset of
S having an upper bound also has a least upper bound, then
S is said to have the least-upper-bound property. As noted above, the set
R of all real numbers has the least-upper-bound property. Similarly, the set
Z of integers has the least-upper-bound property; if
S is a nonempty subset of
Z and there is some number
n such that every element
s of
S is less than or equal to
n, then there is a least upper bound
u for
S, an integer that is an upper bound for
S and is less than or equal to every other upper bound for
S. A
well-orderIn mathematics, a well-order relation on a set S is a strict total order on S with the property that every non-empty subset of S has a least element in this ordering. Equivalently, a well-ordering is a well-founded strict total order...
ed set also has the least-upper-bound property, and the empty subset has also a least upper bound: the minimum of the whole set.
An example of a set that
lacks the least-upper-bound property is
Q, the set of rational numbers. Let
S be the set of all rational numbers
q such that
q2 < 2. Then
S has an upper bound (1000, for example, or 6) but no least upper bound in
Q: If we suppose
p ∈
Q is the least upper bound, a contradiction is immediately deduced because between any two reals
x and
y (including
√
{{redirect|Suprema}}
{{redirect|LUB|the Uruguayan basketball competition|Liga Uruguaya de Basketball}}
{{Merge|Infimum|discuss=Talk:Infimum#Merge|date=July 2011}}
In mathematicsMathematics 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...
, given a subset
S of a
totallyIn 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...
or
partially ordered setIn 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...
T, the
supremum (sup) of
S, if it exists, is the
least elementIn mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set is an element of S which is greater than or equal to any other element of S. The term least element is defined dually...
of
T that is
greater than or equal to every element of
S. Consequently, the supremum is also referred to as the
least upper bound (
lub or
LUB). If the supremum exists, it is unique. If
S contains a
greatest elementIn mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set is an element of S which is greater than or equal to any other element of S. The term least element is defined dually...
, then that element is the supremum; otherwise, the supremum does not belong to
S (or does not exist). For instance, the negative real numbers do not have a greatest element, and their supremum is 0 (which is not a negative real number).
Suprema are often considered for subsets of
real numberIn mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
s,
rational numberIn mathematics, a rational number is any number that can be expressed as the quotient or fraction a/b of two integers, with the denominator b not equal to zero. Since b may be equal to 1, every integer is a rational number...
s, or any other well-known mathematical structure for which it is immediately clear what it means for an element to be "greater-than-or-equal-to" another element. The definition generalizes easily to the more abstract setting of
order theoryOrder 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...
, where one considers arbitrary
partially ordered setIn 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...
s.
The concept of supremum coincides with the concept of
leastIn mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set is an element of S which is greater than or equal to any other element of S. The term least element is defined dually...
upper boundIn 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...
, but not with the concepts of minimal upper bound,
maximal elementIn 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...
, or
greatest elementIn mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set is an element of S which is greater than or equal to any other element of S. The term least element is defined dually...
. The supremum is in a precise sense
dualIn 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...
to the concept of an
infimumIn mathematics, the infimum of a subset S of some partially ordered set T is the greatest element of T that is less than or equal to all elements of S. Consequently the term greatest lower bound is also commonly used...
.
Supremum of a set of real numbers
In
analysisMathematical analysis, which mathematicians refer to simply as analysis, has its beginnings in the rigorous formulation of infinitesimal calculus. It is a branch of pure mathematics that includes the theories of differentiation, integration and measure, limits, infinite series, and analytic functions...
, the
supremum or
least upper bound of a set
S of real numbers is denoted by sup(
S) and is defined to be the smallest real number that is greater than or equal to every number in
S. An important property of the real numbers is its
completenessIn 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...
: every nonempty subset of the set of real numbers that is bounded above has a supremum that is also a real number.
Examples
In the last example, the supremum of a set of
rationalsIn mathematics, a rational number is any number that can be expressed as the quotient or fraction a/b of two integers, with the denominator b not equal to zero. Since b may be equal to 1, every integer is a rational number...
is
irrationalIn mathematics, an irrational number is any real number that cannot be expressed as a ratio a/b, where a and b are integers, with b non-zero, and is therefore not a rational number....
, which means that the rationals are
incompleteIn mathematical analysis, a metric space M is called complete if every Cauchy sequence of points in M has a limit that is also in M or, alternatively, if every Cauchy sequence in M converges in M....
.
One basic property of the supremum is
for any
functionalsIn mathematics, and particularly in functional analysis, a functional is a map from a vector space into its underlying scalar field. In other words, it is a function that takes a vector as its input argument, and returns a scalar...
f and
g.
If, in addition, we define sup(
S) = −∞ when
S is
emptyIn mathematics, and more specifically set theory, the empty set is the unique set having no elements; its size or cardinality is zero. Some axiomatic set theories assure that the empty set exists by including an axiom of empty set; in other theories, its existence can be deduced...
and sup(
S) = +∞ when
S is not bounded above, then every set of real numbers has a supremum under the affinely extended real number system.
If the supremum belongs to the set, then it is the
greatest elementIn mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set is an element of S which is greater than or equal to any other element of S. The term least element is defined dually...
in the set. The term
maximal elementIn 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...
is synonymous as long as one deals with real numbers or any other totally ordered set.
To show that
a = sup(
S), one has to show that
a is an upper bound for
S and that any other upper bound for
S is greater than
a. Equivalently, one could alternatively show that
a is an upper bound for
S and that any number less than
a is not an upper bound for
S.
Suprema within partially ordered sets
Least upper bounds are important concepts in
order theoryOrder 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...
, where they are also called joins (especially in
lattice theoryIn mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...
). As in the special case treated above, a supremum of a given set is just the least element of the set of its
upper boundIn 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...
s, provided that such an element exists.
Formally, we have: For subsets
S of arbitrary
partially ordered setIn 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...
s (
P, ≤), a
supremum or
least upper bound of
S is an element
u in
P such that
- x ≤ u for all x in S, and
- for any v in P such that x ≤ v for all x in S it holds that u ≤ v.
Thus the supremum does not exist if there is no upper bound, or if the set of upper bounds has two or more elements of which none is a least element of that set.
It can easily be shown that, if
S has a supremum, then the supremum is unique (as the least element of any partially ordered set, if it exists, is unique): if
u1 and
u2 are both suprema of
S then it follows that
u1 ≤
u2 and
u2 ≤
u1, and since ≤ is antisymmetric, one finds that
u1 =
u2.
If the supremum exists it may or may not belong to
S. If
S contains a
greatest elementIn mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set is an element of S which is greater than or equal to any other element of S. The term least element is defined dually...
, then that element is the supremum; and if not, then the supremum does not belong to
S.
The
dualIn 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...
concept of supremum, the greatest lower bound, is called
infimumIn mathematics, the infimum of a subset S of some partially ordered set T is the greatest element of T that is less than or equal to all elements of S. Consequently the term greatest lower bound is also commonly used...
and is also known as
meetIn mathematics, join and meet are dual binary operations on the elements of a partially ordered set. A join on a set is defined as the supremum with respect to a partial order on the set, provided a supremum exists...
.
If the supremum of a set
S exists, it can be denoted as sup(
S) or, which is more common in order theory, by
S. Likewise, infima are denoted by inf(
S) or
S. In lattice theory it is common to use the infimum/meet and supremum/join as binary operators; in this case
(and similarly for infima).
A
complete latticeIn mathematics, a complete lattice is a partially ordered set in which all subsets have both a supremum and an infimum . Complete lattices appear in many applications in mathematics and computer science...
is a partially ordered set in which
all subsets have both a supremum (join) and an infimum (meet).
In the sections below the difference between suprema, maximal elements, and minimal upper bounds is stressed. As a consequence of the possible absence of suprema, classes of partially ordered sets for which certain types of subsets are guaranteed to have least upper bound become especially interesting. This leads to the consideration of so-called
completeness propertiesIn 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...
and to numerous definitions of special partially ordered sets.
Examples
The supremum of a subset
S of (ℤ
+, |), where | denotes "
dividesIn mathematics, a divisor of an integer n, also called a factor of n, is an integer which divides n without leaving a remainder.-Explanation:...
", is the lowest common multiple of the elements of
S.
The supremum of a subset
S of (
P, ⊆), where
P is the
power set of some set, is the supremum with respect to ⊆ (subset) of a subset
S of
P is the
unionIn set theory, the union of a collection of sets is the set of all distinct elements in the collection. The union of a collection of sets S_1, S_2, S_3, \dots , S_n\,\! gives a set S_1 \cup S_2 \cup S_3 \cup \dots \cup S_n.- Definition :...
of the elements of
S.
Greatest elements
The distinction between the supremum of a set and the
greatest elementIn mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set is an element of S which is greater than or equal to any other element of S. The term least element is defined dually...
of a set may not be immediately obvious. The difference is that the greatest element must be a member of the set, whereas the supremum need not. For example, consider the set of negative real numbers (excluding zero). This set has no greatest element, since for every element of the set, there is another, larger, element. For instance, for any negative real number
x, there is another negative real number
x/2, which is greater. On the other hand, every real number greater than or equal to zero is certainly an upper bound on this set. Hence, 0 is the least upper bound of the negative reals, so the supremum is 0. This set has a supremum but no greatest element.
In general, this situation occurs for all subsets that do not contain a greatest element. In contrast, if a set does contain a greatest element, then it also has a supremum given by the greatest element.
Maximal elements
For an example where there are no greatest but still some
maximal elementIn 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, consider the set of all subsets of the set of natural numbers (the powerset). We take the usual subset inclusion as an ordering, i.e. a set is greater than another set if it contains all elements of the other set. Now consider the set
S of all sets that contain at most ten natural numbers. The set
S has many maximal elements, i.e. elements for which there is no greater element. In fact, all sets with ten elements are maximal. However, the supremum of
S is the (only and therefore least) set which contains all natural numbers. One can compute the least upper bound of a subset
A of a powerset (i.e.
A is a set of sets) by just taking the union of the elements of
A.
Minimal upper bounds
Finally, a set may have many minimal upper bounds without having a least upper bound. Minimal upper bounds are those upper bounds for which there is no strictly smaller element that also is an upper bound. This does not say that each minimal upper bound is smaller than all other upper bounds, it merely is not greater. The distinction between "minimal" and "least" is only possible when the given order is not a total one. In a totally ordered set, like the real numbers mentioned above, the concepts are the same.
As an example, let
S be the set of all finite subsets of natural numbers and consider the partially ordered set obtained by taking all sets from
S together with the set of
integerThe integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s
Z and the set of positive real numbers
R+, ordered by subset inclusion as above. Then clearly both
Z and
R+ are greater than all finite sets of natural numbers. Yet, neither is
R+ smaller than
Z nor is the converse true: both sets are minimal upper bounds but none is a supremum.
Least-upper-bound property
{{main|Least-upper-bound property}}
The
least-upper-bound property is an example of the aforementioned
completeness propertiesIn 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...
which is typical for the set of real numbers. This property is sometimes called
Dedekind completeness.
If an ordered set
S has the property that every nonempty subset of
S having an upper bound also has a least upper bound, then
S is said to have the least-upper-bound property. As noted above, the set
R of all real numbers has the least-upper-bound property. Similarly, the set
Z of integers has the least-upper-bound property; if
S is a nonempty subset of
Z and there is some number
n such that every element
s of
S is less than or equal to
n, then there is a least upper bound
u for
S, an integer that is an upper bound for
S and is less than or equal to every other upper bound for
S. A
well-orderIn mathematics, a well-order relation on a set S is a strict total order on S with the property that every non-empty subset of S has a least element in this ordering. Equivalently, a well-ordering is a well-founded strict total order...
ed set also has the least-upper-bound property, and the empty subset has also a least upper bound: the minimum of the whole set.
An example of a set that
lacks the least-upper-bound property is
Q, the set of rational numbers. Let
S be the set of all rational numbers
q such that
q2 < 2. Then
S has an upper bound (1000, for example, or 6) but no least upper bound in
Q: If we suppose
p ∈
Q is the least upper bound, a contradiction is immediately deduced because between any two reals
x and
y (including
√{{overlineThe square root of 2, often known as root 2, is the positive algebraic number that, when multiplied by itself, gives the number 2. It is more precisely called the principal square root of 2, to distinguish it from the negative number with the same property.Geometrically the square root of 2 is the...
and
p) there exists some rational
p{{'}}, which itself would have to be the least upper bound (if
p > √{{overline|2}}) or a member of
S greater than
p (if
p < √{{overline|2}}). Another example is the Hyperreals; there is no least upper bound of the set of positive infinitesimals.
There is a corresponding 'greatest-lower-bound property'; an ordered set possesses the greatest-lower-bound property if and only if it also possesses the least-upper-bound property; the least-upper-bound of the set of lower bounds of a set is the greatest-lower-bound, and the greatest-lower-bound of the set of upper bounds of a set is the least-upper-bound of the set.
If in a partially ordered set
P every bounded subset has a supremum, this applies also, for any set
X, in the function space containing all functions from
X to
P, where
f ≤
g if and only if
f(x) ≤
g(x) for all
x in
X. For example, it applies for real functions, and, since these can be considered special cases of functions, for real
n-tuples and sequences of real numbers.
See also
- Infimum
In mathematics, the infimum of a subset S of some partially ordered set T is the greatest element of T that is less than or equal to all elements of S. Consequently the term greatest lower bound is also commonly used...
- Essential suprema and infima
- Uniform norm (supremum norm)
- Limit superior and limit inferior
In mathematics, the limit inferior and limit superior of a sequence can be thought of as limiting bounds on the sequence...
(supremum limit)
- Specker sequence
In computability theory, a Specker sequence is a computable, strictly increasing, bounded sequence of rational numbers whose supremum is not a computable real number. The first example of such a sequence was constructed by Ernst Specker in 1949....
- Upper and lower bounds