Relations

A rational discourse's use lies in its ability to describe the relationships among entities of interest. Mathematics can formalise all relationships in terms of relations, characterised by: context gives meaning to r as a relation in so far as it gives meaning, for any values offered in place of left and right, to r relates left to right as a statement, a.k.a. an assertion – i.e. admissible as the subject matter of a proof or disproof, albeit potentially undecidable.

Primitive notions

In so far as a relation, r, relates y to x, I'll describe x as a right value of r and y as a left value of r; I'll describe both x and y as, simply, values of r.

In my writings about relations, I describe relationships among relations; consequently, I allow that relations may be values, so discuss relations whose values are relations. Other contexts, using what I build out of relations, likely opt to limit which relations to entertain as values, thereby restricting the relations discussed. As different contexts may come to different choices as to which relations to accept as values, I prefer to keep my writings indifferent to the question, as if most questions about whether relations are values were undecidable. None the less:

When discussion involves one relation as a (left or right) value of some other, the first is treated as a value, so the above is relevant to it; but the second is only discussed as a relation. If it is not a value, it still serves in the text as a short-hand that relates how it was specified to the things it is shown to relate (or not) to one another.

I introduce denotations for specifying relations, usually in terms of other relations, thereby equipping myself to build tools with which to describe relationships among relations and to construct relations out of other relations.

I'll say that r subsumes s iff s relates x to y implies r relates x to y and, as a synonym, introduce a relation named subsume and specified by: subsume relates r to s iff r subsumes s, i.e.

