]> Composing Relations

# Composing Relations

I define composition on relations; it's a combiner and, in an important sense, it serves as the universal combiner. Its definition is, given relations r and s,

• r&on;s = (: x ←z ; r relates x to some y that s relates to z :)

It can be used to combine any two relations whatsoever, albeit many cases shall give the empty relation as composite simply because the left operand has no right value that's a left value of the right operand (there is no y, in the above, that r has as right value and s as left value). Swapping the order of its operands typically changes the result: r&on;s need not be equal to s&on;r.

## Easy Consequences

From the definition, given any relations a, b and c, observe that: (a&on;b)&on;c relates w to z precisely if a relates w to some x which b relates to some y which c relates to z precisely if a&on;(b&on;c) relates w to z; whence that (a&on;b)&on;c = a&on;(b&on;c) – composition is associative. Thus we are able to write a&on;b&on;c unambiguously and likewise for longer (finite) sequences of relations.

Every relation is an operand that &on; accepts both on its right and on its left; and every composite of relations is a relation, so {relations} is closed under &on; and &on; is closed. Given associativity, it is thus a combiner. As it combines any relation with any relation, it is furthermore flat. It is neither cancellable nor complete; it does have an identity (the universal identity (: x ←x :) composes on either side of any r to give r) but most relations don't have inverses under it (if only for want of some left or right values of the universal identity).

Given relations r, s consider reverse(r&on;s); this relates z to x precisely if r&on;s relates x to z, precisely if r relates x to some y that s relates to z, precisely if reverse(s) relates z to some y that reverse(r) relates to x, precisely if reverse(s)&on;reverse(r) relates z to x. Thus reverse(r&on;s) = reverse(s)&on;reverse(r) and reverse is a (self-inverse) coautomorphism of the binary operator &on; (or cofunctor on its category).

A mapping is simply a relation that, for any given right value (input) only relates one left value to it (the output to which it maps the input); a monic is likewise a relation that, for any given left value, only relates it to one right value; the reverse of a mapping is monic, and vice versa. Formally, a relation r is a mapping precisely if r relates w to y and x to y implies w = x; r is monic precisely if r relates x to y and x to z implies y = z. If we now compose two mappings, f&on;g, and the composite relates v to z and w to z, we can infer that it related v via some x to z and w via some y to z; since g then relates x to z and y to z, with g a mapping, we can infer x = y, thus f relates v to x and w to x = y hence, as f is a mapping, v = w; this being true whenever f&on;g relates v and w to the same z, we can infer that f&on;g is a mapping and any composite of mappings is a mapping. Likewise, every composite of monics is a monic.

## End-relations of composites

For any relation r, its collection of left values is (: x ←x :r) and its collection of right values is (r: x ←x :). I also define end-relations, on these two collections (respectively), by

• (| r :) = (: x ←y ; {u: r relates x to u} subsumes {u: r relates y to u}, which is not empty :)
• (: r |) = (: x ←y ; {u: r relates u to x} subsumes {u: r relates u to y}, which is not empty :)

The former is r's left-relation, among its left values; the latter is its right-relation, among its right values. Each is transitive and reflexive (because subsumes is). So now let us consider how the collections of values and the end-relations of a composite relate to those of the relations composed.

Every left value of r&on;s is necessarily a left value of r, so (: x←x :r) subsumes (: x←x :r&on;s) and likewise (s: x←x :) subsumes (r&on;s: x←x :). It's eminently possible for r to have left values that it only relates to right values that aren't left values of s, and likewise with left swapped with right and r swapped with s, so in each case the subsumes definitely can be strict – r can have left values, and s can have right values, that r&on;s lacks.

