Upper and lower bounds

This article is about precise bounds. For asymptotic bounds, see Big O notation.

A set with upper bounds and its least upper bound.

In mathematics, especially in order theory, an upper bound of a subset S of some partially ordered set (K, ≤) is an element of K which is greater than or equal to every element of S.^[1] The term lower bound is defined dually as an element of K which is less than or equal to every element of S. A set with an upper bound is said to be bounded from above by that bound, a set with a lower bound is said to be bounded from below by that bound. The terms bounded above (bounded below) are also used in the mathematical literature for sets that have upper (respectively lower) bounds.

Examples

For example, 5 is a lower bound for the set { 5, 8, 42, 34, 13934 }; so is 4; but 6 is not.

Another example: for the set { 42 }, the number 42 is both an upper bound and a lower bound; all other real numbers are either an upper bound or a lower bound for that set.

Every subset of the natural numbers has a lower bound, since the natural numbers have a least element (0, or 1 depending on the exact definition of natural numbers). An infinite subset of the natural numbers cannot be bounded from above. An infinite subset of the integers may be bounded from below or bounded from above, but not both. An infinite subset of the rational numbers may or may not be bounded from below and may or may not be bounded from above.

Every finite subset of a non-empty totally ordered set has both upper and lower bounds.

Bounds of functions

The definitions can be generalized to functions and even sets of functions.

Given a function $f$ with domain $D$ and a partially ordered set $(K, \leq)$ as codomain, an element $y$ of $K$ is an upper bound of $f$ if $y \geq f (x)$ for each $x$ in $D$ . The upper bound is called sharp if equality holds for at least one value of $x$ .

Function $g$ defined on domain $D$ and having the same codomain $(K, \leq)$ is an upper bound of $f$ if $g (x) \geq f (x)$ for each $x$ in $D$ .

Function $g$ is further said to be an upper bound of a set of functions if it is an upper bound of each function in that set.

The notion of lower bound for (sets of) functions is defined analogously, with ≤ replacing ≥.

Tight bounds

An upper bound is said to be a tight upper bound, a least upper bound, or a supremum if no smaller value is an upper bound. Similarly a lower bound is said to be a tight lower bound, a greatest lower bound, or an infimum if no greater value is a lower bound.

References

↑ Mac Lane, Saunders; Birkhoff, Garrett (1991). Algebra. Providence, RI: American Mathematical Society. p. 145. ISBN 0-8218-1646-2.

This article is issued from Wikipedia - version of the 6/5/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.