Movatterモバイル変換

Monotonic function

From Wikipedia, the free encyclopedia

Order-preserving mathematical function

"Monotonicity" redirects here. For information on monotonicity as it pertains tovoting systems, seemonotonicity criterion. For information on monotonicity as it pertains to logical systems, seeMonotonicity of entailment.

"Monotonic" redirects here. For other uses, seeMonotone (disambiguation).

Figure 1. A monotonically non-decreasing function

Figure 2. A monotonically non-increasing function

Figure 3. A function that isnot monotonic

Inmathematics, amonotonic function (ormonotone function) is afunction betweenordered sets that preserves or reverses the givenorder.^[1]^[2]^[3] This concept first arose incalculus, and was later generalized to the more abstract setting oforder theory.

In calculus and analysis

[edit]

Incalculus, a function $f {\displaystyle f}$ defined on asubset of thereal numbers with real values is calledmonotonic if it is either entirely non-decreasing, or entirely non-increasing.^[2] That is, as per Fig. 1, a function that increases monotonically does not exclusively have to increase, it simply must not decrease.

A function is termedmonotonically increasing (alsoincreasing ornon-decreasing)^[3] if for all $x {\displaystyle x}$ and $y {\displaystyle y}$ such that $x\leq y$ one has $f\!\left(x\right)\leq f\!\left(y\right)$ , so $f {\displaystyle f}$ preserves the order (see Figure 1). Likewise, a function is calledmonotonically decreasing (alsodecreasing ornon-increasing)^[3] if, whenever $x\leq y$ , then $f\!\left(x\right)\geq f\!\left(y\right)$ , so itreverses the order (see Figure 2).

