residuated


Let P,Q be two posets. Recall that a function f:PQ is order preserving iff xy implies f(x)f(y). This is equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath to saying that the preimageMathworldPlanetmath of any down set under f is a down set.

Definition A function f:PQ 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 yQ, there is some xP such that

f-1(y)=x,

where f-1(A) for any AQ is the set {aXf(a)A}, and b={ccb}.

Let us make some observations on a residuated function f:PQ:

  1. 1.

    f is order preserving.

    Proof.

    Suppose ab in P. Then there is some cP such that c=f-1(f(b)). Since f(b)f(b), bc, or bc, which means ac, or ac. But this implies af-1(f(b)), so that f(a)f(b), or f(a)f(b). ∎

  2. 2.

    The x in the definition above is unique.

    Proof.

    If x=z, then xz, or xz. Similarly, zx, so that x=z. ∎

  3. 3.

    g:QP given by g(y)=x is a well-defined function, with the following properties:

    1. (a)

      g is order preserving,

    2. (b)

      1Pgf,

    3. (c)

      fg1Q.

    Proof.

    g is order preserving: if rs in Q, then rs, so that u=f-1(r)f-1(s)=v, where u=g(r) and v=g(s). But uv implies uv, or g(r)g(s).

    1Pgf: let xP, y=f(x), and z=g(y). Then xf-1(y)f-1(y)=z, which implies xz=g(f(x)) as desired.

    fg1Q: pick yQ and let x=g(y). Then f-1(y)=x, so that f(x)f(x)=f(f-1(y))=y, or f(x)y, or f(g(y))=f(x)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 yQ, and let x=g(y). We want to show that x=f-1(y). First, suppose af-1(y). Then f(a)y, which means g(f(a))g(y)=x. But then ag(f(a)), and we get ax, or ax. Next, suppose ax=g(y). Then f(a)f(x)=f(g(y))y, so af-1(f(a))f-1(y).

To see uniqueness, suppose h:QP is order preserving such that 1Phf and fh1Q. Then g=1Pg(hf)g=h(fg)=h1Q=h and h=1Ph(gf)h=g(fh)g1Q=g. ∎

Definition. Given a residuated function f:PQ, the unique function g:QP defined above is called the residual of f, and is denoted by f+.

For example, given any function f:AB, the induced function f:P(A)P(B) (by abuse of notation, we use the same notation as original function f), given by f(S)={f(a)aS} is residuated. Its residual is the function f-1:P(B)P(A), given by f-1(T)={aAf(a)T}.

Here are some properties of residuated functions and their residuals:

  • A bijectiveMathworldPlanetmathPlanetmath residuated function is an order isomorphism, and conversely. Furthermore, the residual is residuated, and is its inversePlanetmathPlanetmathPlanetmath.

  • If f:PQ is residuated, then ff+f=f and f+ff+=f+.

  • If f:PQ and g:QR are residuated, so is gf and (gf)+=f+g+.

  • If f:PQ is residuated, then f+f:PP is a closure map on P. Conversely, any closure function can be decomposed as the functionalPlanetmathPlanetmathPlanetmathPlanetmath compositionMathworldPlanetmath of a residuated function and its residual.

Remark. Residuated functions and their residuals are closely related to Galois connections. If f:PQ 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:PQ is residuated, and g:QP 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
Canonical name Residuated
Date of creation 2013-03-22 18:53:22
Last modified on 2013-03-22 18:53:22
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 12
Author CWoo (3771)
Entry type Definition
Classification msc 06A99
Classification msc 06A15
Defines residual