The Legendre-Fenchel transform from a category theoretic perspective SimonWillerton 5 1 Abstract 0 2 TheLegendre-Fencheltransformisaclassicalpieceofmathematicswith manyapplications. Inthispaperweshowhowitarisesinthecontextof n categorytheoryusingcategoriesenrichedovertheextendedrealnumbers a R:=[ ∞,+∞]. AkeyingredientisPavlovic’s“nucleusofaprofunctor” J − construction.Thepairingbetweenavectorspaceanditsdualcanbeviewed 5 asanR-profunctor; theconstructionofthenucleusofthisprofunctoris 1 theconstructionofalotofthetheoryoftheLegendre-Fencheltransform. ] Forarelationbetweensetsviewedasa true,false -valuedprofunctor,the T construction of the nucleus is the cons{truction o}f the Galois connection C associatedtotherelation. . Oneinsightgivenbythisapproachisthattherelevantstructureonthe h functionspacesinvolvedintheLegendre-Fencheltransformissomething t a like a metric but is asymmetric and can take negative values. This ‘R- m structure’isaconsiderablerefinementoftheusualpartialorderonreal- [ valuedfunctionspaceanditallowsanaturalinterpretationofToland-Singer duality and of the two tropical module structures on the set of convex 1 functions. v 1 9 Contents 7 3 0 1 Introduction 1 . 1 0 2 Categoriesenrichedoverposets 7 5 1 3 Thenucleusofaprofunctor 22 : v i 4 TheGaloiscorrespondencefromarelation 25 X r 5 TheLegendre-Fencheltransform 26 a 1 Introduction One role of category theory is as a kind of metamathematics: it gives a lan- guagefordescribinghowseeminglydifferentconstructionsindisparateparts ofmathematicsarereallythesame. Untilthe1970s,areassuchaslogic,algebra, algebraicgeometryandalgebraictopologyweretheareasinwhichcategory 1 theoryhadmostreach,butthenLawvere[10]showedusingenrichedcategory theorythatcategorytheorywasentwinedwithmetricspacetheory. FollowingLawvere[11]andtakingenrichedcategoriesseriously,wewill seeherehow,fromthepairingbetweenavectorspaceanditsdual,thenucleus ofaprofunctorconstruction[17]givesrisetoalargeamountofthetheoryaround theLegendre-Fencheltransformandconvexfunctions. Wewillalsoseehow theGaloiscorrespondencearisingfromarelationbetweensetsisanexampleof thisnucleusfromaprofunctorconstruction;otherexamplesofthisconstruction includetheIsbellcompletionofacategory,theDedekind-MacNeillecompletion for posets, the fuzzy concept lattice arising from a fuzzy context [2, 17], the tropicalspanofatropicalmatrix[5]andthedirectedtightspanforgeneralized metricspaces[23]. 1.1 Thebasicidea Here we will recall the construction of Galois connection from a relation — which is a fundamental construction across mathematics — and also recall theconstructionoftheLegendre-Fencheltransformandthenbrieflyexplain howtheyhaveacommonrefinedgeneralizationinthenucleusofaprofunctor construction. 1.1.1 RelationsandGaloisconnections. Suppose you have two sets G and M and a relation I between them. Two examplestobearinmindherearethefollowing: 1. fromalgebraicgeometry,G =Cn, M =C[x ,...x ]andxIpif p(x) =0; 1 n 2. from number theory, G is a field L equipped with a subfield K L, ⊂ M =Aut(L,K)thefieldautomorphismsfixingK,and(cid:96)Iϕif ϕ((cid:96)) = (cid:96). Wewrite (G)fortheposetofsubsetsofGorderedbysubsetinclusion. Simi- P larly,wewrite (M)op fortheposetofsubsetsof Mwiththeoppositeorder. P FromIwegetapairoforderpreservingfunctions I∗: (G)(cid:29) (M)op: I , P P ∗ where I∗(S)(cid:66) m M sImforalls S , { ∈ | ∈ } I (T)(cid:66) g G gItforallt T . ∗ { ∈ | ∈ } TheseformaGaloisconnectioninthat S I (T) I∗(S) T, ⊆ ∗ ⇐⇒ ⊇ asbothsidesaresayingthateveryelementofTisrelatedtoeveryelementofS. Wethengetaclosureoperationoneachpowerset: I I∗: (G) (G), I∗I : (M)op (M)op. ∗ P → P ∗ P → P Theseareidempotent—(I I )2 =I I and(I I )2 =I I —andtheysatisfy ∗ ∗ ∗ ∗ S I I∗(S)andT I∗I (∗T)forall∗S G,T ∗M,thust∗heymeritthename ⊂ ∗ ⊃ ∗ ⊂ ⊂ 2 closureoperations. Theclosedsubsetsarethosewhicharefixedbytheclosure operations,i.e.thosethatareequaltotheirclosure.Thetotalityofclosedsubsets givestwoposets (G)and (G). TheGaloisconnectionrestrictstoaGalois Pcl Pcl correspondence,i.e.aduality,betweentheclosedsubsetsofGandtheclosed subsetsof M: I∗: Pcl(G)(cid:27)Pcl(M)op: I∗. Wecanlookatwhatthisgivesintheexamplesmentionedabove. 1. Inthealgebraicgeometryexample,theclosedsubsetsofCn areprecisely thealgebraicsets(thatisthosedefinedbyasetofpolynomials)andthe closedsubsetsofC[x ,...,x ]arepreciselytheradicalideals. TheGalois 1 n correspondenceisthefundamentalcorrespondenceofalgebraicgeometry. 2. Inthenumbertheoryexample,providedtheextensionisGalois,theclosed subsetsofLaretheintermediatefieldsbetweenLandK,whiletheclosed subsetsofAut(L,K)arepreciselytheKrull-closedsubgroups. TheGalois correspondenceistheclassicalGaloiscorrespondence. 1.1.2 TheLegendre-Fencheltransform. SupposethatVisarealvectorspace,V#isitslineardualandFun(V,R)denotes thespaceoffunctionsfromV totheextendedrealnumbersR := [ ∞,+∞]. − Thereisastandardpairoftransformsbetweenfunctionspaces L∗: Fun(V,R)(cid:29)Fun(V#,R): L , ∗ givenby L∗(f)(k)(cid:66)sup(cid:8) k,x f(x)(cid:9), L (g)(x)(cid:66) sup(cid:8) k,x g(k)(cid:9). (cid:104) (cid:105)− ∗ (cid:104) (cid:105)− x V k V# ∈ ∈ ThetransformL istheLegendre-FencheltransformandwewillrefertoL ∗ asthereverseLegendre-Fencheltransform.1 Thefunctionspaceseachhavea∗ partialorderonthemusingthetotalorderonR,for f , f : V R, 1 2 → f (cid:60) f f (x)(cid:62) f (x) forallx V. 1 2 1 2 ⇐⇒ ∈ WeusetheoppositeorderforthefunctionsonV#. Withrespecttotheseorders thetwotransformsformaGaloisconnection,sowegetaclosureoperationon eachfunctionspace. L L∗: Fun(V,R) Fun(V,R); L∗L : Fun(V#,R) Fun(V#,R). ∗ → ∗ → Theseareidempotentand,forinstance,L L∗(f) (cid:60) f. Infact,L L∗(f)isthe ∗ ∗ pointwise-smallest,lowersemi-continuous,convexfunctionwhichdominates f;thelower-semicontinouspartisonlyrelevantwhenthefunctiontakesinfinite values. Now we can look at the functions fixed by these closure operators andthesearepreciselythelower-semicontinuousconvexfunctions. Fromthis it follows that the Lengendre-Fenchel transform and its reverse restrict to a 1InSection5below,IwillreverttothestandardnotationofwritingL∗(f)as f(cid:63)andsimilarly L (g)asg(cid:63). ∗ 3 bijection, actually a Galois correspondence: using Cvx to denote the lower semi-continuous,convexfunctionswehave L∗: Cvx(V,R)(cid:27)Cvx(V#,R) : L . ∗ ThisisknownasLegendre-Fenchelduality. Itcropsupinmanyareasofmathe- maticsforinstanceinmathematicalphysicstotranslatebetweenHamiltonian andLagrangianformalisms(see,e.g.,[1]),inoptimizationtheory(see,e.g.,[18]) andinlargedeviationtheory(see,e.g.,[22]). 1.1.3 Thegeneralconstruction Thetwoconstructionspresentedareclearlysimilar,theybothinvolveaGalois connection to construct a duality (or a Galois correspondence if you prefer). However,thesimilaritygoesmuchdeeperanditcanbeilluminatedinthelight ofenrichedcategorytheory,asbothoftheseconstructionsareexamplesofwhat, followingPavlovic[17],wewillcallthenucleusofaprofunctorconstruction; ShenandZhang[19]alsoconsideredtheconstruction. Thetermsusedinthe followingparagraphwillbeexplainedinSection2. Fortheconstructionyoustartwithaprofunctorbetweentwosetsorenriched categories,inthefirstcasethisistherelationbetweenGand M,thoughtofa functionG M true,false ,andinthesecondcasethisisthetautological × → { } pairing V V# R R between the vector space and its dual. You then × → ⊂ considerthecategoriesofpresheavesonyouroriginalcategories,inthefirst casethisleadstotheposetsofsubsetsof G and M andinthesecondcaseto the spaces of functions on V and V#. From the profunctor you construct an enrichedadjunctionbetweenthepresheafcategories. Intheonecaseyouget the Galois connection between the sets of subsets, in the other case you get theLegendre-Fencheltransformanditsreverse. Thenucleusisthenextracted asthepartsofthepresheafcategoriesonwhichtheadjunctionrestrictstoan equivalence. In the one case you get the Galois correspondence, and often aninterestingduality,intheothercaseyougettheLegendre-Fenchelduality betweenconvexfunctions. Herethesetofclassicaltruthvalues true,false andthesetofextendedreal { } numbersRbothformexamplesofwhatacategorytheoristmightcallacomplete andcocomplete, closedmonoidalposet; otherfolkmightcallsuchathinga commutativequantaleoracomplete,commutative,idempotentsemiring. In thispaperwepresentthetheoryofcategoriesandprofunctorsenrichedover suchthingspayingparticularattentiontothesetwomainexamples. 1.2 Whatwegain Afairquestiontoaskatthispointis“WhatdowegainfromviewingLegendre- Fenchel duality as a profunctor nucleus?” It could be a case of translating somethingfamiliartoanunfamiliarlanguagefornorealgain. Infact,wegain a few things. On the one hand we see that from a category theory point of view,theLegendre-Fencheltransformisinevitableonceyouhavethepairing betweenavectorspaceanditsdual. Youcanseehowmuchofthetheoryisjust formalnonsenseandhowmuchisspecifictothecaseinhand.Astheprofunctor nucleusarisesinvariousplaces,suchasintightspansformetricspaces,thereis thepotentialforbuildingbridgesbetweendifferentdisciplines. 4 Ontheotherhand,onamoreconcretelevel,afundamentalinsightthatwe gainisthatthesetoffunctionsFun(V,R)shouldbeconsiderednotasaposet butasanR-space,somethinglikeanasymmetricmetricspacewithpossibly negative distances. There is an R-metric, like a very generalized notion of distance,d: Fun(V,R) Fun(V,R) Rgivenby × → d(f , f )(cid:66)sup f (x) f (x) , 1 2 2 1 { − } x V ∈ wheresomecareisneededtounderstandthedifferencebetweeninfinitequan- tities, for example ( ∞) ( ∞) = ∞ and (+∞) (+∞) = ∞, see Sec- − − − − − − tion2.2.2fordetails. Thissatisfiesthetriangleinequalityandd(f, f) = 0if f takesafinitevaluesomewhere, otherwised(f, f) = ∞. However, itisnot − symmetric. UnderlyinganysuchR-metricisapreorder(cid:60),definedasfollows: f (cid:60) f 0(cid:62)d(f , f ). 1 2 1 2 ⇐⇒ Unpacking the definition this gives the usual partial order on the space of functionsdescribedabove. SothisR-metriconFun(V,R)isarefinementofthe usualpartialorder. With respect to this R-metric, we find (Theorem 3) that the Legendre- Fenchel transform is a distance non-increasing function so that d(f , f ) (cid:62) 1 2 d(L∗(f1),L∗(f2)),inotherwords, sup f2(x) f1(x) (cid:62) sup L∗(f1)(k) L∗(f2)(k) . { − } { − } x V k V# ∈ ∈ We also learn (Theorem 2) that the Legendre-Fenchel transform and its re- verseformanadjunctionwhichmeansthatd(L∗(f),g) =d(f,L (g)),inother ∗ words, sup L∗(f)(k) g(k) =sup L (g)(x) f(x) . { − } { ∗ − } k V# x V ∈ ∈ ThisisarefinementofthestatementthattheLegendre-Fencheltransformand itsreverseformaGaloisconnection,i.e.that f (cid:60)L (g)ifandonlyifg(cid:60)L∗(f). ∗ Inthecasethatitisrestrictedtoconvexfunctionsthenwefind(Theorem5) that the Legendre-Fenchel transform is actually a distance preserving map, meaningd(L∗(f1),L∗(f2)) =d(f1, f2),inotherwords, sup L∗(f1)(k) L∗(f2)(k) =sup f2(x) f1(x) . { − } { − } k V# x V ∈ ∈ ThisisnotpartofthestandardtreatmentoftheLegendre-Fencheltransform, butitisknownasToland-Singerduality. Itisarefinementofthestandardorder theoreticstatementthatforconvexfunctions f and f wehave f (cid:60) f 1 2 1 2 L∗(f2)(cid:60)L∗(f1). ThefactthatitisstrongerthanthatisillustratedinFigur⇐e1⇒. InthefirstpictureofFigure1weseetwoconvexfunctions f , f : R R. 1 2 → Neither function dominates the other so the fact that the Legendre-Fenchel transform is order reversing tells us nothing about the transforms of these functions. We see, however, that d(f , f ) = 1 and d(f , f ) = 3, so Toland- 1 2 2 1 Singer duality tells us that d(L∗(f1),L∗(f2)) = 1 and d(L∗(f2),L∗(f1)) = 3 whichweclearlyseeinthesecondpicture. Thedistanceonthefirstpictureis 5 3 f1 3 L∗(f2) 2 2 1 1 f2 x L∗(f1) k -1 1 2 3 1 1 − 1 -1 − Figure1: IllustratingToland-Singerduality. NoteL∗(f1)(k) =L∗(f2)(k) = +∞ when k >1. | | themaximumclimbbetweengraphsandthedistanceonthesecondpictureis themaximumfall. The nucleus of a profunctor is complete and cocomplete in a categorical sense. Whatthatmeanshereinparticularisthatthespaceofconvexfunctions hasproducts,coproducts,tensorsandcotensors(Theorem7). Theproductoftwoconvexfunctionsisjusttheirpointwisemaximum: f f (x)(cid:66)max(f (x), f (x)). 1 2 1 2 (cid:117) The coproduct is the lower semi-continuous, convex hull of their pointwise minimum: f1 f2 (cid:66)L L∗(min(f1, f2)). (cid:116) ∗ Intheordertheoreticworldthesearetheleastupperboundandgreatestlower boundsofthefunctions,butinthismetricworldtheysatisfystrongerproperties, namely d(f, f f ) =max(d(f, f ),d(f, f )) 1 2 1 2 (cid:117) d(f f , f) =max(d(f , f),d(f , f)) 1 2 1 2 (cid:116) The tensor product and cotensor product (cid:116) are actions of the monoid (cid:12) (R,+)onthesetofconvexfunctions: fora R, f Cvx(V,R)andx V, ∈ ∈ ∈ (a(cid:116) f)(x) = f(x) a; (a f)(x) = f(x)+a. − (cid:12) Theproduct andcotensor(cid:116)makethesetofconvexfunctions f Cvx(V,R) (cid:117) ∈ intoamoduleoverthetropicalsemiring(R,min,+),thatisRwithminimum asadditionandusualadditionasmultiplication. Similarly,thecoproduct and (cid:116) tensor makethesetofconvexfunctionsCvx(V,R)intoamoduleoverthe (cid:12) tropicalsemiring(R,min,+)inadifferentway. 1.3 Synopsis ThebulkofthepaperisSection2inwhichwegothroughalotofessentiallystan- dardcategorytheoreticnotionssuchaspresheaves,adjunctions,profunctors, 6 completenessandcocompleteness,butwedothisinthenon-standardcontext ofcategoriesenrichedovertheextendedrealnumbersR; thisisintendedto besuitableforthoseinterestedintheLegendre-Fencheltransformwithlittle background in category theory. The nucleus of a profunctor is described in Section 3 by analogy with constructing a pair of adjoint linear maps from a matrix. InSection4weseehowtheusualtheoryofGaloisconnectionsfrom relations arises by considering the case of categories enriched over classical truthvalues. Thepay-offcomesinSection5inwhichtheprecedingtheoryis puttogetherforR-categoriesandalotofthetheoryoftheLegendre-Fenchel transformdropout,suchasToland-Singerdualityandthetwotropicalmodule structuresonthesetofconvexfunctions. 1.4 Furtherquestions Thereareseveralquestionsthatthisworknaturallyleadsto: herearetwoof them. What happens if we work over Z = Z ∞,+∞ ? Discrete convex • ∪{− } analysisseemstobemoresubtle(see[16]and[6])anditwouldbeworth seeingifthisapproachleadstoanythinginteresting. Fenchel Duality (see Theorem 31.1 of [18]) involves both convex and • concavefunctions;isitpossibletoformulatethisincategoricaltermsand doesitgeneralizetoothersituations? 1.5 Acknowledgements IwouldliketothankTomLeinster,MarkKambites,MarianneJohnson,Hiroshi Hirai,SoichiroFujiiandBruceBartlettforusefulcommentsandconversations. I would also like to thank contributors to the n-Category Cafe´ where earlier piecesofthisworkwasposted. 2 Categories enriched over posets Inthissectionthetheoryofcategoriesenrichedovermonoidalposetsispre- sented with particular emphasis placed on enriching over the posets R and Truth. Theintentionisthatthisshouldbeaccessibletoareaderwithaninterest intheLegendre-Fencheltransformbutwithnotmuchbackgroundincategory theory. 2.1 Quantales,thincategoriesandidempotentsemirings Inthispaperweconsidercategoriesenrichedovermonoidalposets. Thestruc- tureofamonoidalposetcropsupindifferentareaswithdifferentnamesand differentfeaturesemphasised,soitisworthexplainingherehowtheseconnect. Ourmainexamples—theextendedrealnumbersRwiththeorder(cid:62)andthe setofclassicaltruthvaluesTruthwithentailmentastheorder—aregivenafter thedefinitions. 7 2.1.1 Commutativequantales In concise terms, a commutative quantale is a complete lattice which has a commutative, unital, associative, binary operation which distributes over arbitraryjoins. Unpackingthisdefinition,wehave⊗aposet2 (Q,(cid:88))suchthat (cid:86) (cid:87) everysubsetofW Qhasbothameet xandajoin x;inparticular, thesesatisfy,foral⊂lw W, x∈W x∈W ∈ (cid:86) x(cid:88)w and w(cid:88)(cid:87) x. x W x W ∈ ∈ When(cid:88)is(cid:54)thenthemeet(cid:86)istheinfimum,andwhenitis(cid:62)thenthemeet(cid:86) isthesupremum. Thisposetisequippedwithamonoidstructure : Q Q Qwithunit ⊗ × → 1 Qandwhichsatisfiesdistributivityoverjoins: ∈ q (cid:87) x = (cid:87) (q x). ⊗ x∈W x∈W ⊗ Fromthisdatawecandefinearesiduationmap[ , ]: Q Q Qby − − × → [b,c](cid:66)(cid:87)a:a b(cid:88)ca. ⊗ Thiswillsatisfytheadjunctionproperty a b(cid:88)c a(cid:88)[b,c]. ⊗ ⇐⇒ 2.1.2 Idempotentsemirings Acommutativeidempotentsemiringisacommutativesemiringinwhichthe additionisidempotent.Firstly,acommutativesemiring,basicallyaringwithout negatives,consistsoftwocommutativemonoidstructures(S, ,0)and(S, ,1) ⊕ ⊗ onthesamesetSsuchthat distributesover . Theadditionisidempotentif ⊗ ⊕ s s = s foralls S. ⊕ ∈ ThisallowsustodefineapartialorderonSby a (cid:88) bifandonlyif a b = b. (cid:87) ⊕ Then becomesthejoin ,and distributesoverit. Byinductionthismeans ⊕ ⊗ thatwehavejoinsforarbitraryfinitesubsets,andthatmultiplicationdistributes overthesefinitejoins. WesaythatSiscompleteifarbitrarysubsetshavejoins andmultiplicationdistributesoverarbitraryjoins. Arbitrarymeetscanthenbe definedintermsofthejoins: forasubsetW S defineW(cid:48) := y S y (cid:88) xforallx W then(cid:86) x = (cid:87) y. Again⊂theresiduationca{nb∈ede|fined by ∈ } x∈W y∈W(cid:48) [b,c](cid:66) (cid:77) a. a:a b(cid:88)c ⊗ Onecanseeinthismannerthatacomplete,commutative,idempotentsemiring isthesamethingasacommutativequantale. 2Iamassiduouslynotpreferringeither(cid:54)or(cid:62)asmyrelation.Here(cid:88)canbepronouncedas‘is relatedto’. 8 2.1.3 Monoidalthincategories Athincategoryisacategoryinwhichthereisatmostonemorphismbetween eachpairofobjects. Workinginathincategoryismuchsimplerthanworking inanarbitrarycategoryas,forinstance,alldiagramscommute. Havingathin categoryisthesameashavingatransitive,reflexiverelationontheobjectsof thecategory,thecorrespondenceisdefinedvia a(cid:88)b thereisamorphisma b. ⇐⇒ → This is not quite the same thing as having a partial order, however, as anti- symmetrymightfail: wecouldhavedistinctobjectsaandbwhichhavearrows a b and b a. Such a relation is called a preorder. The condition that a → → thincategoryactuallycorrespondstoapartialorderispreciselytheskeletal conditionwhichisthatallisomorphismsareequalities. Wecanturnanythin categoryintoaskeletalcategorybytakingisomorphismclassesofobjects. Amonoidalcategoryisacategory withafunctor : together C ⊗ C×C → C with some associativity and unitality constraints. In the case of a skeletal, thin category the constraints are just that the product should be associative and unital on the set of objects. The monoidal structure is symmetric if this productiscommutative. Themonoidalstructureisclosedifthereisafunctor [ , ]: op whichisadjointto inthesensethat − − V ×V → V ⊗ thereisamorphisma b c thereisamorphisma [b,c]. ⊗ → ⇐⇒ → Asyoushouldbeabletotell,thisisthesameastheconditionontheresiduation foraquantale. Therearenotionsofcategoricalproductsandcoproducts,for thin categories these amount to precisely meets and joins for the associated preorders. Asthemonoidalproducthasarightadjointitwillautomatically distributeoverjoins. Beingcompleteandcocompleteinthecategoricalsense amounts,forathincategory,tohavingarbitraryproductsandcoproducts. Fromthisconcisediscussionitishopefullyclearthatacompleteandcocom- plete,skeletal,closed,symmetricmonoidalthincategoryisthesamethingasa commutativequantale. 2.2 Ourmainexamples Themainexamplesoftheabovestructuresthatweareinterestedinhereare truth values and extended real numbers. We will get to Galois connections usingthefirstandtheLegendre-Fencheltransformusingthesecond. 2.2.1 Truth WetakeTruthtobethecategorywithtwoobjectstrueandfalseandasingle non-identityarrowfalse true. Themonoidalproductistakentobe‘logical → and’&,andtheresiduationisimplication,so[a,b] = (a b). Theorderonthe ⇒ set true,false canbeinterpretedas‘entailment’ ,sotheonlynon-reflexive { } (cid:96) relationshipisfalse true. Themeetisthesameastheproduct,namelylogical (cid:96) and,butisoftenthoughtofas‘forall’. Thejoinis‘logicalor’,oftenthoughtof as‘thereexists’. 9 2.2.2 R Todefinethestructureontheextendedrealnumbers,westartwithRequipped with the order (cid:62), so that meet (cid:86) is supremum and join (cid:87) is infimum, this hasusualadditionasthemonoidalproductandsubtractionastheresiduation because a+b(cid:62)c a(cid:62)c b. ⇐⇒ − We make this structure complete by adding a maximum element +∞ and a minimumelement ∞todefineR. Thentherequirementthat+distributes − overinfimaensuresthatthereisauniqueextensionof+toR. Finallywecan usetheformulaforresiduationtoextendsubtractiontoR: c b = inf a. − a+b(cid:62)c ThearithmeticissummarizedinthefollowingtablesliftedfromtheBachelor’s ThesisofFujii[6]. y y x+y ∞ t +∞ y x ∞ t +∞ − − − ∞ ∞ ∞ +∞ ∞ ∞ +∞ +∞ x −s −∞ s−+t +∞ x −s −∞ t s +∞ +∞ −+∞ +∞ +∞ +∞ −∞ −∞ ∞ − − − Itisimportanttoobservethatthereareafewsubtletiesinthesedefinitions,so theydon’tbehavequitehowyoumightnaivelyexpect.Forinstance,subtracting +∞isnotthesameasadding ∞: − (+∞)+( ∞) = (+∞); (+∞) (+∞) = ( ∞). − − − Asimilarstructure,butwiththeoppositeorderwasconsideredbyLawvere in[12];thisstructurewasconsideredfromtheidempotentsemiringperspective in[4]. Whilstthisarithmeticoftheinfinitemightseemalittlestrange,itisthe appropriatestructurefortheLegendre-Fencheltransform. As an idempotent semiring, R has + as its multiplication and min as its addition. 2.3 EnrichedstructuresforTruthandR Wewillgothroughalotofthetheoryofcategoriesenrichedoverourtwomain examples. Thestandardreferencesformuchofthegeneraltheoryofenriched categoriesare[8]and[3]. 2.3.1 Categories Recallthatanordinarysmallcategory canbedefinedtoconsistofasetof C objectsob( )suchthat C foreveryc,c(cid:48) thereisaset (c,c(cid:48)) ob(Set)calledthehom-set; • ∈ C C ∈ foreveryc,c(cid:48),c(cid:48)(cid:48) thereisafunction (c,c(cid:48)) (c(cid:48),c(cid:48)(cid:48)) (c,c(cid:48)(cid:48)),this • ∈ C C ×C → C iscalledcomposition; 10