SUO: Re: Relations And Their Divisitudes
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
RATD. Note 25
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
Compositional Analysis of Relations (cont.)
We continue with the trick already in progress,
whereby Ulam reports Tarski as defining the
relational composition P o Q of two 2-adic
relations P, Q c X x X in this way:
Definition. P o Q = p_13 (P x X |^| X x Q).
To get this drift of this definition, one needs
to understand that it's written within a school
of thought that holds that all 2-adic relations
are, "without loss of generality", covered well
enough, "for all practical purposes", under the
aegis of subsets of a suitable cartesian square,
and thus of the form L c X x X. So, if one has
started out with a 2-adic relation of the shape
L c U x V, one merely lets X = U |_| V, trading
in the initial L for a new L c X x X as need be.
The projection p_13 : X^3 -> X^2 is just the projection
of the cartesian cube X^3 = X x X x X on the space that
takes the shape of the cartesian square X^2 = X x X that
is spanned by the first and the third relational domains,
but since these domains now have the same names and the
same contents it is necessary to distinguish them by
numbering their relational places.
Finally, the notation of the cartesian product sign "x"
is abused, or extended, depending on your point of view,
to signify a couple of other "products" with respect to
a 2-adic relation L c X x X and a subset W c X, like so:
Definition. L x W = {<x, y, z> in X^3 : <x, y> in L and z in W}.
Definition. W x L = {<x, y, z> in X^3 : x in W and <y, z> in L}.
Applying these definitions to the case of P, Q c X x X, the 2-adic relations
whose relational composition P o Q c X x X is about to be defined, one finds:
P x X = {<x, y, z> in X^3 : <x, y> in P and z in X},
X x Q = {<x, y, z> in X^3 : x in X and <y, z> in Q}.
I hope it's clear that these are just the appropriate
special cases of the tacit extensions already defined:
P x X = te_12.3 (P),
X x Q = te_23.1 (Q).
In summary, then, the expression:
p_13 (P x X |^| X x Q)
is equivalent to the expression:
p_13 (te_12.3 (P) |^| te_23.1 (Q))
and this form is generalized -- although, relative to one's school of thought,
perhaps inessentially so -- by the form from my school that I give as follows:
Definition. P o Q = Proj_XZ (TE_XY.Z (P) |^| TE_YZ.X (Q)).
Jon Awbrey
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o