Residuated mapping

<h2 id="definition">Definition</h2>
If A, B are posets, a function f: A → B is residuated if and only if the preimage under f of every principal down-set of B is a principal down-set of A.

<h2 id="consequences">Consequences</h2>
If B is a poset, the set of functions A → B can be ordered by the <a href="/facts/Pointwise_order/dt4Mrs6w">pointwise order</a> f ≤ g ↔ (∀x ∈ A) f(x) ≤ g(x).
It can be shown that a monotone function f is residuated if and only if there exists a (necessarily unique) monotone function f +: B → A such that f o f + ≤ idB and f + o f ≥ idA, where id is the <a href="/facts/Identity_function/9AtsP0LC">identity function</a>. The function f + is the residual of f. A residuated function and its residual form a <a href="/facts/Galois_connection/lwuFXX2d">Galois connection</a> under the (more recent) monotone definition of that concept, and for every (monotone) Galois connection the lower adjoint is residuated with the residual being the upper adjoint.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> Therefore, the notions of monotone Galois connection and residuated mapping essentially coincide.
Additionally, we have f -1(↓{b}) = ↓{f +(b)}. 
If B° denotes the <a href="/facts/Duality_(order_theory)/TTTcqYQy">dual order</a> (opposite poset) to B then f : A → B is a residuated mapping if and only if there exists an f * such that f : A → B° and f *: B° → A form a <a href="/facts/Galois_connection/lwuFXX2d">Galois connection</a> under the original <a href="/facts/Antitone/MjQK0YL2">antitone</a> definition of this notion.
If f : A → B and g : B → C are residuated mappings, then so is the <a href="/facts/Function_composition/r5Pvnmth">function composition</a> gf : A → C, with residual (gf) + = f +g +. The antitone Galois connections do not share this property.
The set of monotone transformations (functions) over a poset is an <a href="/facts/Ordered_monoid/AeNaNxPo">ordered monoid</a> with the pointwise order, and so is the set of residuated transformations.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>

<h2 id="examples">Examples</h2>
<ul><li>The <a href="/facts/Ceiling_function/ssehyMMf">ceiling function</a> 
 
 
 
 x
 ↦
 ⌈
 x
 ⌉
 
 
 {\displaystyle x\mapsto \lceil x\rceil }
 
 from R to Z (with the usual order in each case) is residuated, with residual mapping the natural embedding of Z into R.</li>
<li>The embedding of Z into R is also residuated. Its residual is the <a href="/facts/Floor_function/ssehyMMf">floor function</a> 
 
 
 
 x
 ↦
 ⌊
 x
 ⌋
 
 
 {\displaystyle x\mapsto \lfloor x\rfloor }
 
.</li></ul>
<h2 id="residuated-binary-operators">Residuated binary operators</h2>
If • : P × Q → R is a binary map and P, Q, and R are posets, then one may define residuation component-wise for the left and right translations, i.e. multiplication by a fixed element. For an element x in P define xλ(y) = x • y, and for x in Q define λx(y) = y • x. Then • is said to be residuated if and only if xλ and λx are residuated for all x (in P and respectively Q). Left (and respectively right) division are defined by taking the residuals of the left (and respectively right) translations: x\y = (xλ)+(y) and x/y = (λx)+(y)
For example, every <a href="/facts/Ordered_group/xoLNpEqH">ordered group</a> is residuated, and the division defined by the above coincides with notion of <a href="/facts/Group_(mathematics)/IQTYqINt">division in a group</a>. A less trivial example is the set Matn(B) of <a href="/facts/Square_matrices/5TP9mNNn">square matrices</a> over a <a href="/facts/Boolean_algebra_(structure)/cHbo65jm">boolean algebra</a> B, where the matrices are ordered <a href="/facts/Pointwise/dt4Mrs6w">pointwise</a>. The pointwise order endows Matn(B) with pointwise meets, joins and complements. <a href="/facts/Matrix_multiplication/lYDB6Ro2">Matrix multiplication</a> is defined in the usual manner with the "product" being a meet, and the "sum" a join. It can be shown<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> that X\Y = (Y tX ′)′ and X/Y = (X ′Y t)′, where X ′ is the complement of X, and Y t is the <a href="/facts/Transposed_matrix/8wmsagGS">transposed matrix</a>).

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Residuated_lattice/p84UdNQ3">Residuated lattice</a></li></ul>
<h2 id="notes">Notes</h2>

<ul><li>J.C. Derderian, "Galois connections and pair algebras", Canadian J. Math. 21 (1969) 498-501.</li>
<li>Jonathan S. Golan, Semirings and Affine Equations Over Them: Theory and Applications, <a href="/facts/Springer-Verlag/nAesf6nT">Kluwer Academic</a>, 2003, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 1-4020-1358-2. Page 49.</li>
<li>T.S. Blyth, "Residuated mappings", <a href="/facts/Order_(journal)/7kF1kG7K">Order</a> 1 (1984) 187-204.</li>
<li>T.S. Blyth, Lattices and Ordered Algebraic Structures, Springer, 2005, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 1-85233-905-5. Page 7.</li>
<li>T.S. Blyth, M. F. Janowitz, Residuation Theory, <a href="/facts/Pergamon_Press/qe6ctSTB">Pergamon Press</a>, 1972, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-08-016408-0. Page 9.</li>
<li>M. Erné, J. Koslowski, A. Melton, G. E. Strecker, A primer on Galois connections, in: Proceedings of the 1991 Summer Conference on General Topology and Applications in Honor of <a href="/facts/Mary_Ellen_Rudin/cYFs5kXH">Mary Ellen Rudin</a> and Her Work, Annals of the New York Academy of Sciences, Vol. 704, 1993, pp. 103–125. Available online in various file formats: <a href="https://web.archive.org/web/20060108063506/http://www.iti.cs.tu-bs.de/TI-INFO/koslowj/RESEARCH/gal_bw.ps.gz">PS.GZ</a> <a href="http://www.math.ksu.edu/~strecker/primer.ps">PS</a></li>
<li>Klaus Denecke, Marcel Erné, Shelly L. Wismath, Galois connections and applications, Springer, 2004, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 1402018975</li>
<li>Galatos, Nikolaos, Peter Jipsen, Tomasz Kowalski, and Hiroakira Ono (2007), Residuated Lattices. An Algebraic Glimpse at Substructural Logics, Elsevier, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-444-52141-5.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Denecke, p. 95; Galatos, p. 148 <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Erné, Proposition 4 <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Blyth, 2005, p. 193 <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Blyth, p. 198 <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
</ol>

Residuated mapping open-in-new

Residuated mapping