SUO: Reducibility Among Relations
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
I am going to string together a cleaned-up composite version of
an earlier thread on the topic of reducibility among relations --
viewed another way, on the extent to which it is possible to
construct relations between complex relations and simpler
relations. The aim here, once we get past questions of
what is reducible in what way and what not in no way,
is to develop concrete and fairly general methods
for analyzing the structures of those relations
that are indeed amenable to a useful analysis --
and here I probably ought to emphasize that
I am talking about the structure of each
relation in itself, at least, to the
extent that it presents itself in
extensional form, and not just
the syntax of this or that
relational expression.
By way of a lightly diverting overture, let's begin
with an examplar of a "degenerate triadic relation",
a particular version of the "between relation", but
let us make it as simple as we possibly can and not
attempt to analyze even that much of a case in full
or final detail, but leave something for the finale.
Let B = {0, 1}.
Let the relation named "Rise<2>"
such that Rise<2> c B^2 = B x B,
be exactly this set of 2-tuples:
| Rise<2> = {<0, 0>,
| <0, 1>,
| <1, 1>}
Let the relation named "Rise<3>"
such that Rise<3> c B^3 = BxBxB,
be exactly this set of 3-tuples:
| Rise<3> = {<0, 0, 0>,
| <0, 0, 1>,
| <0, 1, 1>,
| <1, 1, 1>}
Then Rise<3> is a "degenerate 3-adic relation"
because it can be expressed as the conjunction
of a couple of 2-adic relations, specifically:
Rise<3><x, y, z> iff [Rise<2><x, y> and Rise<2><y, z>].
But wait just a minute! You read me clearly to say already --
and I know that you believed me! -- that no 3-adic relation
can be decomposed into any 2-adic relations, so what in the
heck is going on!? Well, "decomposed" implies the converse
of "composition", which has to mean "relational composition"
in the present context, and this composition is a different
operation entirely from the "conjunction" that was employed
above, to express Rise<3> as a conjunction of two Rise<2>'s.
Okay, there is a lot more to say, even about such a simple example,
but I have a feeling that this much is just about enough for today.
Jon Awbrey
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