Every value of (| r&on;s :) is a left value of r; and we may have some left values of r that aren't left values of r&on;s. In particular, r may relate x to y, x to b and c to b for some y that is a left value of s, b that isn't and c that r doesn't relate to anything else. In such a case, {u: r relates x to u} subsumes {u: r relates c to u}, so (| r :) relates x to c; but c is not a value of (| r&on;s :); so (| r&on;s :) definitely doesn't subsume (| r :). On the other hand, as x is a left value of r&on;s (because r relates x to y, which is a left value of s), any w that (| r :) relates to x must also (be related by r to y, hence) be a left value of r&on;s and, since r relates w to every y that r relates x to, via which r&on;s can relate x to anything, r&on;s must in fact relate w to everything it relates x to; so x is a left value of r&on;s and (| r :) relates w to x implies (| r&on;s :) relates w to x. Thus we find that (| r&on;s :) subsumes (: (| r :) :r&on;s), the restriction of (| r :) to those left values that r does actually relate to some left value of s. The corresponding statement for the right-relations is a little more unwieldy, (: r&on;s |) subsumes (: (: s |) :(r&on;s:x←x:)) but, in any case, what we have isn't particularly neat.

So let's look instead at (| r :s), the left-equivalence of the restriction of r to only those right values that s has as a left-value; this cuts out any left values of r that aren't left values of r&on;s. It may also relate some left values of r to one another that (| r :) didn't: if r relates x to y, w to y, x to b and w to c, with b and c distinct, while s has y but neither b nor c as a left value, then (| r :) won't relate x to y or y to x, while (| r :s) relates each to the other. We can, however, be sure that (| r :s) subsumes (: (| r :) :r&on;s), just as (| r&on;s :) does, for exactly the same reason. For the right-relation, naturally, (r: s |) likewise subsumes (: (: s |) :(r&on;s:x←x:)).

So first suppose that (| r :s) relates w to x; we know r relates each of them to at least some left value of s, hence both are left values of r&on;s. So suppose r&on;s relates x to z; it necessarily does so via some y, that r relates x to and that s relates to z; as (| r :s) relates w to x, r also relates w to y, hence r&on;s relates w to z. Thus (| r :s) relates w to x implies r&on;s relates x to z implies r&on;s relates w to z, hence (| r&on;s :) relates w to x; so (| r&on;s :) subsumes (| r :s). Likewise, (: r&on;s |) subsumes (r: s |).

When (| r&on;s :) relates w to x, it's possible that r relates w and x to some y that s relates to z and r also relates x, but not w, to some c that s relates to z; because this last doesn't add anything to what r&on;s relates x to, (| r&on;s :) doesn't notice it, but (| r :s) does, so won't relate w to x. Thus the converse of the preceding doesn't hold: (| r :s) needn't subsume (| r&on;s :) and, likewise, (r: s |) needn't subsumes (: r&on;s |).

## Restricted composition

The tendency to get empty composite, arising from composition happily combining any two arbitrary relations, somewhat limits what one can usefully say about composition; however, we can define restrictions of it that play nicer, at the expense of being more picky about what relations they compose. We may even be able to improve on the preceding section's slightly unsatisfactory results.

