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 can be characterized as the 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 Xsrr \circ s \leq 1_Y; \qquad 1_X \leq s \circ r

in which case it may be proven that s=r ops = r^{op}. A relation is functional if and only if rr op1 Yr \circ r^{op} \leq 1_Y, and is entire if and only if 1 Xr opr1_X \leq r^{op} \circ r.

Further to this: 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 August 24, 2012 20:06:25 by Urs Schreiber (