# Relations

One can characterize a relation as being any s for which the question does s relate x to y ? is meaningful whenever x and y stand for values, though (as ever) it need not always be decidable. Two relations, s and r, are then taken to be equal precisely if s relates x to y iff r relates x to y for arbitrary values x and y. (This is the axiom of extensionality.)

Any statement may, in these terms, be said to relate any two of the values it mentions: for instance, Daniel Welbourne is Eddy's father may be read as a (singleton) relation which relates Daniel Welbourne to Eddy. It is a restriction of the more general relation X is Y's father; X->Y. Note that the same statement may also be read as a relation which relates Daniel Welbourne to father: as such it is a restriction of X is Eddy's Y; X->Y.

A general relation is a template for a statement, having two slots in it to be filled by values, which are duly related if the statement holds true when they are used to fill the slots. Note that does s relate x to y ? need not be symmetric between x and y: so which slot in the template is taken as x and which as y is a material choice, which will affect the reading of the statement-template as a relation.

Whenever a relation, s, relates x to y I'll describe x as an initial value of s and y as a final value of s. This will save me introducing an initial value of s as some x for which there is a y for which s relates x to y. I'll describe both initial and final values of any relations as, simply, values of the relation.

There is a natural composition on relations: the composite of s before r or r after s, which I'll write as r&on;s, relates x to z precisely if s relates x to some y while r relates that y to z. [The order of the expression, r&on;s as s before r but with s on the right, conflicts with the common reading order of English text: get used to it, it is a natural consequence of following that orthodoxy which writes f&on;g for x->f(g(x)), when f and g are mappings.]

I'll describe composition (of s before r, as above) as clean precisely if [(|r) subsumes (s|)] every final value of s is an initial value of r – when discussing mappings, it is usual to work with clean composition. I'll occasionally describe r&on;s as coClean when the implication goes the other way – that is, [(s|) subsumes (|r)] every initial value of r is a final value of s – and as isoClean when both clean and coClean – that is, [(s|)=(|r)] x initial for r iff x final for s. [Indeed, a relation (r|s:t) composes cleanly after r and before t: likewise, (r:s|t) composes coCleanly after r or before t, as appropriate; and s= (r|s|t) tells us the compositions in t&on;s&on;r are all isoClean.]

There is a relation, called empty, which doesn't relate anything to anything: there is also a relation, all, which relates everything to everything. There is a relation, called reverse, which relates relation r to relation s precisely if r relates x to y is equivalent to s relates y to x: it is worth noticing that reverse relates reverse to reverse. There is a relation called fixed-point which relates a value x to a relation r precisely if r relates x to x: we then say that x is a fixed point of r.

