Upper and lower bounds
From Wikipedia, the free encyclopedia
This article is about order theory and lattice theory. For analysis of algorithms in computational complexity, see Big O notation.
In mathematics, especially in order theory, an upper bound of a subset S of some partially ordered set (P, ≤) 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. 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 empty subset Φ of a partially ordered set P is conventionally considered to be both bounded from above and bounded from below with every element of P being both upper and lower bound of Φ. Formally, given a partially ordered set (P, ≤), an element u of P is an upper bound of a subset S of P, if
Using ≥ instead of ≤ leads to the dual definition of a lower bound of S.
PropertiesA subset S of a partially ordered set P may fail to have any bounds or may have many different upper and lower bounds. By transitivity, any element greater than or equal to an upper bound of S is again an upper bound of S, and any element lesser than or equal to any lower bound of S is again a lower bound of S. The bounds of a subset S of a partially ordered set P may or may not be elements of S itself. If S contains an upper bound then that upper bound is unique and is called the greatest element of S. The greatest element of S (if it exists) is also the least upper bound of S. Distinctions between upper bounds, least upper bounds/supremumsThe transitivity property leads to the consideration of least upper bounds (or suprema) and greatest lower bounds (or infima). ExamplesEvery subset of the natural numbers has a lower bound or an upper bound. Every finite subset of a totally ordered set has both upper and lower bounds. 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. A special situation does occur when a subset is equal to the set of lower bounds of its own set of upper bounds. This observation leads to the definition of Dedekind cuts. Further introductory information is found in the article on order theory. Bounds of functionsThe definitions can be generalised to sets of functions. Let S be a set of functions Failed to parse (Missing texvc executable; please see math/README to configure.): S=\{f_1(\cdot), f_2(\cdot), \dots\} , with domain F and having a partially ordered set as a codomain. A function Failed to parse (Missing texvc executable; please see math/README to configure.): g(\cdot) with domain Failed to parse (Missing texvc executable; please see math/README to configure.): G \supseteq F is an upper bound of S if Failed to parse (Missing texvc executable; please see math/README to configure.): f_i(x) \le g(x) for each function Failed to parse (Missing texvc executable; please see math/README to configure.): f_i(\cdot) in the set and for each x in F. In particular, Failed to parse (Missing texvc executable; please see math/README to configure.): g(\cdot) is said to be an upper bound of Failed to parse (Missing texvc executable; please see math/README to configure.): f(\cdot) when S consists of only one function Failed to parse (Missing texvc executable; please see math/README to configure.): f(\cdot) (i.e. S is a singleton). Note that this does not imply that Failed to parse (Missing texvc executable; please see math/README to configure.): f(\cdot) is a lower bound of Failed to parse (Missing texvc executable; please see math/README to configure.): g(\cdot) . See alsode:Schranke (Mathematik) es:Mayorante fr:Majorant it:Maggiorante he:חסם (מתמטיקה) pl:Ograniczenie górne sv:Uppåt begränsad |
