[ notation | bestiary | mappings ]
This page uses an old notation (see link above) and is in need of maintenance.
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.]
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
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:
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.
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
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.
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).
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.
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.
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.
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.
I take relations, as discussed here, as the first
among the bundle of fundamental notions on which
I aim to build up mathematical tools for physics. As alluded to
above, mappings
and collections come next
, paving the
way for the Natural Numbers (aka finite
ordinals or non-negative integers) as a first example for the general discussion
of addition and multiplication, which lead on to the general notion
of scalars and linearity. In parallel with this I need
to develop the subtle properties of sub-relation
which enable discussion of continuity, smoothness and integration (or
measure).
A relation may be described as an arrow
land, in which context I build up categorical
notions which discuss
abstract compositions
, of which the composition of relations, above, is a
concrete example.
[ denotations | bestiary | mappings ]
The following links are targets of incoming links here forwarded to where their discussion has gone.
Valid CSS ? Valid HTML ? Written by Eddy.