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. something either true, false
or undecidable.
universal identity.
is in; &on; as composition; reversal, transitivity and reflexivity.
from A to Bwhile leaving enough slack to be useful.
See also:
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, my discourses interpret relations as values
and entertain
relations whose values are relations. 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.
s relates x to yimplies
r relates x to y:)
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.
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:
r relates x to y or s relates x to y
r relates x to y and s relates x to y
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
collectionsor
identities.
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)
defined by: empty relates x to y
is false, regardless of the values given for x and y; i.e. empty doesn't relate
anything to anything.
which relates any value to itself, but to nothing else; it could equally be denoted {values}; and
the all-relation or all-equivalence, which relates every value to every value (note that All is capitalised, unlike empty; though I don't use it much in newer texts).
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.
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:
r&on;s relates x to ziff
r relates x to some y which s relates to z
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
.)
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|)}.
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.
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 ?
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:
in which left and right must both denotate relations and their respective end-relation constraints (as above) are implied; mapping, monic or iso – depending which was used – further constrain the type, in a manner which depends on these end-constraints, if present. To determine whether a given relation r is of the relevant type: if left is omitted, take Z = (:x←x:r), otherwise take Z = (:left|); if right is omitted, take A = (r:x←x:), otherwise take A = (|right:); then, variously, use of
asserts that (Z:r:) relates h to a,
i to b and A relates a to b
implies Z relates h to i
,
asserts that (:r:A) relates h to a, i
to b and Z relates h to i
implies A relates a to b
,
asserts both of these conditions.
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.
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 :).
Written by Eddy.