I shall abbreviate x is a fixed point of r, at least in formulae, to x is in r: fixed point is going to serve me in a rôle which generalizes membership of collections. [Since every value of an identity (i.e. a collection) is a fixed point of it, this has exactly the orthodox meaning for collections: in general, in treats any relation the same as the collection of fixed points of that relation, which is just the maximal identity it subsumes. But for this we need identities, which I haven't yet defined.]

## Sub-Relations and related notions

There's a relation, called sub-relation, which relates one relation, r, to another, s, precisely if r relates x to y implies s relates x to y: r is then described as a sub-relation of s and I'll say that s subsumes r. One way of obtaining sub-relations from a relation is by restriction: for relations r, s, t we have (r:s:t) which relates x to y precisely if

• s relates x to y,
• x is a final value of r and
• y is an initial value of t.

Sub-relations of s need not all be of this form, but those which are are known as restrictions of s. If all initial values of s are final values of r (e.g. if r = (|s)), then r is irrelevant in the above so may sensibly be left out. Similarly, t may be elided if (|t) subsumes (s|).

The relation sub-relation will warrant a huge amount of discussion in due course. For the moment, let me introduce two crucial notions connected with it:

union

The union of relations r, s is a relation, r&unite;s, which relates x to y precisely if either r or s does so: I'll write it r&unite;s.

intersection

The intersection of r with s is the relation, r&intersect;s, which relates x to y precisely if both r and s do so.

Each relation united into a union is a sub-relation of that union; and any intersection is a sub-relation of each of the relations intersected to produce it. To generalize union and intersection to take lots of relations, rather than just two (or finitely many, which repetition of two can get us), we need some way of specifying a collection of relations. For this, final values of some relation (typically, indeed, a collection, whose final values are its members), suffice: I define

unite
relates r to u iff u is the relation which relates x to y precisely if there is some final value of r which relates x to y; and
intersect
relates r to u iff u is the relation which relates x to y precisely if every final value of r relates x to y.

## Atoms and isolation

The empty relation is a sub-relation of every relation: every relation is a sub-relation of itself. A proper sub-relation of a relation r is one which is equal to neither r nor empty. A relation is described as atomic precisely if it is non-empty and has no proper sub-relations. A relation which only relates (nothing but x to anything, nothing to anything but y, and) some given x to some given y is a sub-relation of any relation which relates x to y (indeed, it is the intersection of all relations which relate x to y). I shall call such a relation a singleton: it is clear that its only sub-relations are itself and empty, so it is atomic.

A non-empty relation, r, is one which relates some x to some y: it therefore has a singleton sub-relation, which is either a proper sub-relation of r or equal to r; so if a relation is atomic it must be equal to some singleton. Thus singletons are the only atomic relations. [It may, however, be sensible to treat a non-singleton, r, as computationally atomic if it is not practical to actually exhibit a proper sub-relation of r - provided, that is, there is still enough we can decide about r to make it worth discussing in the first place.]

I'll describe two relations as disjoint precisely if their intersection is empty. Note that this still admits the possibility that they have some initial or final values in common – but they cannot have any fixed points in common. Consequently, disjoint reflexive relations (see below) have no initial values, final values or fixed points in common.

## Mappings and Collections

It is easy enough to define mappings – as relations which relate any value to at most one value; when such a relation relates x to y, it is said to map x to y. Any sub-relation, s, of a mapping, f, is s= ((|s):f:) and so is a restriction of f.

Equality is the relation which relates x to y precisely if x=y (a notion which I presume context to have defined for all values it admits, whether or not it is decidable, which is why the definition of relations comes with a definition of equality thereon). It is trivially a mapping. I'll call any sub-relation of equality an identity or collection. [Restrictions of equality may equally be thought of as diagonal relations.] The composite of any relation, r, with equality (in either order) is r. For any relation, r, we have collections of initial, (|r) = (:equal:r), and final, (r|) = (r:equal:), values: these are just the identities which have the same initial and final (respectively) values as r. When r is, itself, an identity, these are both r.

The reverse notion to mapping, a relation which relates at most one value to any given value, may sensibly be called monic: but I'll usually just say that the relation's reverse is a mapping or introduce this mapping and discuss its reverse. A mapping whose reverse is also a mapping is called one-to-one: in particular, any mapping which is equal to its reverse (i.e. symmetric) is one-to-one – for example, both reversal and equality.

For any mapping f, the composite f&on;reverse(f) is an identity – it is equal to (f|) – and reverse(f)&on;f is an equivalence (see below). When f is one-to-one, the latter is the identity (|f).

## Equivalences

A relation is described as symmetric if it is equal to its reverse. A relation, r, is described as reflexive precisely if it has, as fixed points, all its values – i.e. r relates x to y implies r relates x to x and r relates y to y. This, equivalently, means that (|r) and (r|) are sub-relations of r – whence, indeed, (|r)=(r|). A relation, r, is described as transitive precisely if its self-composite, r&on;r, is a sub-relation of r. A relation which is symmetric, reflexive and transitive is known as an equivalence. Any identity is trivially an equivalence.

The fixed-point notion, above, then lets me describe a value, x, as being in an equivalence, S, precisely when S relates x to x – which is, by reflexivity, true whenever S relates x to anything or anything to x. A sub-relation, S, of an equivalence, C, is referred to as a sub-equivalence of C precisely when, for every initial x and final y of S, S relates y to x precisely if C does – i.e. (S:C:S) = S. (In particular, this says that (|S) = (S|).)

Equivalences deserve their own page.

### Complements

This section uses a newer notation than the rest of the page.

There is a relation, not, which relates r to s precisely if: their intersection is empty and their union is an all-relation – i.e. for each left value x of either and right value y of either, precisely one of r and s relates x to y. Clearly reverse(not) = not and not relates empty to every all-relation (so not is neither monic nor a mapping), including empty itself, which is thus the unique fixed point of not (unique because any fixed point of not has empty intersection with itself, hence is empty). As not = reverse(not), not&on;not subsumes (|not:) = (:not|), which is an equivalence on relations.

If not relates A and B to Z then the intersection of A with B is disjoint from Z; and its union with Z is the intersection of the two all-relations obtained by uniting each of A and B with Z; any intersection of all-relations is an all-relation, so not also relates A&intersect;B to Z and, indeed, intersect(:not:{Z}) to Z. If not relates A to Z, let B = ((|Z:): A :(:Z|)); then A subsumes B and, since Z = ((|Z:): Z :(:Z|)), B&unite;Z is just ((|Z:)| A&unite;Z |(:Z|)) which is an all-relation; and B&intersect;Z is empty because subsumed by A&intersect;Z, so not also relates B to Z, so B subsumes intersect(:not:{Z}). Now, if B relates x to y then Z doesn't so, if not relates C to Z, the union of C and Z is an all-relation; x and y are left and right values of Z, respectively, hence also of any relation which subsumes Z, hence of this all-relation; but Z doesn't relate x to y, so C must; so C subsumes B and, conversely, A subsumes ((|Z:): C :(:Z|)) whence this last is equal to B and (: ((|Z:):A:(:Z|)) ←A :not&on;{Z}) is constant: not relates the sole output of this constant to Z, and anything else not relates to Z subsumes it; so it is intersect(:not:{Z}).

Thus empty = intersect(:not:{r}) for any all-relation r, including r = empty and r = {a} for any single value a, while intersect(:x←x:not&on;{{a,b}}) = unite({a←b,b←a}) for arbitrary values a and b. Note that not does distinguish between all-relations, despite relating them all to empty: not relates empty to any all-relation, while the only all-relation it relates any other all-relation to is empty itself; not doesn't relate all-relation a to any relation which relates any left value of a to any right value of a – e.g. any all-relation whose left and right values overlap with those of a – but anything non-empty that not relates a non-empty all-relation to must share all the all-relation's left and right values (so as to relate them to other values), while not relating any of these to one another (so as to be disjoint), so can't be an all-relation.

Note that the mapping, knot = (: intersect(:not:{Z}) ←Z :{relations}) maps every all-relation to empty, so it's not monic and isn't equal to its own reverse. In general, composing knot&on;knot maps any Z to a sub-relation, Y, for which: let L = {x: ({x}:Z|) = (:Z|)} and R = {x: (|Z:{x}) = (|Z:)}; so Z subsumes the (L:all:(:Z|)) and ((|Z:):all:R), which overlap in (L:all:R); then Z is the union of these all-relations with Y = knot(knot(Z)), which is disjoint from these all-relations.

## Disjoint sums

The disjoint sum, e+i, of a pair, [e,i], of identities gives us a collection of tagged values: as if it were the union of {[x,]:x in e} and {[,y]:y in i}, for some reading of [x,] and [,y]. The crucial thing is that if we have some c in the intersection of e and i, we can distinguish [c,] from [,c]. To do that we need to be able to ask a member of e+i two questions: how are you tagged ? and what is your value ?. This is not so hard: the answer is to make [x,] be the singleton mapping 1->x, with [,y] = 0->y. Thus the disjoint sum becomes a collection of singletons: a member's tag is the one input it will accept, and its value is its one output.

This is generalized by the disjoin mapping: disjoin(r) relates x to s precisely if s is a singleton sub-relation of some member of ({x}:r|). Notice that unite({x}:disjoin(r)|) = unite({x}:r|) [which is {r(x)} when r is a mapping] for each x in (|r); that unite(r|) = unite(disjoin(r)|); and that disjoin&on;disjoin = disjoin. When r is a pair of collections, so r= [r(1),r(0)] and each r(j) is a collection, disjoin(r) is the collection of singletons each of which takes an input, j, of r, i.e. either 0 or 1, and produces an output in r(j). With e=r(1) and i=r(0), this is just the disjoint sum above.

## Purity

Time for an inductively defined meta-notion. For any type of relation, I'll describe a relation as being pure, of that type, if all its values are pure of that type. Thus a pure set is one whose members are all pure sets, a pure function is a mapping from a set of pure functions to a set of pure functions and so on. The sets of pure functions in this last case are, synonymously, identity functions on themselves: as such they are pure functions, but need not be pure sets – though every pure set is a pure function. All very neat and tidy, but what about exhibiting some ?

Inevitably, we can examine the empty relation, which happens also to be a set (hence function, collection and mapping by turns) and find that it has no values so the purity condition is fatuously satisfied (for every type). We can thus build a relation, the singleton empty->empty, which is equivalently the set {empty}, which is a pure set (hence all the others above) because its one value, empty, is a pure set. We can now build singletons empty->{empty}, {empty}->{empty} and {empty}->empty, all of which are pure functions, the second being the pure set {{empty}}. We can keep building singletons like this, and we can (as I'll shortly show) take unions of the ones we've built this far. This fairly rapidly lets us build a large collection of pure relations, but let's have some tools to help us.

If a union or non-empty intersection of pure things of some type is also of that type, then it is pure. This follows because any member of the result is a member of at least one pure thing of the relevant type, hence is pure of that type. Where we can build things up from singletons, which are minimal non-empty relations, there is no real use to intersection, which is fine by me. If the successor of a pure thing of some type is, likewise, of that type then it is also pure (it's only gained one new value, which we know to be pure).

Thus: every natural number is a pure natural number, and an ordinal; every ordinal is a pure ordinal, and a pure set; every set of pure sets is a pure set, a pure collection, and a pure function; every mapping between sets of pure functions is a pure function; every collection of pure collections is a pure collection, and a pure mapping; every mapping between collections of pure mappings is a pure mapping, and a pure relation; any relation whose values are all pure relations is a pure relation. This gives us plenty of pure things of each kind.

Notice that the restriction of All to pure relations is a pure relation and the collection of pure collections is a pure collection: hence each of these is its own successor. The collection of pure sets isn't a set, as it subsumes the collection of pure sets which are not members of themselves, which would be pure, if it were a set, so we'd have to ask whether it is a member of itself and find that if it is it isn't and vice versa.