ONT Re: Reductions Among Relations
RAR. Note 7
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.
| Remark on the Ancestry, the Application, and
| The Anticipated Broadening of these Concepts.
| This is basically the same operation that C.S. Peirce described as
| "relative multiplication", except for the technical distinction that
| he worked primarily with so-called "relative terms", like "lover of",
| "sign of the object ~~~ to", and "warrantor of the fact that ~~~ to",
| rather than with the kinds of extensional and intensional relations
| to which the majority of us are probably more accustomed to use.
| It is with regard to this special notion of "composition", and it alone,
| that I plan to discuss the inverse notion of "decomposition". I try to
| respect other people's "reserved words" as much as I can, even if I can
| only go so far as to take them at their words and their own definitions
| of them in forming my interpretation of what they are apparently saying.
| Therefore, if I want to speak about other ways of building up relations
| from other relations and different ways of breaking down relations into
| other relations, then I will try to think up other names for these ways,
| or revert to a generic usage of terms like "analysis" and "combination".
| When a generalized definition of "relational composition" has been given,
| and its specialization to 2-adic relations is duly noted, then one will
| be able to notice that it is simply an aspect of this definition that
| the composition of two 2-adic relations yields nothing more than yet
| another 2-adic relation. This will, I hope, in more than one sense
| of the word, bring "closure" to this issue, of what can be reduced
| to compositions of 2-adic relations, to wit, just 2-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.