[Inquiry] Re: Reductions Among Relations

[Jon Awbrey]

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

RAR.  Note 7

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

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