# 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. 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. 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. 3.

$g:Q\to P$ given by $g(y)=x$ is a well-defined function, with the following properties:

1. (a)

$g$ is order preserving,

2. (b)

$1_{P}\leq g\circ f$,

3. (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 order-preserving maps, where as in Blyth, they are order reversing.

## References

Title residuated Residuated 2013-03-22 18:53:22 2013-03-22 18:53:22 CWoo (3771) CWoo (3771) 12 CWoo (3771) Definition msc 06A99 msc 06A15 residual