In all contexts which deal with relations, I deem two relations to be equal if each subsumes the other. Formally this is (as we'll see below) an equivalence. One may reasonably consider two relations to be conceptually distinct entities if they are specified distinctly, even if the two agree entirely on all questions of form do you relate this to that ? All the same, for my purposes, the proper notion of equality when dealing with relationships is this mutually subsumes equivalence, regardless of how the relations are specified. Note that each relation fatuously subsumes itself, hence is equivalent to itself in this sense; and thus equal to itself.

Hopefully it is clear that subsume is not constructible: in my context, it relates itself to itself ! A context which does not entertain it as a value can, none the less, expand every statement I make about subsume into a statement about which relations subsume which others.

Given arbitrary relations r and s, there's a smallest relation which subsumes both and a largest relation which each subsumes, called the union and intersection, respectively, of r with s:

The union necessarily subsumes each of the relations combined, each of which necessarily subsumes the intersection. In so far as two relations are constructible, so also are their union and intersection.

Particular Encodings and Prominent Examples

My formalisation encodes relationships among many entities in terms of chained two-entity relationships, using a technique known as currie-ing (because Haskell B. Currie persuaded some mathematicians and computer scientists that the way to formalise a many-parametered function is in terms of a single-parameter function which takes the first parameter and returns a single-parameter function which takes the second parameter and so on, with the penultimate step producing a single-parameter function which takes the last parameter and yields the over-all result of the many-parameter function). Currie encodes relationships among at least two entities; for less than two entities, we may quibble at calling a predicate a relationship among one entity or calling a statement a relationship among no entities, but they have the right form, so do warrant encoding as relations; to whit

Thus the statements true and false encode as the all-relation (which relates x to y, regardless of their values) and the empty relation (which doesn't relate any value to any value).

A statement can equally be used as a fatuous predicate – true, for any value, iff the statement is true, ignoring the value just as the statement's encoding as a relation ignored both values it was asked about – and the predicates corresponding thereby to true and false give us the universal identity (which relates x to x for every value x, but does not relate any x to any y unless y=x, so this all-collection is not the same thing as the all-relation encoding true directly as a statement) and the empty collection – which is the same relation as the empty relation, since the constraint x and y are the same value is irrelevant when we're going to say no to that value even if this constraint is met.

We thus have the relations (which we'll shortly see to be equivalences: for now, you can ignore this detail, though it affects one name)

Since empty has no values, I can give it meaning in any context at all – it doesn't need to presume any values provided by context; indeed, every relation subsumes empty and empty is vacuously constructible as well as (decidably) computable. The other two may very well be in-expressible to some contexts so, to avoid making my tools useless to those contexts, I shall avoid discussion depending on them. None the less, they equip me with short-forms for various statements, which a context disliking them can safely translate into appropriate long forms; e.g. a relation subsumed by the universal identity is simply one which never relates x to y unless x and y denote the same value, albeit it may be more selective than the universal identity in which values it does relate – indeed, there is a direct correspondence between predicates and such relations.

Salient Properties and Structural Primitives

I'll describe a relation subsumed by the universal identity as a collection or identity: equivalently, a collection is the encoding of a predicate, in the scheme above.

I'll describe a value, x, as a fixed point of a relation, r, iff r relates x to x; in such a case I'll also say that x is in r (because, when r is a collection, its members are its fixed points and, indeed, a collection consists entirely of fixed points). The collection of fixed points of r is simply the intersection of r with the universal identity.

Given two relations r and s, I'll define the composite, r&on;s, of r { [ to the ] left of ; after } s or s { [to the ] right of ; before } r by:

Composition is an unambiguous binary operator: I shall, in due course, establish it as the archetypical binary operator. The temporal connotations of before and after will make more sense when we consider mappings (which regard their right values as inputs and left values as outputs); for the moment, it suffices to note that the definition quite deliberately runs the other way to the order in which English text is normally read.

For a composite, the right values of r&on;s are right values of s (though some right values of s may be missed out) and the left values of r&on;s are left values of r (with a matching proviso, arising because r's right values and s's left values are not guaranteed to coincide – indeed, if there is no overlap, r&on;s will be empty).

I can define a relation, reverse, by: reverse relates r to s iff r relates x to y iff s relates y to x. Fixed points of reverse are often described as symmetric, though I'll prefer to call them fixed points of reverse to avoid confusion with symmetry under other operations. Note that reverse(r&on;s) = reverse(s)&on;reverse(r); that reverse(reverse) = reverse is a fixed point of itself; and that every relation is a fixed point of reverse&on;reverse (i.e. reverse is self-inverse on relations). When reverse relates one relation to another, I'll describe each as the reverse of the other.

I'll describe a relation as left-reflexive iff every left value is a fixed point; and as right-reflexive iff every right value is a fixed point. The reverse of a right-reflexive relation is trivially left-reflexive; and vice-versa. I'll describe a relation as reflexive iff it is both left-reflexive and right-reflexive – i.e. all its values are fixed points; r is reflexive iff r relates x to y implies x in r and y in r. The reverse of a reflexive relation is trivially reflexive.

I'll describe a relation, r, as transitive iff r subsumes r&on;r. The reverse of any transitive relation is necessarily transitive. The intersection of two transitive relations is necessarily transitive. Thus the intersection of a transitive relation with its reverse is trivially transitive.

Note that if r is either left- or right-reflexive, r&on;r subsumes r; in which case, if r is transitive, r&on;r = r. Note that subsume is both transitive and reflexive, so subsume&on;subsume = subsume. Every transitive fixed point of reverse is reflexive (since, if it's r and relates x to y, r (as its own reverse) also relates y to x, hence r&on;r relates x via y to x and y via x to y; and r, being transitive, subsumes r&on;r, so every value of r is a fixed point of r). Note, however, that r&on;r subsumes r, or even r&on;r = r, need not imply that r is reflexive (e.g. when r is < on the rationals or reals – indeed, I'm even considering r&on;r = r but r has no fixed points as a specification of a continuum ordering.)

End-relations

For any relation r, I introduce end-relations (|r:) and (:r|) on r's left and right values, respectively, defined by:

If reverse relates r to s then (|r:) = (:s|); in particular, r = reverse(r) implies (|r:) = (:r|). Since subsume is transitive and reflexive, so are both (|r:) and (:r|), for any relation r. Any reflexive relation necessarily subsumes its left-relation and the reverse of its right relation – given reflexive r: (|r:) relates x to z implies r relates x to everything r relates z to, one of which is z so r also relates x to z; (:r|) relates x to z implies r relates, to x, everything that it relates to z, one of which is z, so r relates z to x. Any transitive relation is necessarily subsumed by its left-relation and by the reverse of its right-relation – if transitive r relates x to z then r subsumes r&on;r which relates x to everything r relates z to, hence (|r:) relates x to z; and r subsumes r&on;r, which relates, to z, everything r relates to x, hence (:r|) relates z to x. Thus any transitive reflexive relation – notably including any end-relation – is necessarily equal to its left-relation and to the reverse of its right-relation. In particular, (|subsume:) = subsume = reverse(:subsume|).

Using end-relations, I define restriction denotations; (r:s:t) = (:r|)&on;s&on;(|t:)

For any relations f and g, (|f&on;g:) subsumes (|f:g) and (:f&on;g|) subsumes (f:g|).

Proof: suppose (|f:g) relates x to z; so {y in (|g:): f relates x to y} subsumes {y in (|g:): f relates z to y} and neither is empty. Now suppose f&on;g relates z to some w; implicitly, f relates z to some y which g relates to w; but then f must also relate x to y, hence f&on;g relates x to w as well. Thus {y: f&on;g relates x to y} subsumes {y: f&on;g relates z to y}, so (|f&on;g:) relates x to z. Thus (|f:g) relates x to z implies (|f&on;g:) relates x to z, i.e. (|f&on;g:) subsumes (|f:g).

Analogously, suppose (f:g|) relates x to z; so {y in (:f|): g relates y to x} subsumes non-empty {y in (:f|): g relates y to z}; composing f on the left of either of these yields {w: f&on;g relates w to x} subsumes {w: f&on;g relates w to z}; thus (:f&on;g|) subsumes (f:g|).

At the same time, note that {x in (|f&on;g:)} = {x in (|f:g)} and {x in (:f&on;g|)} = {x in (f:g|)}.

Equivalences and end-equivalences

I'll describe a relation as an equivalence iff it's a transitive fixed point of reverse; as noted above, this necessarily implies that it is reflexive. Because it is transitive and reflexive, any equivalence is necessarily equal to its left-relation and the reverse of its right-relation; because it is a fixed point of reverse, this means it is also equal to its right relation.

Notably, the all-relation is an equivalence, as is every collection, including empty. The intersection or union of any relation with its reverse is necessarily a fixed point of reverse; if the original relation was transitive, so is the intersection, which is thus necessarily an equivalence.

For any given relation r, intersecting either (:r|) or (|r:) with its reverse will yield an equivalence; I call these the end-equivalences of the relations (and used to, before 2004/June, use (:r|) and (|r:) to denote them; this does not change which values are their fixed points). I'll describe the end-equivalence thus obtained from (|r:) as r's left-equivalence and that from (:r|) as r's right-equivalence; and I'll describe values related by these equivalences as being (|r:)-equivalent and (:r|)-equivalent respectively, notwithstanding that (|r:) and (:r|) might not themselves be equivalences.

For any relation f, f&on;reverse(f) is a relation among f's left values; it is symmetric and reflexive; and it subsumes (|f:). Likewise, reverse(f)&on;f is a symmetric reflexive relation among f's right values and subsumes (:f|). [Forward reference: mapping and monic.] For a mapping, f&on;reverse(f) = (|f:) is a collection and reverse(f)&on;f = (:f|) is an equivalence; for a monic, reverse(f)&on;f = (:f|) is a collection and f&on;reverse(f) = (|f:) is an equivalence.

Whence and Whither

I'll say that one relation, e, conforms with another, c, precisely if c relates at least one value of e to each value of c and, whenever c relates one value of e to another, so does e. I'm mainly concerned to apply this to end-relations, which are transitive and reflexive; in this case, e conforms with c can be encoded as {x in (:e&on;c|)} = {x in (:c|)} and e subsumes (e:c:e). Composing c on the right of the former, with e and c reflexive and transitive, we can infer that: c relates u to v implies {x in (:e|): c relates x to v} subsumes {x in (:e|): c&on;c relates x to v} subsumes {x in (:e|): c relates x to u} implies (e:c|) relates v to u; thus the first condition implies that (e:c|) subsumes c; which, in turn, implies the given first condition, so the two are equivalent. Thus, for transitive reflexive e, e conforms with c iff (e:c|) subsumes c and e subsumes (e:c:e).

I'll describe a relation, r, as being from [{ within ; all of }] right precisely if: (|right:) subsumes (r:x←x:) and; either within is specified or reverse(:r|) conforms with (|right:). In the latter case, I'll write (:r|right), which makes the given assertions. For the sake of practical match-up with orthodox language further down the line, from's default is from all of, making the covering assertion; but from within just asserts that (|right:) subsumes (r:x←x:), i.e. every right value of r is a left value of right.

I'll describe a relation, r, as being [{ in ; on }] to left precisely if: every left value of r is a right value of left and, if on is used, (|r:) conforms to reverse(:left|). In the latter case, I'll write (left|r:), which makes the given assertions. In contrast to from, but again for match-up with orthodox language, the default form of to is in to (or into) which only asserts that (:left|) subsumes (:x←x:r); use of on to (or onto) makes the added assertion that r's left-relation conforms with left's reversed right-relation. (The reversals are due to subsume being opposite ways round in left- and right-relations.)

I'll combine these two in the obvious way – given collections A and Z, a relation from A to Z is (Z:r|A) or from all of A in to Z, which will match up with orthodox language for functions (as contrasted with partial functions, which are from within); r will be epimorphic if (it's a function and) it's (Z|r:A) or from within A on to Z. The corresponding statements for more general relations (rather than collections and functions) take account of pertinent equivalences, factoring out the need to operate on values via equivalence classes of which they are members.

Theorem: if g is from [within] A onto f and f is from g [on] to Z then f&on;g is from [within] A [on] to Z.

Proof: first, consider the case using [within] but not [on]. This case is trivial, since: every left value of f&on;g is a left value of f, hence a right value of Z; and every right value of f&on;g is a right value of g, hence a left value of A.

For the other cases, we need the consequences of the conforms with constraints g onto f and f from (implicitly: all of) g. These tell us, first, that (|g:) relates each left value of g to at least one right value of f; and (:f|) relates each right value of f to at least one left value of g. If f relates x to y, then it also relates x to any right value of f to which (:f|) relates y, hence in particular to at least some left value of g, so f&on;g relates x to some right value of g. If g relates y to z then it also relates, to z, any left value of g that (|g:) relates y to; hence it relates at least some right value of f to z. Thus f&on;g has the same left values as f and the same right values as g. Our conforms with constraints also tell us that, whenever u and v are left values of g and right values of f, (:f|) relates u to v iff (|g:) relates u to v. Thus if f relates x to y and

Does a relation from or to an end-relation intrinsically conform with the end-relation aside from the need to cover all of it ?

Mapping, monic and iso

I define three types – monic, mapping and iso – that refine the from and to type specifiers given above. These stipulate uniqueness properties, expanded enough to allow unique modulo a suitable equivalence. These type denotations match the template:

Grammatically, iso and monic are adjectives; when a noun is needed a text may treat either as if it were a noun; or use isomorphism or monic relation as appropriate; either can equally be used to qualify some other noun. When mapping is qualified by some adjective – or adjectival clause – it is common to contract it to map, most notably in a linear map, which just means a mapping which is linear.

An iso – a.k.a. monic mapping – is also known as a correspondence: if qualified as from A to Z, it identifies the equivalence classes of (|A:) with those of (:Z|), one-to-one; if unqualified – i.e. implicitly qualified on its end-collections – or only qualified on collections, it identifies its left and right values one-to-one – each equivalence class of a collection is a singleton.

The defaults for left and right are collections, which leads to mapping, monic and iso being uniqueness requirements when unadorned (these match their orthodox meanings). When C is a collection, C relates e to g just says e = g; the constraints above are thus simplified to: mapping (:r:A) relates h to a and i to a iff h = i; and monic (Z:r:) relates h to a and h to b iff a = b. A mapping to a collection has a unique output (left value) for each input (right value); correspondingly, a monic from a collection has a unique right value for each left value (though it may use the same right value for several left values, just as a mapping may produce the same output in response to several inputs). More generally, a mapping pulls back an equivalence on its left values to imply one on its right values; while a monic pushes one forward the other way.

For f = (Z:f:A) to be a mapping from A to Z, the above requires (:Z|) to subsume f&on;(|A:)&on;reverse(f), which certainly subsumes f&on;reverse(f) and hence (|f:A); while monic requires (:A|) to subsume reverse(f)&on;(:Z|)&on;f, which certainly subsumes reverse(f)&on;f and hence (Z:f|). For each z in (|f:), f&on;reverse(f) relates z, via each a in ({z}:f|), to each x in (|f:) which f relates to a member of ({z}:f|); when Z is a collection, subsuming f&on;reverse(f), z must be the only such x, though there may be several a in ({z}:f|); so each right value, a, of f has exactly one left value related to it, making f(a) an unambiguous denotation.

The reverse of a monic relation is a mapping; the reverse of a mapping is monic. Consequently, though I shall concentrate my attention on the world of mappings, everything I prove about mappings delivers a natural dual truth about monics; but I shalln't always go into its details, given that they're simply obtained by judicious application of reversal.

Any right value of a right-reflexive relation, f, is a fixed point of f; if, furthermore, f is a mapping to a collection, its inputs are its right values, hence fixed points of f, so f is an identity; thus any right-reflexive mapping to a collection is a collection. Likewise, a left-reflexive monic from within a collection is a collection.

A left-reflexive mapping is also, at least in some contexts, described as a projection. Given a mapping f, saying that it is left-reflexive amounts to saying that it acts as the identity on its outputs (left values); it maps each output only to itself. We can thus infer that f = f&on;f and, in particular, that every projection is transitive.

Theorem: any composite of monics is monic; any composite of mappings is a mapping. Proof: suppose f and g are monic. If f&on;g relates some x to some y and to some z; infer that f relates x to some u which g relates to y and f relates x to some v which g relates to y; but f is monic, so u is v and g relates it to both y and z; but g is monic, so y is z. Thus f&on;g is monic. One can reason likewise for mappings, or simply exploit that fact that their reverses are monic, so have monic composite, whose reverse is thus a mapping; yet equal to the original composite of mappings.

Generalisation: if g is monic from within A onto f and f is monic from g to Z then f&on;g is monic from within A to Z; if g is a mapping from within A onto f and f is a mapping from g to Z then f&on;g is a mapping from within A to Z. Note that g is onto f and f is from (all of) g, hence (|g:) relates each of g's left values to at least one right value of f, so g relates, to each of its right values, at least one right value of f, thus Suppose the first case and f&on;g maps a to c and j to h while (|:) relates c to h.

suppose f is monic from Y to Z and g is monic from X to Y. Suppose (Z:f&on;g:) relates a to c and j to h while (|X:) relates c to h; so f relates a to some b which g relates to c; and f relates j to some i which g relates to h; g is monic from X, relating b to c and i to h and (|X:) relates c to h, so we infer that (:Y|) relates b to i; We then need (|Y:) to be (:Y|) so that this implies, via f monic, (:Z|) relates a to j.

Transposition and its kin

Reverse just corresponds to swapping the names used in the two-relationship underlying a relation. For a many-name relationship, one may wish to perform an arbitrary permutation on the names: to describe such permutations in terms of the relations by which currie-ing encodes the relationship is, in general, somewhat fiddly – it is usually better to use some other encoding of the many-name relationship, if such permutation will often be needed. For example, one can encode the many-name relationship as a relation whose right values are lists of the successive right values to be supplied to: the relation encoding it, the left values thereof, and so on; one can then compose a permutation with this list – and, optionally, re-currie the result to undo the enlisting operation.

However, the commonest case is when we swap the two values combined by a binary operator – known as transposing the binary operator. If I construe a binary operator, *, in its aspect as the relation (: c← (: c=b*a; b←a :) :), I can express transposition by composing this relation to the left of reverse. However, it is more usual to encode the binary operator as (: (: b*a ← b :) ← a :) which obliges us to actually do some work to express transposition.

The transpose, t, of a relation, r, is a mapping defined by: t(a) relates c to b (i.e. maps b to c, when t(a) turns out to be a mapping) iff r relates, to b, some s which relates c to a:

This may be re-cast as (: r(b) relates c to a; c ←b :) ←a, or, indeed, (: r(b,a) ←b :) ←a; for contrast, r = (: (: r(a,b) ←b :) ←a :) is fatuous whenever r's left values are all relations.

Relations: formalising relationships

Contents