ONT Re: Inquiry Into Irreducibility
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
Howard,
Here are two pieces of additional discussion on the "projective reducibility" of
relations, from a long-running dialogue that was carried on in parallel with the
more monological material that I gave on the "Reductions Among Relations" thread.
¤~~~~~~~~~¤~~~~~~~~~¤~ARCHIVE~¤~~~~~~~~~¤~~~~~~~~~¤
Subj: Expostulation
Date: Sun, 15 Apr 2001 00:34:17 -0400
From: Jon Awbrey <jawbrey@oakland.edu>
To: Matthew West <Matthew.R.West@is.shell.com>,
Standard Upper Ontology <standard-upper-ontology@ieee.org>
To summarize what is on the RAR thread:
1. If the genre of analysis/synthesis is relational de/composition,
then no 3-adic relations are reducible to 2-adic relations.
So if you seek examples under this heading, all 3-adics
are irreducible to 2-adics under relational composition.
2. If the genre of analysis/synthesis is projective de/construction,
then some 3-adics are reducible to 2-adics and some are not.
a. Two examples of projectively reducible 3-adic relations
are the ones from the "Story of A and B".
b. Two examples of projectively irreducible 3-adic relations
are the relations L^0 and L^1, that are discussed in this
excerpt from the RAR thread:
Projectively Irreducible Triadic Relations, or
Triadic Relations Irreducible Over Projections:
Consider the triadic relations L^0 and L^1
that are specified in the following set-up:
| B = {0, 1}, with the "+" signifying addition mod 2,
| analogous to the "exclusive-or" operation in logic.
|
| B^k = {<x<1>, ..., x<k>> : x<j> in B for j = 1 to k}.
In what follows, the space XxYxZ is isomorphic to BxBxB = B^3.
For lack of a good isomorphism symbol, I will often resort to
writing things like "XxYxZ iso BxBxB" or even "XxYxZ = B^3".
| Relation L^0
|
| L^0 = {<x, y, z> in B^3 : x + y + z = 0}.
|
| L^0 has the following four triples
| of the form <x, y, z> in B^3:
|
| <0, 0, 0>
| <0, 1, 1>
| <1, 0, 1>
| <1, 1, 0>
| Relation L^1
|
| L^1 = {<x, y, z> in B^3 : x + y + z = 1}.
|
| L^1 has the following four triples
| of the form <x, y, z> in B^3:
|
| <0, 0, 1>
| <0, 1, 0>
| <1, 0, 0>
| <1, 1, 1>
Those are the relations,
here are the projections:
Taking the dyadic projections of L^0
we obtain the following set of data:
| (L^0)<XY> has these four triples
| of the form <x, y> in XxY:
|
| <0, 0>
| <0, 1>
| <1, 0>
| <1, 1>
| (L^0)<XZ> has these four triples
| of the form <x, z> in XxZ:
|
| <0, 0>
| <0, 1>
| <1, 1>
| <1, 0>
| (L^0)<YZ> has these four triples
| of the form <y, z> in YxZ:
|
| <0, 0>
| <1, 1>
| <0, 1>
| <1, 0>
Taking the dyadic projections of L^1
we obtain the following set of data:
| (L^1)<XY> has these four triples
| of the form <x, y> in XxY:
|
| <0, 0>
| <0, 1>
| <1, 0>
| <1, 1>
| (L^1)<XZ> has these four triples
| of the form <x, z> in XxZ:
|
| <0, 1>
| <0, 0>
| <1, 0>
| <1, 1>
| (L^1)<YZ> has these four triples
| of the form <y, z> in YxZ:
|
| <0, 1>
| <1, 0>
| <0, 0>
| <1, 1>
Now, for ease of verifying the data, I have written
these sets of pairs in the order that they fell out
on being projected from the given triadic relations.
But, of course, as sets, their order is irrelevant,
and it is simply a matter of a tedious check to
see that both L^0 and L^1 have exactly the same
projections on each of the corresponding planes.
To summarize:
The relations L^0, L^1 sub B^3 are defined by the following equations,
with algebraic operations taking place as in the "Galois Field" GF(2),
that is, with 1 + 1 = 0.
1. The triple <x, y, z> in B^3 belongs to L^0 iff x + y + z = 0.
L^0 is the set of even-parity bit-vectors, with x + y = z.
2. The triple <x, y, z> in B^3 belongs to L^1 iff x + y + z = 1.
L^1 is the set of odd-parity bit-vectors, with x + y = z + 1.
The corresponding projections of L^0 and L^1 are identical.
In fact, all six projections, taken at the level of logical
abstraction, constitute precisely the same dyadic relation,
isomorphic to the whole of BxB and expressible by means of
the universal constant proposition 1 : BxB -> B. In sum:
(L^0)<XY> = (L^1)<XY> = 1<XY> = BxB = B^2,
(L^0)<XZ> = (L^1)<XZ> = 1<XZ> = BxB = B^2,
(L^0)<YZ> = (L^1)<YZ> = 1<YZ> = BxB = B^2.
Therefore, L^0 and L^1 constitute examples of
"projectively irreducible triadic relations",
"triadic relations irreducible on projections".
http://suo.ieee.org/ontology/msg02169.html
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
Subj: Expostulation
Date: Fri, 20 Apr 2001 02:22:14 -0400
From: Jon Awbrey <jawbrey@oakland.edu>
To: Arisbe <arisbe@stderr.org>,
SemioCom <semiocom@listbot.com>,
Stand Up Ontology <standard-upper-ontology@ieee.org>
CC: Matthew West <Matthew.R.West@is.shell.com>
Matthew,
I am going to put some more time in on the concrete examples,
and clear away everything that's been said a number of times,
leaving only the lines of inquiry that still await an answer.
Matthew West wrote (MW):
Jon Awbrey wrote (JA):
MW: So I'm afraid that is not an argument that will
convince me on its own. If you wish to do that
you will have to present a specific example of
where the information in some triadic relation
cannot be transformed into some set of binary
relations. If you provide the triadic relation,
I will provide the binary relations from which
the triadic relation can be constructed (or not
and admit you are right).
JA: Just to refresh your memory,
here are L^0 and L^1 once again:
---------------------------------------------------
|
| Relation L^0
|
| L^0 = {<x, y, z> in B^3 : x + y + z = 0}.
|
| L^0 has the following four triples
| of the form <x, y, z> in B^3:
|
| <0, 0, 0>
| <0, 1, 1>
| <1, 0, 1>
| <1, 1, 0>
|
---------------------------------------------------
|
| Relation L^1
|
| L^1 = {<x, y, z> in B^3 : x + y + z = 1}.
|
| L^1 has the following four triples
| of the form <x, y, z> in B^3:
|
| <0, 0, 1>
| <0, 1, 0>
| <1, 0, 0>
| <1, 1, 1>
|
---------------------------------------------------
|
| Most recent exposition of L^0 & L^1 at:
|
| http://suo.ieee.org/ontology/msg02167.html
|
---------------------------------------------------
JA: Perhaps the difficulty in getting started on this task lies
in knowing exactly what it would mean that "the information
in some triadic relation [can] be transformed into some set
of binary relations", or even just what, in operational and
practical terms, may be incumbent on a person who is called
for to "provide the binary relations from which the triadic
relation can be constructed". My sense of it tells me that
the word "information" plays a critical role in the problem,
but I will need to think a bit more about how to tackle the
elicitation and the explication of its bearing on the issue.
JA: Let me tell you where I think that you and I stand at present.
I believe that we have agreed on the ground rules that nothing of
any rational sense will come of arguing about any puported form of
"analysis", "decomposition", "discombobulation", "reconstruction",
"reduction", "transliteration", "transmogrification", or whatever,
unless we have clearly defined the particular species of relation
that we are talking about in a case at issue. Now, for my own part,
I regard the argument as being effectively over right at this point,
since I never knew a "form of analysis" (FOA) that pretended to be
anything other than a relationship among one thing, the analysand,
and at least two other things, the analytic components. One plus
at least two implies at least three, and so the very idea of a FOA
has us neck deep already in a 3-adic relation.
MW: But as usual you skip from three things to necessary triadicity.
In fact the only thing that is required for 3 things (or any
number of things for that matter) to be related is that in some
network of relations there is a path that links them together.
JA: This is one way that we can say, if we speak loosely enough,
that "three things are related". People sometimes describe
this by saying that they are "pairwise related" in such and
such a way that chosen triples are connected in 2-adic pairs.
It is what is what we might call some kind of "discombobulatable
3-adic relation", say, "conjunctively reducible", which is the
same thing, if I remember correctly, or related to, at least,
the "projectively reducible" 3-adic relation. Anyway, there
are many such special cases of relations, but their existence
does not affect the general truth that many 3-adic relations
are not of this kind. And, once again, the logical forms of
these very reductions involve 3-adic relations at every step
of the corresponding analyses.
JA: For example, contemplate the 3-adic relation that is expressed by
the rheme "--- is an ordered pair consisting of --- and then ---",
of which one instantiation is <<Jack, Jill>, Jack, Jill>, and which
one single instance might be diagrammed as follows:
| Jack
| o
| /
| <Jack, Jill> o---<|
| \
| o
| Jill
JA: Let us symbolize this 3-adic relation by writing statements
of the form "LP12 (q, x, y)", of which we have the example
where LP12 (<Jack, Jill>, Jack, Jill) is true.
JA: The 3-adic relation that is meant to be exemplified here,
of which <<Jack, Jill>, Jack, Jill> is but one exemplar,
is just the sort of thing that can be expressed in terms
of certain pairwise connections, say, as we might try to
suggest by means of the following scheme:
| Jack
| [LP1]--o
| / \
| <Jack, Jill> o [L12]
| \ /
| [LP2]--o
| Jill
JA: In this picture, the 2-adic relations LP1, LP2, and L12
are defined to capture forms of pairwise relations like:
LP1 (q, x) <=> x is the 1st component
in the ordered pair q.
LP2 (q, y) <=> y is the 2nd component
in the ordered pair q.
L12 (x, y) <=> x is the 1st component &
y is the 2nd component
in some ordered pair.
JA: Now, to justify the claim that the original 3-adic relation can be
defined or expressed in terms of these particular 2-adic relations,
it is necessary to write out the requisite definition, for example:
LP12 (q, x, y) <=> LP1 (q, x) and LP2 (q, y).
JA: This, I think, does it. So here is an example of a 3-adic relation
that is "definable in terms of" (DITO) 2-adic relations. This is
all well and good to say, but it can only be well and good to say
if one chooses one's words very carefully, as I have in this case.
There is no mention of a 3-adic relation being "decomposable" to
2-adic relations, for that would invoke the notion of relational
composition, on analogy to functional composition, in minds that
have been exposed to certain early and formative life experiences.
JA: I would like to interject a note of reservation at this juncture,
since the definition of LP12 that I gave above is not yet in the
form that I would consider the tip-top shape for perfect clarity.
The main thing that it lacks in its current shape is any sort of
careful circumscriptions of the so-called "domains of definition"
for the assorted relations that serve defined and defining roles.
Just as a thing to think about, you might well see reason to ask:
"What is the domain of definition for the variable q?" But I do
not want to get bogged down in all of that now, so let's move on.
Still, it helps to name these domains: so "Q", "X", "Y" will do.
JA: Also, while I'm at it, allow me to convert my temporary terminology
into what is more like the "standard-usage-onyms" where I come from.
As a start, notice that the 2-adic relations LP1 and LP2 are actually
functions from the domain of q to the domains of x and y, respectively.
In recognition of this fact, it is usual to give them functional names,
commonly something like the following reformulations of the definitions:
1. Proj<1> : XxY -> X such that Proj<1> : <x, y> ~> x.
2. Proj<2> : XxY -> Y such that Proj<2> : <x, y> ~> y.
JA: And yet, once again, this entire skirmish to mop-up the residual bits
of 2-adic structure that may be squeegeed out of the original 3-adic
relation is being waged only after the general issue has been conceded,
for we had to use the 3-adic relation associated with the truth-functional
connective "and" just to express the definition of LP12.
JA: Still, I do not believe that the example that I gave of L^0 and L^1
is definable or reducible over any 2-adics in even this sort of way.
At least, I gave a proof that they cannot be projectively reducible,
and I am yet waiting for you to come up with the promised analysis
along whatever lines that you might be able to devise.
JA: What we have just now established, a little ways above,
is that an ordered pair q is determined by this "data":
a couple of 2-adic relations, in particular, functions,
whose names are not of any great importance, but which
I am now calling the "projections" Proj<1> amd Proj<2>,
together with the values of q's projections in X and Y.
JA: Here is a sort of picture that can be useful in helping us
to remember what is essential in this kind of a relational
situation, beneath the vast bewildering array of notations:
| Q
| =
| X x Y
| o
| o o
| o o
| o o
| o o
| o o
| o q o
| x7 o / \ o y7
| x6 o / * y6
| x5 o / o y5
| x4 * o y4
| x3 o o y3
| x2 o y2
| X x1 y1 Y
|
| This picture indicates that Q = X x Y,
| that X = {x1, x2, x3, x4, x5, x6, x7},
| that Y = {y1, y2, y3, y4, y5, y6, y7},
| that q = <x3, y5>, or, in other words,
| that Proj<1>(q) = x3, Proj<2>(q) = y5.
JA: At this juncture, I would like to demonstrate a few amusing
diversions that can be found in this genre of illustrations.
JA: We have just illustrated the circumstance -- coincidence? I think not! --
that a deux-tuple is determined by the details of its projective pieces --
still, according to a sage bit of wisdom, if a deux-tuple did not exist
that was determined by the data of its projective parts, then it should
be necessary to invent one that was -- which is parably what this bible
of pan-categorics tells us about the genesis of every cartesian product:
JA: So what if we add another character, yclept "p", let us say,
to this little drama of relations that we have set out here?
| Q
| =
| X x Y
| o
| o o
| o o
| o o
| o o
| o o
| o p q o
| x7 o / \ / \ o y7
| x6 * . * y6
| x5 o / \ o y5
| x4 * * y4
| x3 o o y3
| x2 o y2
| X x1 y1 Y
|
| This picture indicates that Q = X x Y,
| that X = {x1, x2, x3, x4, x5, x6, x7},
| that Y = {y1, y2, y3, y4, y5, y6, y7},
| that p = <x5, y3>, or, in other words,
| that Proj<1>(p) = x5, Proj<2>(p) = y3,
| that q = <x3, y5>, or, in other words,
| that Proj<1>(q) = x3, Proj<2>(q) = y5.
JA: We are now looking at a non-trivial 2-adic relation,
that is, one that has more than one 2-tuple to its name.
Speaking of which, it has none yet, so let's give it the
moniker "M<35>", mnemonically, say, for "Move 3 <-> 5".
JA: Now, one of the interesting things that we can do with
the "coordinate projections" Proj<1> and Proj<2> is to
extend their definitions from single points or tuples
to entire relations, comprising many points or tuples.
JA: Definition. For the 2-adic relation L c X x Y, and Proj<j>, j = 1, 2,
the "projection of L on the j^th axis (or j^th domain)" is defined as:
Proj<j>(L) = {Proj<j>(e) : e in L}.
JA: Thus, in the present example:
1. Proj<1>(M<35>) = {Proj<1>(p), Proj<1>(q)} = {x3, x5} c X.
2. Proj<2>(M<35>) = {Proj<2>(p), Proj<2>(q)} = {y3, y5} c Y.
JA: Well, that was such fun that I'm tempted to try another one.
Let us then contemplate another non-trivial 2-adic relation,
oh, I don't know, just pulling a random one out of thin air:
| Q
| =
| X x Y
| o
| o o
| o o
| o o
| o r o
| o / \ o
| o / \ o
| x7 o / \ o y7
| x6 * s * y6
| x5 o / \ o y5
| x4 * * y4
| x3 o o y3
| x2 o y2
| X x1 y1 Y
|
| This picture indicates that Q = X x Y,
| that X = {x1, x2, x3, x4, x5, x6, x7},
| that Y = {y1, y2, y3, y4, y5, y6, y7},
| that r = <x5, y5>, or, in other words,
| that Proj<1>(r) = x5, Proj<2>(r) = y5,
| that s = <x3, y3>, or, in other words,
| that Proj<1>(s) = x3, Proj<2>(s) = y3.
JA: Let us dub this one as "L<35>", say, on the basis
of a likely graphical analogy, for "Loop 3 and 5".
JA: Computing the projections for this example:
1. Proj<1>(L<35>) = {Proj<1>(r), Proj<1>(s)} = {x3, x5} c X.
2. Proj<2>(L<35>) = {Proj<2>(r), Proj<2>(s)} = {y3, y5} c Y.
JA: Thus this renders it beyond the shadow of a doubt,
if it was not already evident from their mugshots,
that L<35> & M<35> have the very same projections.
JA: So, what have we learned from this state of affairs?
Just that, even though single tuples are determined
by their projection data, that relations themselves,
generally speaking, are not.
JA: I think that this is something to think about.
http://suo.ieee.org/ontology/msg02215.html
¤~~~~~~~~~¤~~~~~~~~~¤~EVIHCRA~¤~~~~~~~~~¤~~~~~~~~~¤