If the order $\leq$ in the definition of monotonicity is replaced by the strict order $<$ , one obtains a stronger requirement. A function with this property is calledstrictly increasing (alsoincreasing).^[3]^[4] Again, by inverting the order symbol, one finds a corresponding concept calledstrictly decreasing (alsodecreasing).^[3]^[4] A function with either property is calledstrictly monotone. Functions that are strictly monotone areone-to-one (because for $x {\displaystyle x}$ not equal to $y {\displaystyle y}$ , either $x<y$ or $x>y$ and so, by monotonicity, either $f\!\left(x\right)<f\!\left(y\right)$ or $f\!\left(x\right)>f\!\left(y\right)$ , thus $f\!\left(x\right)\neq f\!\left(y\right)$ .

To avoid ambiguity, the termsweakly monotone,weakly increasing andweakly decreasing are often used to refer to non-strict monotonicity.

The terms "non-decreasing" and "non-increasing" should not be confused with the (much weaker) negative qualifications "not decreasing" and "not increasing". For example, the non-monotonic function shown in figure 3 first falls, then rises, then falls again. It is therefore not decreasing and not increasing, but it is neither non-decreasing nor non-increasing.

A function $f {\displaystyle f}$ is said to beabsolutely monotonic over an interval $\left(a,b\right)$ if thederivatives of all orders of $f {\displaystyle f}$ arenonnegative or allnonpositive at all points on the interval.

Inverse of function

[edit]

All strictly monotonic functions areinvertible because they are guaranteed to have a one-to-one mapping from their range to their domain.

However, functions that are only weakly monotone need not be invertible; they may be constant on some interval (and therefore not one-to-one).

A function may be strictly monotonic over a limited a range of values and thus have an inverse on that range even though it is not strictly monotonic everywhere. For example, if $y=g(x)$ is strictly increasing on the range $[a,b]$ , then it has an inverse $x=h(y)$ on the range $[g(a),g(b)]$ .

The termmonotonic is sometimes used in place ofstrictly monotonic, so a source may state that all monotonic functions are invertible when they really mean that all strictly monotonic functions are invertible.^{[citation needed]}

Monotonic transformation

[edit]

The termmonotonic transformation (ormonotone transformation) may also cause confusion because it refers to a transformation by a strictly increasing function. This is the case in economics with respect to the ordinal properties of autility function being preserved across a monotonic transform (see alsomonotone preferences).^[5] In this context, the term "monotonic transformation" refers to a positive monotonic transformation and is intended to distinguish it from a "negative monotonic transformation," which reverses the order of the numbers.^[6]

Some basic applications and results

[edit]

Monotonic function with a dense set of jump discontinuities (several sections shown)

The following properties are true for a monotonic function $f\colon \mathbb {R} \to \mathbb {R}$ :

$f {\displaystyle f}$ haslimits from the right and from the left at every point of itsdomain;
$f {\displaystyle f}$ has a limit at positive or negative infinity ( $\pm \infty$ ) of either a real number, $\infty$ , or $-\infty$ .
$f {\displaystyle f}$ can only havejump andremovable discontinuities.
$f {\displaystyle f}$ can only havecountably manydiscontinuities in its domain. The discontinuities, however, do not necessarily consist of isolated points and may even bedense in an interval (a,b). For example, for anysummable sequence $(a_{i})$ of positive numbers and any enumeration $(q_{i})$ of therational numbers, the monotonically increasing function $f(x)=\sum _{q_{i}\leq x}a_{i}$ is continuous exactly at every irrational number (cf. picture). It is thecumulative distribution function of thediscrete measure on the rational numbers, where $a_{i}$ is the weight of $q_{i}$ .
If $f {\displaystyle f}$ isdifferentiable at $x^{*}\in {\mathbb {R}}$ and $f'(x^{*})>0$ , then there is a non-degenerate intervalI such that $x^{*}\in I$ and $f {\displaystyle f}$ is increasing onI. As a partial converse, iff is differentiable and increasing on an interval,I, then its derivative is positive at every point inI.

These properties are the reason why monotonic functions are useful in technical work inanalysis. Other important properties of these functions include:

if $f {\displaystyle f}$ is a monotonic function defined on aninterval $I {\displaystyle I}$ , then $f {\displaystyle f}$ isdifferentiable almost everywhere on $I {\displaystyle I}$ ; i.e. the set of numbers $x {\displaystyle x}$ in $I {\displaystyle I}$ such that $f {\displaystyle f}$ is not differentiable in $x {\displaystyle x}$ hasLebesgue measure zero. In addition, this result cannot be improved to countable: seeCantor function.
if this set is countable, then $f {\displaystyle f}$ is absolutely continuous
if $f {\displaystyle f}$ is a monotonic function defined on an interval $\left[a,b\right]$ , then $f {\displaystyle f}$ isRiemann integrable.

An important application of monotonic functions is inprobability theory. If $X {\displaystyle X}$ is arandom variable, itscumulative distribution function $F_{X}\!\left(x\right)={\text{Prob}}\!\left(X\leq x\right)$ is a monotonically increasing function.

A function isunimodal if it is monotonically increasing up to some point (themode) and then monotonically decreasing.

When $f {\displaystyle f}$ is astrictly monotonic function, then $f {\displaystyle f}$ isinjective on its domain, and if $T {\displaystyle T}$ is therange of $f {\displaystyle f}$ , then there is aninverse function on $T {\displaystyle T}$ for $f {\displaystyle f}$ . In contrast, each constant function is monotonic, but not injective,^[7] and hence cannot have an inverse.

The graphic shows six monotonic functions. Their simplest forms are shown in the plot area and the expressions used to create them are shown on they-axis.

In topology

[edit]

A map $f:X\to Y$ is said to bemonotone if each of itsfibers isconnected; that is, for each element $y\in Y,$ the (possibly empty) set $f^{-1}(y)$ is a connectedsubspace of $X . {\displaystyle X.}$

In functional analysis

[edit]

Infunctional analysis on atopological vector space $X {\displaystyle X}$ , a (possibly non-linear) operator $T:X\rightarrow X^{*}$ is said to be amonotone operator if

$(Tu-Tv,u-v)\geq 0\quad \forall u,v\in X.$ Kachurovskii's theorem shows thatconvex functions onBanach spaces have monotonic operators as their derivatives.

A subset $G {\displaystyle G}$ of $X\times X^{*}$ is said to be amonotone set if for every pair $[u_{1},w_{1}]$ and $[u_{2},w_{2}]$ in $G {\displaystyle G}$ ,

$(w_{1}-w_{2},u_{1}-u_{2})\geq 0.$ $G {\displaystyle G}$ is said to bemaximal monotone if it is maximal among all monotone sets in the sense of set inclusion. The graph of a monotone operator $G(T)$ is a monotone set. A monotone operator is said to bemaximal monotone if its graph is amaximal monotone set.

In order theory

[edit]

Order theory deals with arbitrarypartially ordered sets andpreordered sets as a generalization of real numbers. The above definition of monotonicity is relevant in these cases as well. However, the terms "increasing" and "decreasing" are avoided, since their conventional pictorial representation does not apply to orders that are nottotal. Furthermore, thestrict relations $<$ and $>$ are of little use in many non-total orders and hence no additional terminology is introduced for them.

Letting $\leq$ denote the partial order relation of any partially ordered set, amonotone function, also calledisotone, ororder-preserving, satisfies the property

$x\leq y\implies f(x)\leq f(y)$

for allx andy in its domain. The composite of two monotone mappings is also monotone.

Thedual notion is often calledantitone,anti-monotone, ororder-reversing. Hence, an antitone functionf satisfies the property

$x\leq y\implies f(y)\leq f(x),$

for allx andy in its domain.

Aconstant function is both monotone and antitone; conversely, iff is both monotone and antitone, and if the domain off is alattice, thenf must be constant.

Monotone functions are central in order theory. They appear in most articles on the subject and examples from special applications are found in these places. Some notable special monotone functions areorder embeddings (functions for which $x\leq y$ if and only if $f(x)\leq f(y))$ andorder isomorphisms (surjective order embeddings).

In the context of search algorithms

[edit]

In the context ofsearch algorithms monotonicity (also called consistency) is a condition applied toheuristic functions. A heuristic $h(n)$ is monotonic if, for every noden and every successorn' ofn generated by any actiona, the estimated cost of reaching the goal fromn is no greater than the step cost of getting ton' plus the estimated cost of reaching the goal fromn',

$h(n)\leq c\left(n,a,n'\right)+h\left(n'\right).$

This is a form oftriangle inequality, withn,n', and the goalG_n closest ton. Because every monotonic heuristic is alsoadmissible, monotonicity is a stricter requirement than admissibility. Someheuristic algorithms such asA* can be provenoptimal provided that the heuristic they use is monotonic.^[8]

In Boolean functions

[edit]

With the nonmonotonic function "ifa then bothb andc",false nodes appear abovetrue nodes.

Hasse diagram of the monotonic function "at least two ofa,b,c hold". Colors indicate function output values.

InBoolean algebra, a monotonic function is one such that for alla_i andb_i in{0,1}, ifa₁ ≤b₁,a₂ ≤b₂, ...,a_n ≤b_n (i.e. the Cartesian product{0, 1}ⁿ is orderedcoordinatewise), thenf(a₁, ...,a_n) ≤ f(b₁, ...,b_n). In other words, a Boolean function is monotonic if, for every combination of inputs, switching one of the inputs from false to true can only cause the output to switch from false to true and not from true to false. Graphically, this means that ann-ary Boolean function is monotonic when its representation as ann-cube labelled with truth values has no upward edge fromtrue tofalse. (This labelledHasse diagram is thedual of the function's labelledVenn diagram, which is the more common representation forn ≤ 3.)

The monotonic Boolean functions are precisely those that can be defined by an expression combining the inputs (which may appear more than once) using only the operatorsand andor (in particularnot is forbidden). For instance "at least two ofa,b,c hold" (the ternarymajority function) is a monotonic function ofa,b,c, since it can be written for instance as ((a andb) or (a andc) or (b andc)).

The number of such functions onn variables is known as theDedekind number ofn.

SAT solving, generally anNP-hard task, can be achieved efficiently when all involved functions and predicates are monotonic and Boolean.^[9]

Notes

[edit]

^Clapham, Christopher; Nicholson, James (2014).Oxford Concise Dictionary of Mathematics (5th ed.). Oxford University Press.
^^a ^bStover, Christopher."Monotonic Function".Wolfram MathWorld. Retrieved2018-01-29.
^^a ^b ^c ^d ^e"Monotone function".Encyclopedia of Mathematics. Retrieved2018-01-29.
^^a ^bSpivak, Michael (1994).Calculus. Houston, Texas: Publish or Perish, Inc. p. 192.ISBN 0-914098-89-6.
^See the section on Cardinal Versus Ordinal Utility inSimon & Blume (1994).
^Varian, Hal R. (2010).Intermediate Microeconomics (8th ed.). W. W. Norton & Company. p. 56.ISBN 9780393934243.
^if its domain has more than one element
^Conditions for optimality: Admissibility and consistency pg. 94–95 (Russell & Norvig 2010).
^Bayless, Sam; Bayless, Noah; Hoos, Holger H.; Hu, Alan J. (2015).SAT Modulo Monotonic Theories. Proc. 29th AAAI Conf. on Artificial Intelligence. AAAI Press. pp. 3702–3709.arXiv:1406.0043.doi:10.1609/aaai.v29i1.9755.Archived from the original on Dec 11, 2023.

Bibliography

[edit]

Bartle, Robert G. (1976).The elements of real analysis (second ed.).
Grätzer, George (1971).Lattice theory: first concepts and distributive lattices. W. H. Freeman.ISBN 0-7167-0442-0.
Pemberton, Malcolm; Rau, Nicholas (2001).Mathematics for economists: an introductory textbook. Manchester University Press.ISBN 0-7190-3341-1.
Renardy, Michael & Rogers, Robert C. (2004).An introduction to partial differential equations. Texts in Applied Mathematics 13 (Second ed.). New York: Springer-Verlag. p. 356.ISBN 0-387-00444-0.
Riesz, Frigyes & Béla Szőkefalvi-Nagy (1990).Functional Analysis. Courier Dover Publications.ISBN 978-0-486-66289-3.
Russell, Stuart J.; Norvig, Peter (2010).Artificial Intelligence: A Modern Approach (3rd ed.). Upper Saddle River, New Jersey: Prentice Hall.ISBN 978-0-13-604259-4.
Simon, Carl P.; Blume, Lawrence (April 1994).Mathematics for Economists (first ed.). Norton.ISBN 978-0-393-95733-4. (Definition 9.31)

External links

[edit]

"Monotone function",Encyclopedia of Mathematics,EMS Press, 2001 [1994]
Convergence of a Monotonic Sequence by Anik Debnath and Thomas Roxlo (The Harker School),Wolfram Demonstrations Project.
Weisstein, Eric W."Monotonic Function".MathWorld.

v t e Order theory
Topics Glossary Category
Key concepts	Binary relation Boolean algebra Cyclic order Lattice Partial order Preorder Total order Weak ordering
Results	Boolean prime ideal theorem Cantor–Bernstein theorem Cantor's isomorphism theorem Dilworth's theorem Dushnik–Miller theorem Hausdorff maximal principle Knaster–Tarski theorem Kruskal's tree theorem Laver's theorem Mirsky's theorem Szpilrajn extension theorem Zorn's lemma
Properties & Types (list)	Antisymmetric Asymmetric Boolean algebra topics Completeness Connected Covering Dense Directed (Partial) Equivalence Foundational Heyting algebra Homogeneous Idempotent Lattice Bounded Complemented Complete Distributive Join and meet Reflexive Partial order Chain-complete Graded Eulerian Strict Prefix order Preorder Total Semilattice Semiorder Symmetric Total Tolerance Transitive Well-founded Well-quasi-ordering (Better) (Pre) Well-order
Constructions	Composition Converse/Transpose Lexicographic order Linear extension Product order Reflexive closure Series-parallel partial order Star product Symmetric closure Transitive closure
Topology & Orders	Alexandrov topology &Specialization preorder Ordered topological vector space Normal cone Order topology Order topology Topological vector lattice Banach Fréchet Locally convex Normed
Related	Antichain Cofinal Cofinality Comparability Graph Duality Filter Hasse diagram Ideal Net Subnet Order morphism Embedding Isomorphism Order type Ordered field Positive cone of an ordered field Ordered vector space Partially ordered Positive cone of an ordered vector space Riesz space Partially ordered group Positive cone of a partially ordered group Upper set Young's lattice