functional relation



A binary relation from a set XX to a set YY is called functional if every element of XX is related to at most one element of YY. Notice that this is the same thing as a partial function, seen from a different point of view. A (total) function is precisely a relation that is both functional and entire.


Like any relation, a functional relation rr can be viewed as a span

Δ r ι r ϕ r X Y \array { & & \Delta_r \\ & \swarrow_{\iota_r} & & \searrow^{\phi_r} \\ X & & & & Y }

Such a span is a relation iff the pairing map from the domain Δ r\Delta_r to X×YX \times Y is an injection, and such a relation is functional iff the inclusion map ι r\iota_r is also an injection. Such a relation is entire iff the inclusion map ι r\iota_r is a surjection.

(Total) functions are precisely left adjoints in the bicategory of relations, in other words relations r:XYr: X \to Y in RelRel for which there exists s:YXs: Y \to X satisfying

rs1 Y;1 Xsr.r \circ s \leq 1_Y; \qquad 1_X \leq s \circ r.

For if a relation r:XYr: X \to Y is a function, then

  1. rr op1 Yr r^{op} \leq 1_Y: this just says that if r op(y,x)r^{op}(y, x) and r(x,y)r(x, y'), then y=yy = y'. Equivalently, if r(x,y)r(x, y) and r(x,y)r(x, y') then y=yy = y': this holds precisely because rr is functional or well-defined.

  2. 1 Xr opr1_X \leq r^{op} r: this says that if x=xx = x' in XX, then there exists yy in YY such that r(x,y)r(x, y) and r op(y,x)r^{op}(y, x'), i.e., there exists yy such that r(x,y)r(x, y) and r(x,y)r(x', y). This holds precisely because a function is an entire relation.

On the other hand, suppose r:XYr: X \to Y is a left adjoint.

  1. From 1 Xsr1_X \leq s r we deduce that if x=xx = x' in XX, then there exists yy in YY such that r(x,y)r(x, y) and s(y,x)s(y, x'); in particular rr is entire.

  2. Suppose r(x,y)r(x, y). From x=xx = x there exists yy' such that r(x,y)r(x, y') and s(y,x)s(y', x). Thus s(y,x)s(y', x) and r(x,y)r(x, y); from sr1 Ys r \leq 1_Y we infer y=yy' = y. We conclude at most one yy satisfies r(x,y)r(x, y), making rr functional.

Since rr is a function, it has a right adjoint rr, and by uniqueness of right adjoints, we may conclude s=r ops = r^{op}. The monad t=r oprt = r^{op} r has a unit 1 Xt1_X \leq t (tt is reflexive) and a multiplication tttt t \leq t (tt is transitive), and also t op=(r opr) op=r opr opop=r opr=tt^{op} = (r^{op} r)^{op} = r^{op} r^{op\; op} = r^{op} r = t (tt is symmetric). So the monad tt is an equivalence relation. The above reasoning may be internalized to apply to the bicategory of relations internal to a regular category, in which case this equivalence relation is exactly the kernel pair of the map rr. The comonad c=rr opc = r r^{op} has a counit c1 Yc \leq 1_Y (cc is coreflexive), and such coreflective relations in SetSet correspond to subsets of YY. More generally, in a regular category, the subobject of YY named by cc is the image of rr (the coequalizer of the kernel pair).

Further remarks: surjectivity of a function r:XYr: X \to Y can be expressed as the condition 1 Yrr op1_Y \leq r \circ r^{op}, and injectivity as r opr1 Xr^{op} \circ r \leq 1_X.


Revised on November 21, 2017 02:34:19 by Mike Shulman (