[Inquiry] Re: Reductions Among Relations

[Jon Awbrey]

o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o

RAR.  Note 11

o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o

3.  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  =  Proj_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.

Proj_13 is just the projection of the cartesian
cube X x X x X on the space of shape X x X that
is spanned by the first and the third domains,
but since they 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 P, Q c X x X, the two 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 is 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:

   Proj_13 (P x X |^| X x Q)

is the same thing as:

   Proj_13 (TE_12_3 (P) |^| TE_23_1 (Q))

which is generalized -- though, with respect 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