Upper and lower bounds

Upper and lower bounds

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 Φ. For example, if the number was 7.5, the lower bound would be 7.44999999 infinity but that cannot be expressed on a number line so it would have to be 7.45. The upper bound would be 7.55 and no higher.

Formally, given a partially ordered set ("P", ≤), an element "u" of "P" is an upper bound of a subset "S" of "P", if

: "s" ≤ "u", for all elements "s" of "S".

Using ≥ instead of ≤ leads to the dual definition of a lower bound of "S".

Properties

A 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/supremums

The transitivity property leads to the consideration of least upper bounds (or "suprema") and greatest lower bounds (or "infima").

Examples

Every 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 functions

The definitions can be generalised to sets of functions.

Let "S" be a set of functions S={f_1(cdot), f_2(cdot), dots}, with domain "F" and having a partially ordered set as a codomain.

A function g(cdot) with domain G supseteq F is an "upper bound" of "S" if f_i(x) le g(x) for each function f_i(cdot) in the set and for each "x" in "F".

In particular, g(cdot) is said to be an "upper bound" of f(cdot) when "S" consists of only one function f(cdot) (i.e. "S" is a singleton). Note that this does not imply that f(cdot) is a "lower bound" of g(cdot).

ee also

*ml|Bounded_set|Boundedness_in_order_theory|boundedness in order theory
*Bound graph


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Branch and bound — (BB) is a general algorithm for finding optimal solutions of various optimization problems, especially in discrete and combinatorial optimization. It consists of a systematic enumeration of all candidate solutions, where large subsets of… …   Wikipedia

  • Comparison of Java and C++ — Programming language comparisons General comparison Basic syntax Basic instructions Arrays Associative arrays String operations …   Wikipedia

  • Covariance and contravariance (computer science) — Within the type system of a programming language, covariance and contravariance refers to the ordering of types from narrower to wider and their interchangeability or equivalence in certain situations (such as parameters, generics, and return… …   Wikipedia

  • Least upper bound axiom — The least upper bound axiom, also abbreviated as the LUB axiom, is an axiom of real analysis stating that if a nonempty subset of the real numbers has an upper bound, then it has a least upper bound. It is an axiom in the sense that it cannot be… …   Wikipedia

  • Bounds checking — In computer programming, bounds checking is any method of detecting whether a variable is within some bounds before its use. It is particularly relevant to a variable used as an index into an array to ensure its value lies within the bounds of… …   Wikipedia

  • upper bound — noun (mathematics) a number equal to or greater than any other number in a given set • Topics: ↑mathematics, ↑math, ↑maths • Hypernyms: ↑boundary, ↑edge, ↑bound * * * Math. an element …   Useful english dictionary

  • upper bound — Math. an element greater than or equal to all the elements in a given set: 3 and 4 are upper bounds of the set consisting of 1, 2, and 3. Cf. bound3 (def. 4), greatest lower bound, least upper bound, lower bound. * * * …   Universalium

  • Comparison of Pascal and C — Programming language comparisons General comparison Basic syntax Basic instructions Arrays Associative arrays String operations …   Wikipedia

  • Join and meet — In 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 (necessarily unique) supremum (least upper bound) with respect to a partial order on the set, provided a… …   Wikipedia

  • Limit superior and limit inferior — In mathematics, the limit inferior (also called infimum limit, liminf, inferior limit, lower limit, or inner limit) and limit superior (also called supremum limit, limsup, superior limit, upper limit, or outer limit) of a sequence can be thought… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”