You are here
Homeresiduated
Primary tabs
residuated
Let $P,Q$ be two posets. Recall that a function $f:P\to Q$ is order preserving iff $x\leq y$ implies $f(x)\leq f(y)$. This is equivalent to saying that the preimage of any down set under $f$ is a down set.
Definition A function $f:P\to Q$ between ordered sets $P,Q$ is said to be residuated if the preimage of any principal down set is a principal down set. In other words, for any $y\in Q$, there is some $x\in P$ such that
$f^{{1}}(\downarrow\!\!{y})=\downarrow\!\!{x},$ 
where $f^{{1}}(A)$ for any $A\subseteq Q$ is the set $\{a\in X\mid f(a)\in A\}$, and $\downarrow\!\!b=\{c\mid c\leq b\}$.
Let us make some observations on a residuated function $f:P\to Q$:
1. $f$ is order preserving.
Proof.
Suppose $a\leq b$ in $P$. Then there is some $c\in P$ such that $\downarrow\!\!c=f^{{1}}(\downarrow\!\!f(b))$. Since $f(b)\in\downarrow\!\!f(b)$, $b\in\downarrow\!\!c$, or $b\leq c$, which means $a\leq c$, or $a\in\downarrow\!\!c$. But this implies $a\in f^{{1}}(\downarrow\!\!f(b))$, so that $f(a)\in\downarrow\!\!f(b)$, or $f(a)\leq f(b)$. ∎
2. The $x$ in the definition above is unique.
Proof.
If $\downarrow\!\!x=\downarrow\!\!z$, then $x\in\downarrow\!\!z$, or $x\leq z$. Similarly, $z\leq x$, so that $x=z$. ∎
3. $g:Q\to P$ given by $g(y)=x$ is a welldefined function, with the following properties:
(a) $g$ is order preserving,
(b) $1_{P}\leq g\circ f$,
(c) $f\circ g\leq 1_{Q}$.
Proof.
$g$ is order preserving: if $r\leq s$ in $Q$, then $\downarrow\!\!r\subseteq\downarrow\!\!s$, so that $\downarrow\!\!u=f^{{1}}(\downarrow\!\!r)\subseteq f^{{1}}(\downarrow\!\!s)=% \downarrow\!\!v$, where $u=g(r)$ and $v=g(s)$. But $\downarrow\!\!u\subseteq\downarrow\!\!v$ implies $u\leq v$, or $g(r)\leq g(s)$.
$1_{P}\leq g\circ f$: let $x\in P$, $y=f(x)$, and $z=g(y)$. Then $x\in f^{{1}}(y)\subseteq f^{{1}}(\downarrow\!\!y)=\downarrow\!\!z$, which implies $x\leq z=g(f(x))$ as desired.
$f\circ g\leq 1_{Q}$: pick $y\in Q$ and let $x=g(y)$. Then $f^{{1}}(\downarrow\!\!y)=\downarrow\!\!x$, so that $f(x)\in f(\downarrow\!\!x)=f(f^{{1}}(\downarrow\!\!y))=\downarrow\!\!y$, or $f(x)\leq y$, or $f(g(y))=f(x)\leq y$ as a result. ∎
Actually, the third observation above characterizes $f$ being residuated:
Proposition 1.
If $f$ is order preserving, and $g$ satisfies $3(a)$ through $3(c)$, then $f$ is residuated. In fact, such a $g$ is unique.
Proof.
Suppose $y\in Q$, and let $x=g(y)$. We want to show that $\downarrow\!\!x=f^{{1}}(\downarrow\!\!y)$. First, suppose $a\in f^{{1}}(\downarrow\!\!y)$. Then $f(a)\leq y$, which means $g(f(a))\leq g(y)=x$. But then $a\leq g(f(a))$, and we get $a\leq x$, or $a\in\downarrow\!\!x$. Next, suppose $a\leq x=g(y)$. Then $f(a)\leq f(x)=f(g(y))\leq y$, so $a\in f^{{1}}(f(a))\subseteq f^{{1}}(\downarrow\!\!y)$.
To see uniqueness, suppose $h:Q\to P$ is order preserving such that $1_{P}\leq h\circ f$ and $f\circ h\leq 1_{Q}$. Then $g=1_{P}\circ g\leq(h\circ f)\circ g=h\circ(f\circ g)\leq=h\circ 1_{Q}=h$ and $h=1_{P}\circ h\leq(g\circ f)\circ h=g\circ(f\circ h)\leq g\circ 1_{Q}=g$. ∎
Definition. Given a residuated function $f:P\to Q$, the unique function $g:Q\to P$ defined above is called the residual of $f$, and is denoted by $f^{+}$.
For example, given any function $f:A\to B$, the induced function $f:P(A)\to P(B)$ (by abuse of notation, we use the same notation as original function $f$), given by $f(S)=\{f(a)\mid a\in S\}$ is residuated. Its residual is the function $f^{{1}}:P(B)\to P(A)$, given by $f^{{1}}(T)=\{a\in A\mid f(a)\in T\}$.
Here are some properties of residuated functions and their residuals:

A bijective residuated function is an order isomorphism, and conversely. Furthermore, the residual is residuated, and is its inverse.

If $f:P\to Q$ is residuated, then $f\circ f^{+}\circ f=f$ and $f^{+}\circ f\circ f^{+}=f^{+}$.

If $f:P\to Q$ and $g:Q\to R$ are residuated, so is $g\circ f$ and $(g\circ f)^{+}=f^{+}\circ g^{+}$.

If $f:P\to Q$ is residuated, then $f^{+}\circ f:P\to P$ is a closure map on $P$. Conversely, any closure function can be decomposed as the functional composition of a residuated function and its residual.
Remark. Residuated functions and their residuals are closely related to Galois connections. If $f:P\to Q$ is residuated, then $(f,f^{+})$ forms a Galois connection between $P$ and $Q$. On the other hand, if $(f,g)$ is a Galois connection between $P$ and $Q$, then $f:P\to Q$ is residuated, and $g:Q\to P$ is $f^{+}$. Note that PM defines a Galois connection as a pair of orderpreserving maps, where as in Blyth, they are order reversing.
References
 1 T.S. Blyth, Lattices and Ordered Algebraic Structures, Springer, New York (2005).
 2 G. Grätzer, General Lattice Theory, 2nd Edition, Birkhäuser (1998)
Mathematics Subject Classification
06A99 no label found06A15 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections