Re: Relations And Their Divisitudes

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

RATD.  Note 21

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

Finally, I will make another try at explaining the relationship
between compositional and projective reducibility, and why the
latter is a weaker form of reduction, that is, in those cases
when the reduction is possible, on account of its exploiting
the 3-adic relation & : B x B -> B that is involved in the
use of logical conjunction to synthesize a 2-projectively
reducible 3-adic relation under analysis from its 2-adic
projections, or in the geometric idiom that is commonly
used, from its 2-adic "faces".

Compositional Analysis of Relations

The first order of business under this heading is straightforward enough:
to define what is standardly described as the "composition of relations".
For the time being I limit the discussion to 2-adic and 3-adic relations.

A notion of relational composition is to be defined that generalizes the
usual notion of functional composition.  The "composition of functions"
is that by which -- composing functions "on the right", as they say --
f : X -> Y and g : Y -> Z yield the "composite function" fg : X -> Z.

Accordingly, the "composition" of dyadic relations is that by which --
composing them here by convention in the same left to right fashion --
P c X x Y and Q c Y x Z yield the "composite relation" PQ c X x Z.

There is a neat way of defining relational composition, one that
not only manifests its relationship to the projection operations
that go with any cartesian product space, but also suggests some
natural directions for generalizing relational composition beyond
the limits of the 2-adic case, and even beyond relations that have
any fixed arity, that is, to the general case of formal languages.
I often call this definition "Tarski's Trick", though it probably
goes back further than that.  This is what I will take up next.

Jon Awbrey

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