[Arisbe] Re: Inquiry Into Irreducibility
Jon Awbrey
arisbe@stderr.org
Wed, 22 Aug 2001 17:00:00 -0400
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
Howard,
Here is another installment on "Reductions Among Relations":
¤~~~~~~~~~¤~~~~~~~~~¤~ARCHIVE~¤~~~~~~~~~¤~~~~~~~~~¤
Subj: Reductions Among Relations
Date: Mon, 14 May 2001 15:30:25 -0400
From: Jon Awbrey <jawbrey@oakland.edu>
To: Arisbe <arisbe@stderr.org>,
SemioCom <semiocom@listbot.com>,
Standardize Unto Others <standard-upper-ontology@ieee.org>
CC: Matthew West <Matthew.R.West@is.shell.com>
I thought that it might be a beneficial exercise for me to
work out an explicit definition of "relational composition",
partly as an object example of how such a thing ought to look.
There are, of course, several different styles of definitional
discipline that one might choose from, but I will personally
tend to go for those forms that are most readily converted
into a computational program for recognizing an instance
of the thing defined, that is, what ought to fall under
the concept, term, or predicate that is being defined.
I was under the impression that I had already done this work,
but it now appears that I must have only dreamed it, for the
closest thing that I can find to any sort of real definition
of "relational composition" or "relative multiplication" in
the SUO Archive is an example of its use that remains a bit
tangled up in the treatment of a case of influenza that we
were all puzzling over a while back. Namely, about here:
http://suo.ieee.org/ontology/msg01716.html
http://suo.ieee.org/ontology/msg01722.html
So what I will do is extract this example
and use it to give a formal definition of
relational composition. I recognize that
this is a species of (de)composition that
you say you have no sue for, but it might
just inspire you to develop the analogous
definition of the type of join you desire.
I will begin at the beginning, roughly with the way that C.S. Peirce
intially defined and outlined his notion of "relative multiplication",
though I will be doing this from memory -- so be gentle, I will check
with the original papers (circa 1870) later on. An interesting thing
from my perspective, and what first drew me back to this stage in the
history of logic from the problems that I was investigating years ago,
is the way that Peirce had already, at the very beginning, integrated
the aspects of the logic of relations that we usually problematize as
the "extensional" versus the "intensional". Some of that integration
is dimly apparent even in these simple cases, but the remainder of it
would be well worth detailed and extended study.
Here are some excerpts from the "Influenza" example:
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
Virally Important Topics: The Anxiety Of Influenza
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
Part 1. Graph-Theoretical Picture of Composition
There is this 3-adic transaction among
three relational domains. Let us say:
"Transmitters", "Vectors", "Receivers",
and let us symbolize: C c T x V x R.
In order to prove the proposition, for instance, as in a court of law,
that "John J gave-the-flu-to Mary M", it is necessary but by no means
enough to convince an arbiter that an infectious colony or a virulent
sample of particular micro-organisms of the genus known as "influenza"
was transported from John J (SSN 1 TBN) to Mary M (SSN 2 TBN) on some
well-specified occasion in question.
In other words, the "evidence" for the 2-adic relation that bears
the form and the description F c T x R : "-- gave-the-flu-to --",
is found solely within the 3-adic relation of "communication" C.
Let us assume that this long chain of causal and physical "influences"
can be more conveniently summarized, for our present purposes, in the
form of a 3-adic relation that connects a transmitter t, a "vector" v,
and a receiver r. Thus a bona fide incident or a genuine instance of
the "communication relation" C c TxVxR will be "minimally adequately",
as they say in epidemiology, charted in a datum of the form <t, v, r>.
What is the character of the relationship between
the 3-adic relation of "communication" C c TxVxR
and the 2-adic relation "-- gave-the-flu-to --"?
This particular relation among relations --
you may be about to read my mention, but
will not if I can help it find me to use
the term "meta-relation" for this notion --
is broadly nomenclated as a "projection",
with type here being Proj : TxVxR -> TxR.
Our use of it in this presenting case is
an example of how we transit from caring
about the "detail of the evidence" (DOTE)
to desiring only a brief sum of the fact.
For now, let us stipulate that we have the following
sample of data about the 3-adic relation C c TxVxR :
{..., <John J, Agent A, Mary M>, ...}.
In other words, we are fixing on a single element:
<John J, Agent A, Mary M> in C c TxVxR.
Let us now contemplate the generalization of ordinary functional composition
to 2-adic relations, called, not too surprisingly, "relational composition",
and roughly information-equivalent to Peirce's "relative multiplication".
I will employ the data of our present case to illustrate two different
styles of picture that we can use to help us reason out the operation
of this particular form of relational composition.
First I show one of my favorite genres of pictures for 2-adic relations,
availing itself of the species of graphs known as "bipartite graphs",
or "bigraphs", for short.
Let an instance of the 2-adic relation E c TxV
informally defined by {<t, v> : t exhales v},
be expressed in the form "t exhales v".
Let an instance of the 2-adic relation I c VxR
informally defined by {<v, r> : v infects r},
be expressed in the form "v infects r".
Just for concreteness in the example, let us imagine that:
1. John J exhales three viral particles numbered 1, 3, 5.
2. Mary M inhales three viral particles numbered 3, 5, 7,
each of which infects her with influenza.
The 2-adic relation E that exists in this situation is
imaged by the bigraph on the T and the V columns below.
The 2-adic relation I that exists in this situation is
imaged by the bigraph on the V and the R columns below.
E I
T---->V---->R
o 1 o
/
/
o / 2 o
/
/
J o-----3 o
\ \
\ \
o \ 4 \ o
\ \
\ \
o 5-----o M
/
/
o 6 / o
/
/
o 7 o
Let us now use this picture to illustrate for ourselves,
by way of concrete examples, many of the distinct types
of set-theoretic constructs that would arise in general
when contemplating any similar relational configuration.
First of all, there is in fact a particular 3-adic relation Q
that is determined by the data of these two 2-adic relations.
It cannot be what we are calling the "relational composition"
or the "relative product", of course, since that is defined --
forgive me if I must for this moment be emphatic -- DEFINED
to be yet another 2-adic relation. Just about every writer
that I have read who has discovered this construction has
appeared to come up with a different name for it, and I
have already forgotten the one that I was using last,
so let me just define it and we will name it later:
What we want is easy enough to see in visible form,
as far as the present case goes, if we look at the
composite sketch already given. There the mystery
3-adic relation has exactly the 3-tuples <t, v, r>
that are found on the marked paths of this diagram.
That much insight should provide enough of a hint
to find a duly officious set-theoretic definition:
Q = {<t, v, r> : <t, v> in E and <v, r> in I}.
There is yet another, very convenient, way to define this,
the recipe of which construction proceeds by these stages:
1. For 2-adic relation G c TxV, define GxR,
named the "extension" of G to TxVxR, as:
{<t, v, r> in TxVxR : <t, v> in G}.
2. For 2-adic relation H c VxR, define TxH,
named the "extension" of H to TxVxR, as:
{<t, v, r> in TxVxR : <v, r> in H}.
In effect, these extensions just keep the constraint
of the 2-adic relation "in its places" while letting
the other elements roam freely.
Given the ingredients of these two extensions,
at the elemental level enjoying the two types:
TxV -> TxVxR and VxR -> TxVxR, respectively,
we can define the 3-adic Q as an intersection:
Q(G, H) = GxR |^| TxH
One way to comprehend what this construction means
is to recognize that it is the largest relation on
TxVxR that is congruent with having its projection
on TxV be G and its projection on VxR be H.
Thus, the particular Q in our present example is:
Q(E, I) = ExR |^| TxI
This is the relation on TxVxR, to us, embodying an assumption
about the "evidence" that underlies the case, which restricts
itself to the information given, imposing no extra constraint.
And finally -- though it does amount to something like the "scenic tour",
it will turn out to be useful that we did things in this roundabout way --
we define the relational composition of the 2-adic relations G and H as:
G o H = Proj<T, R> Q(G, H) = Proj<T, R> (GxR |^| TxH)
| Reference:
|
| Although it no doubt goes way back, I am used to thinking
| of this formula as "Tarski's Trick", because I first took
| notice of it in a book by Ulam, who made this attribution.
|
| Ulam & Bednarek,
|"On the Theory of Relational Structures
| And Schemata for Parallel Computation",
| Original report dated May 1977, in:
| Ulam, 'Analogies Between Analogies',
| University of California Press, Berkely, CA, 1990.
Applying this general formula to our immediate situation:
E o I = Proj<T, R> Q(E, I) = Proj<T, R> (ExR |^| TxI)
We arrive at this picture of the composition E o I c TxR:
EoI
T---->R
o o
o o
J o o
\
\
o \ o
\
\
o o M
o o
o o
In summation, E o I = {<John J, Mary M>}.
By the way, you may have noticed that I am using here
what strikes me as a more natural order for composing
2-adic relations, but the opposite of what is usually
employed for functions. In the present ordering, one
can read the appearances of the relational domains in
what seems like a much more straightforward way, just
as they are invoked by the series of relation symbols.
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
Part 2. Matrix-Theoretical Picture of Composition
Let us declare a "logical basis" -- and leave it
as an exercise for the reader to improvise a fit
definition of what is, and what ought to be that --
but anyway a collection of elements of this form:
"Basic Entia" K = T |_| V |_| R
"Transmissia" T = {t1, t2, t3, t4, t5, t6, t7}
"Viral Entia" V = {v1, v2, v3, v4, v5, v6, v7}
"Receptacula" R = {r1, r2, r3, r4, r5, r6, r7}
Just by way of orientation to the way that we speak "way out here",
t3 = John.
r5 = Mary.
So far, so good, but here we have come to one of those junctures
where personal tastes are noticed to be notoriously divergent in
matters of notation, and so at this point I will simply describe
a few of the most popular options:
1. One may lump all of these elements together and work
with a cubic array that has dimensions 21 x 21 x 21,
taking its projections into square matrices 21 x 21.
2. One may consider the very like possibilty, here only,
that the T's and the R's are abstractly the same set,
and reduce the representation in a corresponding way.
3. One may treat the relational domains T, V, R as three
distinct sets, start with a 3-adic relation Q c TxVxR
represented as a cubic array of dimensions 7 x 7 x 7,
taking its projections into square matrices of 7 x 7.
Option 3 seems easier for us here,
just as a way of conserving space.
The extensions of the 2-adic relations E and I
are the following collections of ordered pairs:
E = {<t3, v1>, <t3, v3>, <t3, v5>}
I = {<v3, r5>, <v5, r5>, <v7, r5>}
Peirce represented 2-adic relations in this form:
E = t3:v1 +, t3:v3 +, t3:v5
I = v3:r5 +, v5:r5 +, v7:r5
It is very often convenient, though by no means obligatory,
to arrange these quasi-algebraic terms in forms like these:
T x V =
[
| t1:v1, t1:v2, t1:v3, t1:v4, t1:v5, t1:v6, t1:v7,
| t2:v1, t2:v2, t2:v3, t2:v4, t2:v5, t2:v6, t2:v7,
| t3:v1, t3:v2, t3:v3, t3:v4, t3:v5, t3:v6, t3:v7,
| t4:v1, t4:v2, t4:v3, t4:v4, t4:v5, t4:v6, t4:v7,
| t5:v1, t5:v2, t5:v3, t5:v4, t5:v5, t5:v6, t5:v7,
| t6:v1, t6:v2, t6:v3, t6:v4, t6:v5, t6:v6, t6:v7,
| t7:v1, t7:v2, t7:v3, t7:v4, t7:v5, t7:v6, t7:v7,
]
V x R =
[
| v1:r1, v1:r2, v1:r3, v1:r4, v1:r5, v1:r6, v1:r7,
| v2:r1, v2:r2, v2:r3, v2:r4, v2:r5, v2:r6, v2:r7,
| v3:r1, v3:r2, v3:r3, v3:r4, v3:r5, v3:r6, v3:r7,
| v4:r1, v4:r2, v4:r3, v4:r4, v4:r5, v4:r6, v4:r7,
| v5:r1, v5:r2, v5:r3, v5:r4, v5:r5, v5:r6, v5:r7,
| v6:r1, v6:r2, v6:r3, v6:r4, v6:r5, v6:r6, v6:r7,
| v7:r1, v7:r2, v7:r3, v7:r4, v7:r5, v7:r6, v7:r7,
]
Now, taking these generic motifs as scenic -- or, at least, schematic --
backdrops, one can permit the particular characters of one's favorite
2-adic relations to represent themselves and to play out their action
on this stage, by attaching affirming or nullifying "coefficients" to
the appropriate places of the thus-arrayed company of possible actors.
E =
[
| 0 t1:v1, 0 t1:v2, 0 t1:v3, 0 t1:v4, 0 t1:v5, 0 t1:v6, 0 t1:v7,
| 0 t2:v1, 0 t2:v2, 0 t2:v3, 0 t2:v4, 0 t2:v5, 0 t2:v6, 0 t2:v7,
| 1 t3:v1, 0 t3:v2, 1 t3:v3, 0 t3:v4, 1 t3:v5, 0 t3:v6, 0 t3:v7,
| 0 t4:v1, 0 t4:v2, 0 t4:v3, 0 t4:v4, 0 t4:v5, 0 t4:v6, 0 t4:v7,
| 0 t5:v1, 0 t5:v2, 0 t5:v3, 0 t5:v4, 0 t5:v5, 0 t5:v6, 0 t5:v7,
| 0 t6:v1, 0 t6:v2, 0 t6:v3, 0 t6:v4, 0 t6:v5, 0 t6:v6, 0 t6:v7,
| 0 t7:v1, 0 t7:v2, 0 t7:v3, 0 t7:v4, 0 t7:v5, 0 t7:v6, 0 t7:v7,
]
I =
[
| 0 v1:r1, 0 v1:r2, 0 v1:r3, 0 v1:r4, 0 v1:r5, 0 v1:r6, 0 v1:r7,
| 0 v2:r1, 0 v2:r2, 0 v2:r3, 0 v2:r4, 0 v2:r5, 0 v2:r6, 0 v2:r7,
| 0 v3:r1, 0 v3:r2, 0 v3:r3, 0 v3:r4, 1 v3:r5, 0 v3:r6, 0 v3:r7,
| 0 v4:r1, 0 v4:r2, 0 v4:r3, 0 v4:r4, 0 v4:r5, 0 v4:r6, 0 v4:r7,
| 0 v5:r1, 0 v5:r2, 0 v5:r3, 0 v5:r4, 1 v5:r5, 0 v5:r6, 0 v5:r7,
| 0 v6:r1, 0 v6:r2, 0 v6:r3, 0 v6:r4, 0 v6:r5, 0 v6:r6, 0 v6:r7,
| 0 v7:r1, 0 v7:r2, 0 v7:r3, 0 v7:r4, 1 v7:r5, 0 v7:r6, 0 v7:r7,
]
And then there are times when it is not so convenient!
At any rate, it is then conceivable to push the level
of abstraction in our so-arrayed representations even
one step further, and so long as we keep in mind what
the now-suppressed row-indices and column-indices are
supposed to signify, logically speaking, in the first
place, then we can push them even deeper into the dim
and tacit background of the overriding interpretation.
E =
[
| 0, 0, 0, 0, 0, 0, 0,
| 0, 0, 0, 0, 0, 0, 0,
| 1, 0, 1, 0, 1, 0, 0,
| 0, 0, 0, 0, 0, 0, 0,
| 0, 0, 0, 0, 0, 0, 0,
| 0, 0, 0, 0, 0, 0, 0,
| 0, 0, 0, 0, 0, 0, 0,
]
I =
[
| 0, 0, 0, 0, 0, 0, 0,
| 0, 0, 0, 0, 0, 0, 0,
| 0, 0, 0, 0, 1, 0, 0,
| 0, 0, 0, 0, 0, 0, 0,
| 0, 0, 0, 0, 1, 0, 0,
| 0, 0, 0, 0, 0, 0, 0,
| 0, 0, 0, 0, 1, 0, 0,
]
When all of this is said and done, that is to say,
when all of this is said and done the fitting way,
then one can represent relative multiplication or
relational composition in terms of an appropriate
quasi-algebraic "multiplication" operation on the
rectangular matrices that represent the relations.
The logical operation of the relative product has
to be qualified as "quasi-algebraic" just to help
us keep in mind the fact that it is not precisely
the one that algebraically-minded folks would put
on the same brands of {0, 1}-coefficient matrices.
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
Onward ...
Let me start by going back to the way that Peirce
intially represented 2-adic relations in terms of
2-tuples that have an algebra defined on them:
| Peirce represented 2-adic relations in this form:
|
| E = t3:v1 +, t3:v3 +, t3:v5
|
| I = v3:r5 +, v5:r5 +, v7:r5
The composite symbol "+," will have to serve for
the variety of different symbols that Peirce and
his variety of different typographers have taken
to using at different points in time to signify
the logical operation of inclusive disjunction.
Especially in this matrix algebra setting, the
ordinary plus sign "+" is a strictly reserved
keysign for the additive operation of a field.
Given a basis $X$ = {x<1>, ..., x<n>}, where each element
stands in for an entity, an object, a particular, a thing,
or whatever in the universe of discourse, Peirce employed
a "colonial notation" of the form "s<1>: ... :s<k>", with
s<j> in $X$ for j = 1 to k, to represent ordered k-tuples.
Each type of relational operation that one defines over
this initial basis and over this k-tuply extended basis
corresponds to a way of combining f-tuples and g-tuples
to arrive at specified h-tuples for appropriate choices
of positive integers f, g, h.
In the case of the ordinary relational composition of
two 2-adic relations to get a product 2-adic relation,
the quasi-algebraic rule is this:
| (u:v)(x:y) = (u:y) if v = x.
| (u:v)(x:y) = 0 otherwise.
For example, consider the problem to compute the
relative product EI = EoI of the pair of 2-adic
relations, E and I, that are given as follows:
| E = t3:v1 +, t3:v3 +, t3:v5
| I = v3:r5 +, v5:r5 +, v7:r5
One simply forms the indicated product:
| EI = (t3:v1 +, t3:v3 +, t3:v5)(v3:r5 +, v5:r5 +, v7:r5)
and then proceeds to multiply the whole thing out,
using a composition rule of the form given above
to reduce complex terms whenever possible.
Like so:
| EI = (t3:v1 +, t3:v3 +, t3:v5)(v3:r5 +, v5:r5 +, v7:r5)
|
| = (t3:v1)(v3:r5) +, (t3:v1)(v5:r5) +, (t3:v1)(v7:r5) +,
| (t3:v3)(v3:r5) +, (t3:v3)(v5:r5) +, (t3:v3)(v7:r5) +,
| (t3:v5)(v3:r5) +, (t3:v5)(v5:r5) +, (t3:v5)(v7:r5)
|
| = 0 +, 0 +, 0 +,
| t3:r5 +, 0 +, 0 +,
| 0 +, t3:r5 +, 0
|
| = t3:r5
|
| = John:Mary
In conclusion, we compute that John gave the flu to Mary.
Okay, that is an illustration of yet another way to compute
the relative product, and it is still not the kind of exact
definition that I had in mind when I started this note, but
I will need to rest a while and get back to that task later.
I now retreat to a quiet nook to read some poetry to myself.
I leave you to your own devices,
Jon Awbrey
¤~~~~~~~~~¤~~~~~~~~~¤~EVIHCRA~¤~~~~~~~~~¤~~~~~~~~~¤
Reductions Among Relations
http://suo.ieee.org/ontology/msg01727.html
http://suo.ieee.org/ontology/msg01738.html
http://suo.ieee.org/ontology/msg01747.html
http://suo.ieee.org/ontology/msg01766.html
http://suo.ieee.org/ontology/msg01818.html
http://suo.ieee.org/ontology/msg01821.html
http://suo.ieee.org/ontology/msg02167.html
http://suo.ieee.org/ontology/msg02475.html
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
Detached Ideas On Virally Important Topics
http://suo.ieee.org/ontology/msg01716.html
http://suo.ieee.org/ontology/msg01722.html
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