Monotonic function - Wikipedia

In mathematics, a monotonic function (or monotone function) is a function between ordered sets that preserves or reverses the given order. Monotonicfunction FromWikipedia,thefreeencyclopedia Jumptonavigation Jumptosearch Order-preservingmathematicalfunction "Monotonicity"redirectshere.Forinformationonmonotonicityasitpertainstovotingsystems,seemonotonicitycriterion.Forinformationonmonotonicityasitpertainstologicalsystems,seeMonotonicityofentailment. "Monotonic"redirectshere.Forotheruses,seeMonotone(disambiguation). Figure1.Amonotonicallynon-decreasingfunction. Figure2.Amonotonicallynon-increasingfunction Figure3.Afunctionthatisnotmonotonic Inmathematics,amonotonicfunction(ormonotonefunction)isafunctionbetweenorderedsetsthatpreservesorreversesthegivenorder.[1][2][3]Thisconceptfirstaroseincalculus,andwaslatergeneralizedtothemoreabstractsettingofordertheory. Contents 1Incalculusandanalysis 1.1Inverseoffunction 1.2Monotonictransformation 1.3Somebasicapplicationsandresults 2Intopology 3Infunctionalanalysis 4Inordertheory 5Inthecontextofsearchalgorithms 6InBooleanfunctions 7Seealso 8Notes 9Bibliography 10Externallinks Incalculusandanalysis[edit] Incalculus,afunction f {\displaystylef} definedonasubsetoftherealnumberswithrealvaluesiscalledmonotonicifandonlyifitiseitherentirelynon-increasing,orentirelynon-decreasing.[2]Thatis,asperFig.1,afunctionthatincreasesmonotonicallydoesnotexclusivelyhavetoincrease,itsimplymustnotdecrease. Afunctioniscalledmonotonicallyincreasing(alsoincreasingornon-decreasing),[3]ifforall x {\displaystylex} and y {\displaystyley} suchthat x ≤ y {\displaystylex\leqy} onehas f ( x ) ≤ f ( y ) {\displaystylef\!\left(x\right)\leqf\!\left(y\right)} ,so f {\displaystylef} preservestheorder(seeFigure1).Likewise,afunctioniscalledmonotonicallydecreasing(alsodecreasingornon-increasing)[3]if,whenever x ≤ y {\displaystylex\leqy} ,then f ( x ) ≥ f ( y ) {\displaystylef\!\left(x\right)\geqf\!\left(y\right)} ,soitreversestheorder(seeFigure2). Iftheorder ≤ {\displaystyle\leq} inthedefinitionofmonotonicityisreplacedbythestrictorder < {\displaystyle y {\displaystylex>y} andso,bymonotonicity,either f ( x ) < f ( y ) {\displaystylef\!\left(x\right) f ( y ) {\displaystylef\!\left(x\right)>f\!\left(y\right)} ,thus f ( x ) ≠ f ( y ) {\displaystylef\!\left(x\right)\neqf\!\left(y\right)} .) Ifitisnotclearthat"increasing"and"decreasing"aretakentoincludethepossibilityofrepeatingthesamevalueatsuccessivearguments,onemayusethetermsweaklymonotone,weaklyincreasingandweaklydecreasingtostressthispossibility. Theterms"non-decreasing"and"non-increasing"shouldnotbeconfusedwiththe(muchweaker)negativequalifications"notdecreasing"and"notincreasing".Forexample,thefunctionoffigure3firstfalls,thenrises,thenfallsagain.Itisthereforenotdecreasingandnotincreasing,butitisneithernon-decreasingnornon-increasing. Afunction f ( x ) {\displaystylef\!\left(x\right)} issaidtobeabsolutelymonotonicoveraninterval ( a , b ) {\displaystyle\left(a,b\right)} ifthederivativesofallordersof f {\displaystylef} arenonnegativeorallnonpositiveatallpointsontheinterval. Inverseoffunction[edit] Afunctionthatismonotonic,butnotstrictlymonotonic,andthusconstantonaninterval,doesn'thaveaninverse.Thisisbecauseinorderforafunctiontohaveaninverse,thereneedstobeaone-to-onemappingfromtherangetothedomainofthefunction.Sinceamonotonicfunctionhassomevaluesthatareconstantinitsdomain,thismeansthattherewouldbemorethanonevalueintherangethatmapstothisconstantvalue. However,afunctiony=g(x)thatisstrictlymonotonic,hasaninversefunctionsuchthatx=h(y)becausethereisguaranteedtoalwaysbeaone-to-onemappingfromrangetodomainofthefunction.Also,afunctioncanbesaidtobestrictlymonotoniconarangeofvalues,andthushaveaninverseonthatrangeofvalue.Forexample,ify=g(x)isstrictlymonotonicontherange[a,b],thenithasaninversex=h(y)ontherange[g(a),g(b)],butwecannotsaytheentirerangeofthefunctionhasaninverse. Note,sometextbooks[which?]mistakenlystatethataninverseexistsforamonotonicfunction,whentheyreallymeanthataninverseexistsforastrictlymonotonicfunction. Monotonictransformation[edit] Thetermmonotonictransformation(ormonotonetransformation)canalsopossiblycausesomeconfusionbecauseitreferstoatransformationbyastrictlyincreasingfunction.Thisisthecaseineconomicswithrespecttotheordinalpropertiesofautilityfunctionbeingpreservedacrossamonotonictransform(seealsomonotonepreferences).[5]Inthiscontext,whatwearecallinga"monotonictransformation"is,moreaccurately,calleda"positivemonotonictransformation",inordertodistinguishitfroma“negativemonotonictransformation,”whichreversestheorderofthenumbers.[6] Somebasicapplicationsandresults[edit] Monotonicfunctionwithadensesetofjumpdiscontinuities(severalsectionsshown) Thefollowingpropertiesaretrueforamonotonicfunction f : R → R {\displaystylef\colon\mathbb{R}\to\mathbb{R}} : f {\displaystylef} haslimitsfromtherightandfromtheleftateverypointofitsdomain; f {\displaystylef} hasalimitatpositiveornegativeinfinity( ± ∞ {\displaystyle\pm\infty} )ofeitherarealnumber, ∞ {\displaystyle\infty} ,or − ∞ {\displaystyle-\infty} . f {\displaystylef} canonlyhavejumpdiscontinuities; f {\displaystylef} canonlyhavecountablymanydiscontinuitiesinitsdomain.Thediscontinuities,however,donotnecessarilyconsistofisolatedpointsandmayevenbedenseinaninterval(a,b).Forexample,foranysummablesequence ( a i ) (a_{i}) ofpositivenumbersandanyenumeration ( q i ) {\displaystyle(q_{i})} oftherationalnumbers,themonotonicallyincreasingfunction f ( x ) = ∑ q i ≤ x a i {\displaystylef(x)=\sum_{q_{i}\leqx}a_{i}} iscontinuousexactlyateveryirrationalnumber(cf.picture).Itisthecumulativedistributionfunctionofthediscretemeasureontherationalnumbers,where a i {\displaystylea_{i}} istheweightof q i {\displaystyleq_{i}} . Thesepropertiesarethereasonwhymonotonicfunctionsareusefulintechnicalworkinanalysis.Somemorefactsaboutthesefunctionsare: if f {\displaystylef} isamonotonicfunctiondefinedonaninterval I {\displaystyleI} ,then f {\displaystylef} isdifferentiablealmosteverywhereon I {\displaystyleI} ;i.e.thesetofnumbers x {\displaystylex} in I {\displaystyleI} suchthat f {\displaystylef} isnotdifferentiablein x {\displaystylex} hasLebesguemeasurezero.Inaddition,thisresultcannotbeimprovedtocountable:seeCantorfunction. ifthissetiscountable,then f {\displaystylef} isabsolutelycontinuous if f {\displaystylef} isamonotonicfunctiondefinedonaninterval [ a , b ] {\displaystyle\left[a,b\right]} ,then f {\displaystylef} isRiemannintegrable. Animportantapplicationofmonotonicfunctionsisinprobabilitytheory.If X {\displaystyleX} isarandomvariable,itscumulativedistributionfunction F X ( x ) = Prob ( X ≤ x ) {\displaystyleF_{X}\!\left(x\right)={\text{Prob}}\!\left(X\leqx\right)} isamonotonicallyincreasingfunction. Afunctionisunimodalifitismonotonicallyincreasinguptosomepoint(themode)andthenmonotonicallydecreasing. When f {\displaystylef} isastrictlymonotonicfunction,then f {\displaystylef} isinjectiveonitsdomain,andif T {\displaystyleT} istherangeof f {\displaystylef} ,thenthereisaninversefunctionon T {\displaystyleT} for f {\displaystylef} .Incontrast,eachconstantfunctionismonotonic,butnotinjective,[7]andhencecannothaveaninverse. Intopology[edit] Amap f : X → Y {\displaystylef:X\toY} issaidtobemonotoneifeachofitsfibersisconnected;thatis,foreachelement y ∈ Y , {\displaystyley\inY,} the(possiblyempty)set f − 1 ( y ) {\displaystylef^{-1}(y)} isaconnectedsubspaceof X . {\displaystyleX.} Infunctionalanalysis[edit] Infunctionalanalysisonatopologicalvectorspace X {\displaystyleX} ,a(possiblynon-linear)operator T : X → X ∗ {\displaystyleT:X\rightarrowX^{*}} issaidtobeamonotoneoperatorif ( T u − T v , u − v ) ≥ 0 ∀ u , v ∈ X . {\displaystyle(Tu-Tv,u-v)\geq0\quad\forallu,v\inX.} Kachurovskii'stheoremshowsthatconvexfunctionsonBanachspaceshavemonotonicoperatorsastheirderivatives. Asubset G {\displaystyleG} of X × X ∗ {\displaystyleX\timesX^{*}} issaidtobeamonotonesetifforeverypair [ u 1 , w 1 ] {\displaystyle[u_{1},w_{1}]} and [ u 2 , w 2 ] {\displaystyle[u_{2},w_{2}]} in G {\displaystyleG} , ( w 1 − w 2 , u 1 − u 2 ) ≥ 0. {\displaystyle(w_{1}-w_{2},u_{1}-u_{2})\geq0.} G {\displaystyleG} issaidtobemaximalmonotoneifitismaximalamongallmonotonesetsinthesenseofsetinclusion.Thegraphofamonotoneoperator G ( T ) {\displaystyleG(T)} isamonotoneset.Amonotoneoperatorissaidtobemaximalmonotoneifitsgraphisamaximalmonotoneset. Inordertheory[edit] Ordertheorydealswitharbitrarypartiallyorderedsetsandpreorderedsetsasageneralizationofrealnumbers.Theabovedefinitionofmonotonicityisrelevantinthesecasesaswell.However,theterms"increasing"and"decreasing"areavoided,sincetheirconventionalpictorialrepresentationdoesnotapplytoordersthatarenottotal.Furthermore,thestrictrelationsareoflittleuseinmanynon-totalordersandhencenoadditionalterminologyisintroducedforthem. Letting≤denotethepartialorderrelationofanypartiallyorderedset,amonotonefunction,alsocalledisotone,ororder-preserving,satisfiestheproperty x≤yimpliesf(x)≤f(y), forallxandyinitsdomain.Thecompositeoftwomonotonemappingsisalsomonotone. Thedualnotionisoftencalledantitone,anti-monotone,ororder-reversing.Hence,anantitonefunctionfsatisfiestheproperty x≤yimpliesf(y)≤f(x), forallxandyinitsdomain. Aconstantfunctionisbothmonotoneandantitone;conversely,iffisbothmonotoneandantitone,andifthedomainoffisalattice,thenfmustbeconstant. Monotonefunctionsarecentralinordertheory.Theyappearinmostarticlesonthesubjectandexamplesfromspecialapplicationsarefoundintheseplaces.Somenotablespecialmonotonefunctionsareorderembeddings(functionsforwhichx≤yifandonlyiff(x)≤f(y))andorderisomorphisms(surjectiveorderembeddings). Inthecontextofsearchalgorithms[edit] Inthecontextofsearchalgorithmsmonotonicity(alsocalledconsistency)isaconditionappliedtoheuristicfunctions.Aheuristich(n)ismonotonicif,foreverynodenandeverysuccessorn'ofngeneratedbyanyactiona,theestimatedcostofreachingthegoalfromnisnogreaterthanthestepcostofgettington'plustheestimatedcostofreachingthegoalfromn', h ( n ) ≤ c ( n , a , n ′ ) + h ( n ′ ) . {\displaystyleh(n)\leqc\left(n,a,n'\right)+h\left(n'\right).} Thisisaformoftriangleinequality,withn,n',andthegoalGnclosestton.Becauseeverymonotonicheuristicisalsoadmissible,monotonicityisastricterrequirementthanadmissibility.SomeheuristicalgorithmssuchasA*canbeprovenoptimalprovidedthattheheuristictheyuseismonotonic.[8] InBooleanfunctions[edit] Withthenonmonotonicfunction"ifathenbothbandc",falsenodesappearabovetruenodes. Hassediagramofthemonotonicfunction"atleasttwoofa,b,chold".Colorsindicatefunctionoutputvalues. InBooleanalgebra,amonotonicfunctionisonesuchthatforallaiandbiin{0,1},ifa1≤b1,a2≤b2,...,an≤bn(i.e.theCartesianproduct{0,1}nisorderedcoordinatewise),thenf(a1,...,an)≤f(b1,...,bn).Inotherwords,aBooleanfunctionismonotonicif,foreverycombinationofinputs,switchingoneoftheinputsfromfalsetotruecanonlycausetheoutputtoswitchfromfalsetotrueandnotfromtruetofalse.Graphically,thismeansthatann-aryBooleanfunctionismonotonicwhenitsrepresentationasann-cubelabelledwithtruthvalueshasnoupwardedgefromtruetofalse.(ThislabelledHassediagramisthedualofthefunction'slabelledVenndiagram,whichisthemorecommonrepresentationforn≤3.) ThemonotonicBooleanfunctionsarepreciselythosethatcanbedefinedbyanexpressioncombiningtheinputs(whichmayappearmorethanonce)usingonlytheoperatorsandandor(inparticularnotisforbidden).Forinstance"atleasttwoofa,b,chold"isamonotonicfunctionofa,b,c,sinceitcanbewrittenforinstanceas((aandb)or(aandc)or(bandc)). ThenumberofsuchfunctionsonnvariablesisknownastheDedekindnumberofn. Seealso[edit] Monotonecubicinterpolation Pseudo-monotoneoperator Spearman'srankcorrelationcoefficient-measureofmonotonicityinasetofdata Totalmonotonicity Cyclicalmonotonicity Operatormonotonefunction Notes[edit] ^Clapham,Christopher;Nicholson,James(2014).OxfordConciseDictionaryofMathematics(5th ed.).OxfordUniversityPress. ^abStover,Christopher."MonotonicFunction".WolframMathWorld.Retrieved2018-01-29. ^abcde"Monotonefunction".EncyclopediaofMathematics.Retrieved2018-01-29. ^abSpivak,Michael(1994).Calculus.1572WestGray,#377Houston,Texas77019:PublishorPerish,Inc.p. 192.ISBN 0-914098-89-6.{{citebook}}:CS1maint:location(link) ^SeethesectiononCardinalVersusOrdinalUtilityinSimon&Blume(1994). ^Varian,HalR.(2010).IntermediateMicroeconomics(8th ed.).W.W.Norton&Company.p. 56.ISBN 9780393934243. ^ifitsdomainhasmorethanoneelement ^Conditionsforoptimality:Admissibilityandconsistencypg.94-95(Russell&Norvig2010). Bibliography[edit] Bartle,RobertG.(1976).Theelementsofrealanalysis(second ed.). Grätzer,George(1971).Latticetheory:firstconceptsanddistributivelattices.ISBN 0-7167-0442-0. Pemberton,Malcolm;Rau,Nicholas(2001).Mathematicsforeconomists:anintroductorytextbook.ManchesterUniversityPress.ISBN 0-7190-3341-1. Renardy,Michael&Rogers,RobertC.(2004).Anintroductiontopartialdifferentialequations.TextsinAppliedMathematics13(Second ed.).NewYork:Springer-Verlag.p. 356.ISBN 0-387-00444-0. Riesz,Frigyes&BélaSzőkefalvi-Nagy(1990).FunctionalAnalysis.CourierDoverPublications.ISBN 978-0-486-66289-3. Russell,StuartJ.;Norvig,Peter(2010).ArtificialIntelligence:AModernApproach(3rd ed.).UpperSaddleRiver,NewJersey:PrenticeHall.ISBN 978-0-13-604259-4. Simon,CarlP.;Blume,Lawrence(April1994).MathematicsforEconomists(first ed.).ISBN 978-0-393-95733-4.(Definition9.31) Externallinks[edit] "Monotonefunction",EncyclopediaofMathematics,EMSPress,2001[1994] ConvergenceofaMonotonicSequencebyAnikDebnathandThomasRoxlo(TheHarkerSchool),WolframDemonstrationsProject. Weisstein,EricW."MonotonicFunction".MathWorld. Retrievedfrom"https://en.wikipedia.org/w/index.php?title=Monotonic_function&oldid=1086222622" Categories:FunctionalanalysisOrdertheoryRealanalysisTypesoffunctionsHiddencategories:CS1maint:locationArticleswithshortdescriptionShortdescriptionisdifferentfromWikidataAllarticleswithspecificallymarkedweasel-wordedphrasesArticleswithspecificallymarkedweasel-wordedphrasesfromMarch2021 Navigationmenu Personaltools NotloggedinTalkContributionsCreateaccountLogin Namespaces ArticleTalk English Views ReadEditViewhistory More Search Navigation MainpageContentsCurrenteventsRandomarticleAboutWikipediaContactusDonate Contribute HelpLearntoeditCommunityportalRecentchangesUploadfile Tools WhatlinkshereRelatedchangesUploadfileSpecialpagesPermanentlinkPageinformationCitethispageWikidataitem Print/export DownloadasPDFPrintableversion Languages العربيةAzərbaycancaБългарскиCatalàЧӑвашлаČeštinaDanskDeutschEestiΕλληνικάEspañolEsperantoفارسیFrançais한국어ՀայերենBahasaIndonesiaÍslenskaItalianoעבריתҚазақшаLombardNederlands日本語Oʻzbekcha/ўзбекчаPolskiPortuguêsRomânăРусскийSimpleEnglishSlovenčinaSlovenščinaСрпски/srpskiSrpskohrvatski/српскохрватскиSuomiSvenskaதமிழ்УкраїнськаTiếngViệt文言中文 Editlinks