Orthodoxy spends a lot of time looking at functions (U: |V) for various sets U, V; and typically only wants to compose functions (U: f |V) after functions (V: g |W), for some set W; because every left value of g is a right value of f, we are assured that the composite is (U: f&on;g |W); it hasn't ignored any of g, although it might have ignored some of f. The price I pay for working with equivalences in place of sets is that I have to be rather more careful about what condition I impose in place of every left value of g is a right value of f. When U, V and W get replaced by equivalences, I need (U: f |V) to respect the equivalence U: if f relates u to x and v to y with x and y V-equivalent, I need u and v to be U-equivalent for f to feel enough like a mapping; and I need f to at least have a right value V-equivalent to each member of V, albeit some members of V might not be right values of f. Given similar for g, similar should then be implied for f&on;g. Since g's left values are apt to be a canonical (from g's point of view) member in each V-equivalence class, I think I do want to insist that (U: f |V) actually does have every member of V as a right value, not just a right value V-equivalent to each member of V. The V-equivalence of any left values of g for W-equivalent right values then combines with the U-equivalence of f's left values for the right values it gets from g to ensure f&on;g's left values for W-equivalent right values are indeed U-equivalent. I think (: (:U|)&on;f |) needs to subsume V, in fact; and I think it's probably satisfactory to oblige f to do enough of the (:U|) part to ensure that (:f|) subsumes (|V:).

So I describe composition of r after s, r&on;s, as

clean
precisely if (:r|) subsumes (|s:)
co-clean
precisely if (|s:) subsumes (:r|), and as
iso-clean
precisely if (|s:) = (:r|), i.e. the composition is both clean and co-clean.

In each case, the given assertion about end-relations also implies a matching assertion for the end-collections (r: x←x :) in place of (:r|) and (: x←x :s) in place of (|s:).

The first of these is the usual constraint for composability of functions (with support for equivalences tacitly included) and is the one that'll see most use, in particular by homomorphisms. These restricted compositions are categoric rather than flat (as raw composition is), as are the proper compositions of homomorphisms (of various types) derived (usually) from clean composition.

When a composite r&on;s is clean, (s: x←x :) = (r&on;s: x←x :) because (the left side fatuously subsumes the right and) every left value, that s relates to any given right value, is a right value of r so r relates something to that hence r&on;s relates this something to the given right value of s, making it also a right value of r&on;s. In like manner, for a co-clean composite, we get (: x←x :r) = (: x←x :r&on;s); and, in the iso-clean case, both equalities hold. The main upshot of this is that composing two functions cleanly gives a function that accepts all the inputs that the right component does; f&on;g accepts all inputs g accepts.

Next consider the case of three relations r, s, t with r&on;s clean and s&on;t clean; because (r&on;s: x←x :) = (s: x←x :) which subsumes (: x←x :t), the composition (r&on;s)&on;t is also clean; and, since (r: x←x :) subsumes (: x←x :s) which necessarily subsumes (: x←x :s&on;t), the composition r&on;(s&on;t) is also clean. Thus a chain of composition, in which each adjacent pair compose cleanly, is clean as a whole, not just at each pair. Naturally, the same duly holds also for co-clean and iso-clean compositions.

## Factorisability

This is an incomplete discussion !

We can use the relationship between end-relations of composites and those of components to (at least partially) characterise whether a given relation may be expressed as a composite, for given candidates as left-most and right-most component: if r is to be factorised as compose([f,…,g]), (|r:) and (:r|) must subsume ((:x←x:r)| (|f:) :) and (: (:g|) |(r:x←x:)), respectively. [The left | seen in ((:x←x:r)| (|f:) :) asserts that every left value of r is a left value of f, while the whole denotation stands for the restriction of (|f:) to r's left values.]

If we allow any components between f and g – the … in [f,…,g] – we can reliably replace them all by their composite – i.e. replace [f,…,g] with [f, compose([…]), g] – so the only cases to consider are whether f&on;g or f&on;q&on;g can be r. For given f we can ask whether there's some g for which f&on;g is r; we can trivially pose this as a request for some q for which f&on;q&on;(:r|) is r; then g is q&on;(:r|). Likewise, for given g, asking for an f for which f&on;g is r can be posed as a request for q with (|r:)&on;q&on;g = r; f is then (|r:)&on;q. So, in all cases, questions about the ability to factorise r via given left and/or right components are, without loss of generality of form: given r, f and g is there a q for which f&on;q&on;g = r ? Clearly, the above gives necessary conditions; are they sufficient ?

Now, if we're given r, f and g for which (|r:) subsumes ((:x←x:r)| (|f:) :) and (:r|) subsumes (: (:g|) |(r:x←x:)), can we find a q for which r is f&on;q&on;g ? Note that, given arbitrary relations f, g and r, we can use (|f:)&on;r&on;(:g|) to obtain a replacement for r which does meet the given conditions; albeit the replacement may quite readily be empty. Note that if either (|r:) or (:r|) is empty then so is the other and so is r, in which case q = empty solves our problem. If either f or g is empty and r satisfies the constraints given, then r is also empty. Indeed, when r is empty, q = empty will always give f&on;q&on;g = empty, regardless of f and g: empty is factorisable via anything and only empty is factorisable via empty.

Written by Eddy.