Upper and lower bounds: Difference between revisions
Content deleted Content added
Undid revision 951079997 by 2405:204:A127:D866:28A5:6D5C:9C8E:4B57 (talk): Not a typo? |
Citation bot (talk | contribs) Altered template type. Add: doi, pages, issue, volume, date, journal, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Whoop whoop pull up | #UCB_webform 1079/3309 |
||
| (40 intermediate revisions by 30 users not shown) | |||
| Line 1: | Line 1: | ||
{{short description|Majorant and minorant in mathematics}} |
|||
{{About|precise bounds|asymptotic bounds|Big O notation}} |
{{About|precise bounds|asymptotic bounds|Big O notation}} |
||
{{more footnotes|date=March 2012}} |
|||
[[File:Illustration of supremum.svg|thumb|300px|A set with upper bounds and its least upper bound]] |
[[File:Illustration of supremum.svg|thumb|300px|A set with upper bounds and its least upper bound]] |
||
In mathematics, particularly in [[order theory]], an '''upper bound''' of a [[subset]] {{mvar|S}} of some [[partially ordered set]] {{math|(''K'', ≤)}} is an element of {{mvar|K}} which is [[greater than or equal to]] every element of {{mvar|S}}.<ref name="MacLane-Birkhoff" /><ref>{{Cite web|url=https://www.mathsisfun.com/definitions/upper-bound.html|title=Upper Bound Definition (Illustrated Mathematics Dictionary)|website=www.mathsisfun.com|access-date=2019-12-03}}</ref> [[Duality (order theory)|Dually]], a '''lower bound''' of {{mvar|S}} is defined to be an element of {{mvar|K}} which is less than or equal to every element of {{mvar|S}}. A set with an upper (respectively, lower) bound is said to be '''bounded from above''' (respectively '''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.<ref>{{Cite web|url=http://mathworld.wolfram.com/UpperBound.html|title=Upper Bound|last=Weisstein|first=Eric W.|website=mathworld.wolfram.com|language=en|access-date=2019-12-03}}</ref> |
|||
In [[mathematics]], particularly in [[order theory]], an '''upper bound''' or '''majorant'''<ref name=schaefer/> of a [[subset]] {{mvar|S}} of some [[Preorder|preordered set]] {{math|(''K'', ≤)}} is an element of {{mvar|K}} that is {{nobr|[[greater than or equal to]]}} every element of {{mvar|S}}.<ref name="MacLane-Birkhoff" /><ref>{{Cite web|url=https://www.mathsisfun.com/definitions/upper-bound.html|title=Upper Bound Definition (Illustrated Mathematics Dictionary)|website=Math is Fun|access-date=2019-12-03}}</ref> |
|||
[[Duality (order theory)|Dually]], a '''lower bound''' or '''minorant''' of {{mvar|S}} is defined to be an element of {{mvar|K}} that is less than or equal to every element of {{mvar|S}}. |
|||
A set with an upper (respectively, lower) bound is said to be '''bounded from above''' or '''majorized'''<ref name=schaefer/> (respectively '''bounded from below''' or '''minorized''') by that bound. |
|||
The terms '''bounded above''' ('''bounded below''') are also used in the mathematical literature for sets that have upper (respectively lower) bounds.<ref>{{Cite web|url=http://mathworld.wolfram.com/UpperBound.html|title=Upper Bound|last=Weisstein|first=Eric W.|website=mathworld.wolfram.com|language=en|access-date=2019-12-03}}</ref> |
|||
== Examples == |
== Examples == |
||
For example, {{math|5}} is a lower bound for the set {{math|1=''S'' = {{mset|5, 8, 42, 34, 13934}}}} (as a subset of the [[integers]] or of the [[real numbers]], etc.), and so is {{math|4}}. On the other hand, {{math|6}} is not a lower bound for {{mvar|S}} since it is not smaller than every element in {{mvar|S}}. |
For example, {{math|5}} is a lower bound for the set {{math|1=''S'' = {{mset|5, 8, 42, 34, 13934}}}} (as a subset of the [[integers]] or of the [[real numbers]], etc.), and so is {{math|4}}. On the other hand, {{math|6}} is not a lower bound for {{mvar|S}} since it is not smaller than every element in {{mvar|S}}. {{math|13934}} and other numbers ''x'' such that {{math|x ≥ 13934}} would be an upper bound for ''S''. |
||
The set {{math|1=''S'' = {{mset|42}}}} has {{math|42}} as both an upper bound and a lower bound; all other numbers are either an upper bound or a lower bound for that {{mvar|S}}. |
The set {{math|1=''S'' = {{mset|42}}}} has {{math|42}} as both an upper bound and a lower bound; all other numbers are either an upper bound or a lower bound for that {{mvar|S}}. |
||
Every subset of the [[natural number]]s has a lower bound |
Every subset of the [[natural number]]s has a lower bound since the natural numbers have a least element (0 or 1, depending on convention). 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 number]]s 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. |
Every finite subset of a non-empty [[totally ordered set]] has both upper and lower bounds. |
||
| Line 19: | Line 22: | ||
The definitions can be generalized to [[Function (mathematics)|functions]] and even to sets of functions. |
The definitions can be generalized to [[Function (mathematics)|functions]] and even to sets of functions. |
||
Given a function {{italics correction|{{mvar|f}}}} with [[Domain |
Given a function {{italics correction|{{mvar|f}}}} with [[Domain of a function|domain]] {{mvar|D}} and a preordered set {{math|(''K'', ≤)}} as [[codomain]], an element {{mvar|''y''}} of {{mvar|K}} is an upper bound of {{italics correction|{{mvar|f}}}} if {{math|''y'' ≥ {{italics correction|''f''}}(''x'')}} for each {{mvar|x}} in {{mvar|D}}. The upper bound is called ''[[Mathematical jargon#sharp|sharp]]'' if equality holds for at least one value of {{mvar|x}}. It indicates that the constraint is optimal, and thus cannot be further reduced without invalidating the inequality. |
||
Similarly, function {{mvar|g}} defined on domain {{mvar|D}} and having the same codomain {{math|(''K'', ≤)}} is an upper bound of {{italics correction|{{mvar|f}}}}, if {{math|''g''(''x'') ≥ {{italics correction|''f''}}(''x'')}} for each {{mvar|x}} in {{mvar|D}}. |
Similarly, a function {{mvar|g}} defined on domain {{mvar|D}} and having the same codomain {{math|(''K'', ≤)}} is an upper bound of {{italics correction|{{mvar|f}}}}, if {{math|''g''(''x'') ≥ {{italics correction|''f''}}(''x'')}} for each {{mvar|x}} in {{mvar|D}}. The function {{mvar|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, by replacing ≥ with |
The notion of lower bound for (sets of) functions is defined analogously, by replacing ≥ with ≤. |
||
==Tight bounds== |
==Tight bounds== |
||
| Line 29: | Line 32: | ||
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. |
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. |
||
==Exact upper bounds== |
|||
| ⚫ | |||
An upper bound {{mvar|u}} of a subset {{mvar|S}} of a preordered set {{math|(''K'', ≤)}} is said to be an ''exact upper bound'' for {{mvar|S}} if every element of {{mvar|K}} that is strictly majorized by {{mvar|u}} is also majorized by some element of {{mvar|S}}. Exact upper bounds of [[reduced product|reduced products]] of [[linear order|linear orders]] play an important role in [[PCF theory]].<ref>{{Cite journal|url=https://www.sciencedirect.com/science/article/pii/S0168007298000116|title=Exact upper bounds and their uses in set theory|last=Kojman|first=Menachem|journal=Annals of Pure and Applied Logic |date=21 August 1998 |volume=92 |issue=3 |pages=267–282 |doi=10.1016/S0168-0072(98)00011-6 }}</ref> |
|||
| ⚫ | |||
| ⚫ | <ref name="MacLane-Birkhoff">{{cite book | last1 = Mac Lane| first1 = Saunders | author1-link = Saunders Mac Lane | last2 = Birkhoff| first2 = Garrett | author2-link = Garrett Birkhoff | title = Algebra | place = Providence, RI | publisher = [[American Mathematical Society]] | page = 145 | year = 1991 | isbn = 0-8218-1646-2 }}</ref> |
||
== See also == |
|||
* [[Greatest element and least element]] |
|||
* [[Infimum and supremum]] |
|||
* [[Maximal and minimal elements]] |
|||
| ⚫ | |||
| ⚫ | |||
| ⚫ | <ref name="MacLane-Birkhoff">{{cite book | last1 = Mac Lane| first1 = Saunders | author1-link = Saunders Mac Lane | last2 = Birkhoff| first2 = Garrett | author2-link = Garrett Birkhoff | title = Algebra | url = https://archive.org/details/algebra00lane| url-access = limited| place = Providence, RI | publisher = [[American Mathematical Society]] | page = [https://archive.org/details/algebra00lane/page/n164 145] | year = 1991 | isbn = 0-8218-1646-2 }}</ref> |
||
<!-- <ref name="Davey-Priestley"> {{cite book| author = B. A. Davey and H. A. Priestley| year =2002| title = Introduction to Lattices and Order| edition = 2nd | publisher = Cambridge University Press| isbn= 0-521-78451-4}} </ref> --> |
<!-- <ref name="Davey-Priestley"> {{cite book| author = B. A. Davey and H. A. Priestley| year =2002| title = Introduction to Lattices and Order| edition = 2nd | publisher = Cambridge University Press| isbn= 0-521-78451-4}} </ref> --> |
||
<ref name=schaefer>{{cite book | last1=Schaefer | first1=Helmut H. | author-link=Helmut H. Schaefer | last2=Wolff | first2=Manfred P. | title=Topological Vector Spaces | publisher=Springer New York Imprint Springer | series=[[Graduate Texts in Mathematics|GTM]] | volume=8 |page=3 | publication-place=New York, NY | year=1999 | isbn=978-1-4612-7155-0 | oclc=840278135 }} <!-- {{sfn | Schaefer | 1999 | p=}} --> </ref> |
|||
}} |
}} |
||
| Line 40: | Line 54: | ||
[[de:Schranke (Mathematik)]] |
[[de:Schranke (Mathematik)]] |
||
[[es:Mayorante]] |
|||
[[pl:Kresy dolny i górny]] |
[[pl:Kresy dolny i górny]] |
||
Latest revision as of 13:18, 26 September 2024
In mathematics, particularly in order theory, an upper bound or majorant[1] of a subset S of some preordered set (K, ≤) is an element of K that is greater than or equal to every element of S.[2][3] Dually, a lower bound or minorant of S is defined to be an element of K that is less than or equal to every element of S. A set with an upper (respectively, lower) bound is said to be bounded from above or majorized[1] (respectively bounded from below or minorized) by that bound. The terms bounded above (bounded below) are also used in the mathematical literature for sets that have upper (respectively lower) bounds.[4]
Examples
[edit]For example, 5 is a lower bound for the set S = {5, 8, 42, 34, 13934} (as a subset of the integers or of the real numbers, etc.), and so is 4. On the other hand, 6 is not a lower bound for S since it is not smaller than every element in S. 13934 and other numbers x such that x ≥ 13934 would be an upper bound for S.
The set S = {42} has 42 as both an upper bound and a lower bound; all other numbers are either an upper bound or a lower bound for that S.
Every subset of the natural numbers has a lower bound since the natural numbers have a least element (0 or 1, depending on convention). 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
[edit]The definitions can be generalized to functions and even to sets of functions.
Given a function f with domain D and a preordered set (K, ≤) as codomain, an element y of K is an upper bound of f if y ≥ f(x) for each x in D. The upper bound is called sharp if equality holds for at least one value of x. It indicates that the constraint is optimal, and thus cannot be further reduced without invalidating the inequality.
Similarly, a function g defined on domain D and having the same codomain (K, ≤) is an upper bound of f, if g(x) ≥ f(x) for each x in D. The 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, by replacing ≥ with ≤.
Tight bounds
[edit]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.
Exact upper bounds
[edit]An upper bound u of a subset S of a preordered set (K, ≤) is said to be an exact upper bound for S if every element of K that is strictly majorized by u is also majorized by some element of S. Exact upper bounds of reduced products of linear orders play an important role in PCF theory.[5]
See also
[edit]References
[edit]- ^ a b Schaefer, Helmut H.; Wolff, Manfred P. (1999). Topological Vector Spaces. GTM. Vol. 8. New York, NY: Springer New York Imprint Springer. p. 3. ISBN 978-1-4612-7155-0. OCLC 840278135.
- ^ Mac Lane, Saunders; Birkhoff, Garrett (1991). Algebra. Providence, RI: American Mathematical Society. p. 145. ISBN 0-8218-1646-2.
- ^ "Upper Bound Definition (Illustrated Mathematics Dictionary)". Math is Fun. Retrieved 2019-12-03.
- ^ Weisstein, Eric W. "Upper Bound". mathworld.wolfram.com. Retrieved 2019-12-03.
- ^ Kojman, Menachem (21 August 1998). "Exact upper bounds and their uses in set theory". Annals of Pure and Applied Logic. 92 (3): 267–282. doi:10.1016/S0168-0072(98)00011-6.