ONT Re: Inquiry Into Irreducibility
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
Howard,
Here is an expurgated redaction of the sutra -- more like a mantra --
on "Reductions Among Relations" (RAR) with which I bemused the SUO
Warping Group last Fall and again this Spring. I reprised all the
main issues in the last two notes of the series, and so it will be
enough to recapitulate merely the upshot couplet here. Here's One:
¤~~~~~~~~~¤~~~~~~~~~¤~ARCHIVE~¤~~~~~~~~~¤~~~~~~~~~¤
Subj: Reductions Among Relations
Date: Sat, 14 Apr 2001 19:48:55 -0400
From: Jon Awbrey <jawbrey@oakland.edu>
To: Stand Up Ontology <standard-upper-ontology@ieee.org>
CC: Matthew West <Matthew.R.West@is.shell.com>
One of the things that makes the general problem of RAR seem
just a little bit ill-defined is that you would have to survey
all of the conceivable ways of "getting new relations from old"
just to say what you mean by "L is reducible to {L<j> : j in J}",
in other words, that if you had a set of "simpler" relations L<j>,
for indices j in some set J, that this data would somehow fix
the original relation L that you are seeking to analyze,
to determine, to specify, to synthesize, or whatever.
In my experience, however, most people will eventually settle on
either one of two different notions of reducibility as capturing
what they have in mind, namely:
1. Compositive Reduction
2. Projective Reduction
As it happens, there is an interesting relationship between these
two notions of reducibility, the implications of which I am still
in the middle of studying, so I will try to treat them in tandem.
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
I will start out with the notion of "projective reduction"
of relations, in part because it is easier and much more
intuitive (in the visual sense), but also because there
are a number of tools that we need for the other brand
of reduction that arise quite naturally as a part of
the projective setting.
Before we get into the operational machinery and the
vocational vocabulary of it all, let me just suggest
that you keep in mind the following sort of picture,
which pretty much says it all, in that reducing the
"motley of the ten thousand terms" (MOTTTT) sort of
style that the aptest genres and the fittest motifs
of representations are genreally found to exhibit.
Picture a k-adic relation L as a body
that resides in k-dimensional space X.
If the dimensions are X<1>, ..., X<k>,
then the "extension" of L, an object
that I will, for the whole time that
I am working this "extensional" vein,
regard as tantamount to the relation
itself, is a subset of the cartesian
product space X = X<1> x ... x X<k>.
If you pick out your favorite family F of domains
among these dimensions, say, X<F> = {X<j> : j in F},
then the "projection" of a point x in X on the subspace
that gets "generated" along these dimensions of X<F> can
be denoted by the notation "Proj<F><x>".
By extension, the projection of any relation L on that subspace
is denoted by "Proj<F><L>", or still more simply, by "Proj<F>L".
The question of "projective reduction" for k-adic relations
can be stated with moderate generality in the following way:
| Given a set of k-place relations in the same space X and
| a set of projections from X to the associated subspaces,
| do the projections afford sufficient data to tell the
| different relations apart?
Next time, in order to make this discussion more concrete,
I will focus on some examples of triadic relations. In fact,
to start within the bounds of no doubt familiar examples by now,
I will begin with the examples of sign relations that I used before.
http://suo.ieee.org/email/msg00729.html
http://suo.ieee.org/email/msg01224.html
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
Projective Reduction of Triadic Relations
We are ready to take up the question of whether
3-adic relations, in general, and in particular
cases, are "determined by", "reducible to", or
"reconstructible from" their 2-adic projections.
Suppose that L contained in XxYxZ is an arbitrary 3-adic relation,
and consider the three 2-adic relations that are gotten by taking
its projections, its "shadows", if you will, on each of the three
planes XY, XZ, YZ. Using the notation that I introduced before,
and compressing it just a bit or two in passing, one can write
these projections in each of the following ways, depending on
which turns out to be most convenient in a given context:
1. Proj<{X,Y}><L> = Proj<{1,2}><L> = Proj<XY>L = Proj<12>L = L<XY> = L<12>.
2. Proj<{X,Z}><L> = Proj<{1,3}><L> = Proj<XZ>L = Proj<13>L = L<XZ> = L<13>.
3. Proj<{Y,Z}><L> = Proj<{2,3}><L> = Proj<YZ>L = Proj<23>L = L<YZ> = L<23>.
If you picture the relation L as a body in the 3-space XYZ, then
the issue of whether L is "reducible to" or "reconstuctible from"
its 2-adic projections is just the question of whether these three
projections, "shadows", or "2-faces" determine the body L uniquely.
Stating the matter the other way around, L is "not reducible to"
or "not reconstructible from" its 2-dim projections if & only if
there are two distinct relations L and L' which have exactly the
same projections on exactly the same planes.
The next series of Tables illustrates the projection operations
by means of their actions on the sign relations L(A) and L(B)
that I introduced earlier on, in the "Sign Relations" thread.
Recall that we had the following set-up:
| L(A) and L(B) are "contained in" or "subsets of" OxSxI:
|
| O = {A, B},
|
| S = {"A", "B", "i", "u"},
|
| I = {"A", "B", "i", "u"}.
| L(A) has the following eight triples
| of the form <o, s, i> in OxSxI:
|
| <A, "A", "A">
| <A, "A", "i">
| <A, "i", "A">
| <A, "i", "i">
| <B, "B", "B">
| <B, "B", "u">
| <B, "u", "B">
| <B, "u", "u">
| L(B) has the following eight triples
| of the form <o, s, i> in OxSxI:
|
| <A, "A", "A">
| <A, "A", "u">
| <A, "u", "A">
| <A, "u", "u">
| <B, "B", "B">
| <B, "B", "i">
| <B, "i", "B">
| <B, "i", "i">
Taking the 2-adic projections of L(A)
we obtain the following set of data:
| L(A)<OS> has these four triples
| of the form <o, s> in OxS:
|
| <A, "A">
| <A, "i">
| <B, "B">
| <B, "u">
| L(A)<OI> has these four triples
| of the form <o, i> in OxI:
|
| <A, "A">
| <A, "i">
| <B, "B">
| <B, "u">
| L(A)<SI> has these eight triples
| of the form <s, i> in SxI:
|
| <"A", "A">
| <"A", "i">
| <"i", "A">
| <"i", "i">
| <"B", "B">
| <"B", "u">
| <"u", "B">
| <"u", "u">
Taking the dyadic projections of L(B)
we obtain the following set of data:
| L(B)<OS> has these four triples
| of the form <o, s> in OxS:
|
| <A, "A">
| <A, "u">
| <B, "B">
| <B, "i">
| L(B)<OI> has these four triples
| of the form <o, i> in OxI:
|
| <A, "A">
| <A, "u">
| <B, "B">
| <B, "i">
| L(B)<SI> has these eight triples
| of the form <s, i> in SxI:
|
| <"A", "A">
| <"A", "u">
| <"u", "A">
| <"u", "u">
| <"B", "B">
| <"B", "i">
| <"i", "B">
| <"i", "i">
A comparison of the corresponding projections for L(A) and L(B)
reveals that the distinction between these two 3-adic relations
is preserved under the operation that takes the full collection
of 2-adic projections into consideration, and this circumstance
allows one to say that this much information, that is, enough to
tell L(A) and L(B) apart, can be derived from their 2-adic faces.
However, in order to say that a 3-adic relation L on OxSxI
is "reducible" or "reconstructible" in the 2-dim projective
sense, it is necessary to show that no distinct L' on OxSxI
exists such that L and L' have the same set of projections,
and this can take a rather more exhaustive or comprehensive
investigation of the space of possible relations on OxSxI.
As it happens, each of the relations L(A) and L(B) turns
out to be uniquely determined by its 2-dim projections.
This can be seen as follows. Consider any coordinate
position <s, i> in the plane SxI. If <s, i> is not
in L<SI> then there can be no element <o, s, i> in L,
therefore we may restrict our attention to positions
<s, i> in L<SI>, knowing that there exist at least
|L<SI>| = Cardinality of L<SI> = 8 elements in L,
and seeking only to determine what objects o exist
such that <o, s, i> is an element in the objective
"fiber" of <s, i>. In other words, for what o in O
is <o, s, i> in ((Proj<SI>)^(-1))(<s, i>)? Now, the
circumstance that L<OS> has exactly one element <o, s>
for each coordinate s in S and that L<OI> has exactly
one element <o, i> for each coordinate i in I, plus
the "coincidence" of it being the same o at any one
choice for <s, i>, tells us that L has just the one
element <o, s, i> over each point of SxI. Together,
this proves that both L(A) and L(B) are reducible in
an informative sense to 3-tuples of 2-adic relations,
that is, they are "projectively 2-adically reducible".
Next time I will give examples of 3-adic relations
that are not reducible to or reconstructible from
their 2-adic projections.
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
Last time I gave two cases of 3-adic (triadic) relations
with projective reductions to 2-adic (dyadic) relations,
by name, "triadics reducible over projections" (TROP's),
"triadics reconstructible out of projections" (TROOP's).
Still, one needs to be very careful and hedgey about saying,
even in the presence of such cases, that "all is dyadicity".
I will make some attempt to explain why in the next episode,
and then I will take up examples of 3-adics that happen to
be irreducible in this sense, in effect, that are not able
to be recovered uniquely from their 2-adic projection data.
Call them "triadics irreducible over projections" (TRIOP's).
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
Projective Reduction of Triadic Relations: The Catch
This scene was initially interjected as a comic relief,
and so I will spare you the drollery of its repetition.
The entire pith and substance of it boils down to this
rather trivial observation, but one whose significance,
such as it may be, gets overlooked with serious punity,
and that is the fact that, even though one we have now
found in the sign relations L(A) and L(B) two examples
of 3-adic relations which are reconstructible from and
in this sense reducible to the 2-dimensional data sets
of their 2-adic projections, we entertain an insidious
self-deception if we think that we have given the slip
to 3-adic relations altogether. I feel sometimes like
I am straining to call the attentions of fish to water
by blubbering and glubbering "HOH, HOH, HOH" until the
sea shall free me, I guess, whenever I try to say this,
but I guess that I might as well just go ahead and try,
one more time, while still I have the O^2, and so here
I go, again, flailing at the logical immersion of this
entire process of "analysis" (= Greek for washing back)
in hope of rendering its nigh unto invisible influence
slightly more opaque to the light of a higher analysis.
All of which is just my attempt to remind you in a way
that you will not so soon forget that the very conduct
of the whole analytic reduction step is an association
among at least three relations, the analysand plus the
two or more analytic components, and there it goes yet
again, this ineluctable triadicity.
To bring the chase up short, the very idea of reduction,
when it means reducing one thing to more than one other
thing, is itself a relation of post-dyadic valence, and
thus parthenogenetically reproducing itself from itself,
evokes the polycloven hydra's hoof of Persean 3-adicity.
Okay, I just thought that you might welcome an intermezzo,
however scherzo-frenetic it might be, but now it's back
to the opera that the phantom of the operators wrote.
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
Projective Reduction of Triadic Relations
In the story of A and B, it appears to be the case
that that the triadic relations L(A) and L(B) are
distinguished from each other, and what's more,
distinguished from all of the other relations
in the garden of OSI, for the same O, S, I.
At least, so says I and my purported proof.
I am so suspicious of this result myself that
I will probably not really believe it for a while,
until I have revisited the problem and the "proof"
a few times, to see if I can punch any holes in it.
But let it pass for proven for now,
and let my feeble faith go for now.
For the sake of a more balanced account,
it's time to see if we can dig up any cases
of "projectively irreducible triadics" (PIT's).
Any such PIT relation, should we ever fall into one,
is bound to occasion another, since it is a porismatic
part of the definition that a triadic relation L is a PIT
if and only if there exists a distinct triadic relation L'
such that the dyadic faces of L and L' are indiscernible.
In this event, then both L and L' fall into the de-genre
of PIT's together.
| Note In Passing:
|
| PIT's are the same thing as TRIOP's, but I left in
| this earlier usage for personal historical reasons,
| and just in case I someday decide to go back to it.
Well, PIT's are not far to find, once you think to look for them --
indeed, the landscape of "formal or mathematical existence" (FOME)
is both figuratively and litterally rife with them!
What follows is the account of a couple,
that I will dub "L^0" and "L^1".
But first, even though the question of projective reduction
has to do with 3-adic relations as a general class, and is
thus independent of their potential use as sign relations,
it behooves us to consider the bearing of these reduction
properties on the topics of interest to us for the sake
of communication and representation via sign relations.
| Note On Notation:
|
| Let any of the locutions, L c XxYxZ, L on XxYxZ, L sub XxYxZ,
| substitute for the peculiar style of "in-line" or "in-passing"
| reference to subsethood that has become idiomatic in mathematics,
| and that would otherwise use the symbol that has been customary
| since the time of Peano to denote "contained in" or "subset of".
Most likely, any triadic relation L on XxYxZ that is imposed on
the arbitrary domains X, Y, Z could find use as a sign relation,
provided that it embodies any constraint at all, in other words,
so long as it forms a proper subset L of the entire space XxYxZ.
But these sorts of uses of triadic relations are not guaranteed
to capture or constitute any natural examples of sign relations.
In order to show what a projectively irreducible 3-adic relation
looks like, I now present a pair of 3-adic relations that have the
same 2-adic projections, and thus cannot be distinguished from each
other on the basis of this data alone. As it happens, these examples
of triadic relations can be discussed independently of sign relational
concerns, but structures of their basic ilk are frequently found arising
in signal-theoretic applications, and they are no doubt keenly associated
with questions of redundant coding and therefore of reliable communication.
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:
1. (L^0)<XY> = (L^1)<XY> = 1<XY> = BxB = B^2,
2. (L^0)<XZ> = (L^1)<XZ> = 1<XZ> = BxB = B^2,
3. (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".
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
We have pursued the "projective analysis" of 3-adic relations,
tracing the pursuit via a ready quantity of concrete examples,
just far enough to arrive at this clearly demonstrable result:
| Some 3-adic relations are and
| some 3-adic relations are not
| uniquely reconstructible from,
| or informatively reducible to,
| their 2-adic projection data.
We now take up the "compositive analysis" of 3-adic relations,
coining a term to prevent confusion, like there's a chance in
the world of that, but still making use of nothing other than
that "standardly uptaken operation" of relational composition,
the one that constitutes the customary generalization of what
just about every formal, logical, mathematical community that
is known to the writer, anyway, dubs "functional composition".
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
Compositive Reduction of Relations
The first order of business under this heading is straightforward enough:
to define what is standardly described as the "composition of relations".
| Notes 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 sub XxY and Q sub YxZ yield the "composite relation" PQ sub XxZ.
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.
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
There are one or two confusions that demand to
be cleared up before I can proceed any further.
We had been enjoying our long-anticipated breakthrough on the
allegedly "easy case" of projective reduction, having detected
hidden within that story of our old friends and usual suspects
A and B two examples of 3-adic relations, L(A) and L(B), that
are indeed amenable, not only to being distinguished, one from
the other, between the two of them, but also to being uniquely
determined amongst all of their kin by the information that is
contained in their 2-dimensional projections. So far, so good.
Had I been thinking fast enough, I would have assigned these the
nomen "triadics reducible in projections over dyadics" (TRIPOD's).
Other good names: "triadics reducible over projections" (TROP's),
or perhaps "triadics reconstructible out of projections" (TROOP's).
Then we found two examples of triadic relations, L^0 and L^1,
that I described as "projectively irreducible triadics" (PIT's),
because they collapse into an indistinct mass of non-descript
flatness on having their dyadic pictures taken. That acronym
does not always work for me, so I will give them the alias of
"triadics irreducible by projections over dyadics" (TIBPOD's),
or perhaps "triadics irreducible over projections" (TIOP's).
| The Author Addresses The Exasperants Of His Foibles:
|
| Please do not concern yourselves too much, or be too irritated by
| my extravagant struggles to hash out memorable hash codes for the
| produce the formal farm and the offerings of the logical scullery.
| I will eventually sort it all out and settle on some few that fit.
I am not accustomed to putting much stock in my own proofs
until I can reflect on them for a suitable period of time
or until a few other people have been able to go over them,
but until that happens I will just have to go with these
results as I presently see them.
In reply to my notes on these topics, Matthew West
has contributed the following pair of commentaries:
1. Regarding L(A) and L(B)
| Whilst I appreciate the academic support for showing
| that any triadic relation can be represented by some
| number of dyadic relations, the real point is to use
| this fact to seek for an improved analysis based on
| more fundamental concepts. It is not the objective
| to do something mechanical.
2. Regarding L^0 and L^1
| I don't think you have shown very much except that reducing
| triadic relations to dyadic relations using the mechanical
| process you have defined can loose information. I am not
| surprised by this. My experience of doing this with real,
| rather than abstract examples, is that there are often
| extra things to do.
So I need to clarify that what I think that I showed was
that "some" triadic relations are "reducible" in a given
informational sense to the information that is contained
in their dyadic projections, e.g., as L(A) and L(B) were,
but that others are not reducible in this particular way,
e.g., as L^0 and L^1 were not.
Now, aside from this, I think that Matthew is raising
a very important issue here, which I personally grasp
in terms of two different ways of losing information,
namely:
1. The information that we lose in forming a trial model,
in effect, in going from the unformalized "real world"
over to the formal context or the syntactic medium in
which models are constrained to live out their lives.
2. The information that we lose in "turning the crank"
on the model, that is, in drawing inferences from
the admittedly reductive and "off'n'wrong" model
in a way that loses even the initial information
that it captured about the real-world situation.
To do it justice, though, I will need to return
to this issue in a less frazzled frame of mind.
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
This will complete the revision of this RARified thread from last Autumn.
I will wind it up, as far as this part of it goes, by recapitulating the
development of the "Rise" relation, from a couple of days ago, this time
working through its analysis and its synthesis as fully as I know how at
the present state of my knowledge. The good of this exercise, of course,
the reason for doing all of this necessary work, is not because the Rise
relation is so terribly interesting in itself, but rather to demonstrate
the utility of the functional framework and its sundry attached tools in
their application to a nigh unto minimal and thus least obstructive case.
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
The good of this whole discussion, the use of it all,
the thing about it that makes it worth going through,
at least, for me, is not just to settle doubts about
the "banal", "common", or figuratively and literally
"trivial" (Latin for locus where "three roads" meet)
type of issue that may have appeared to be its point,
but, as I said in my recent reprise of justification,
to examine and explore "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."
So let me run through this development once more,
this time interlacing its crescendoes with a few
supplemental notes of showcasing or sidelighting,
aimed to render more clearly the aim of the work.
In order to accumulate a stock of ready-mixed concrete instances,
at the same time to supply ourselves with relatively fundamental
materials for building ever more complex and prospectively still
more desirable and elegant structures, maybe, even if it must be
worked out just a little bit gradually, hopefully, incrementally,
and even at times jury-rigged here and there, increasingly still
more useful architectronic forms for our joint contemplation and
and our meet edification, let us then set out once more from the
grounds of what we currently have in our command, and advance in
the directions of greater generalities and expanded scopes, with
the understanding that many such journeys are possible, and that
each is bound to open up on open-ended views at its unlidded top.
By way of a lightly diverting overture, let's begin
with an exemplar of a "degenerate triadic relation" --
do you guess that our opera is in an Italian manor? --
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> <=> [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.
That much we have seen and done before, but in the spirit of
that old saw that "what goes up must come down" we recognize
that there must be a supplementary relation in the scheme of
things that is equally worthy of our note, and so let us dub
this diminuendo the "Fall" relation, and set to define it so:
Let the relation named "Fall<2>"
such that Fall<2> c B^2 = B x B,
be exactly this set of 2-tuples:
| Fall<2> = {<0, 0>,
| <1, 0>,
| <1, 1>}
Let the relation named "Fall<3>"
such that Fall<3> c B^3 = BxBxB,
be exactly this set of 3-tuples:
| Fall<3> = {<0, 0, 0>,
| <1, 0, 0>,
| <1, 1, 0>,
| <1, 1, 1>}
And on those notes I must rest ...
To be continued ...
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
Starting from the simplest notions of Rise and Fall,
I may easily have chosen to leave it as an exercise
for the reader to discover suitable generalizations,
say from Rise<k> and Fall<k> for k of order 2 and 3,
to the slightly more general case in which k is any
natural number, that is, finite, integral, positive.
But that is far too easy a calisthenic, and no kind
of a work-out to offer our band of fearless readers,
and so the writer picks up the gage that he himself
throws down, and for his health runs the easy track!
Let B = {0, 1}.
Let the relation Rise<k> c B^k
be defined in the following way:
| Rise<k><x<1>, ..., x<k>>
|
| iff
|
| Rise<2><x<1>, x<2>> and Rise<k-1><x<2>, ..., x<k>>
Let the relation Fall<k> c B^k
be defined in the following way:
| Fall<k><x<1>, ..., x<k>>
|
| iff
|
| Fall<2><x<1>, x<2>> and Fall<k-1><x<2>, ..., x<k>>
But let me now leave off, for the time being,
from the temptation to go any further in the
direction of increasing k than I ever really
intended to, on beyond 2 or 3 or thereabouts,
for that is not the aim of the present study.
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
In this note I revisit the "Between" relation on reals,
and then I rework it as a discrete and finite analogue
of its transcendantal self, as a Between relation on B.
Ultimately, I want to use this construction as working
material to illustrate a method of defining relational
compositions in terms of projections. So let us begin.
Last time I defined Rise and Fall relations on B^k.
Working polymorphously, as some people like to say,
let us go ahead and define the analogous relations
over the real domain R, not even bothering to make
new names, but merely expecting the reader to find
the aptest sense for a given context of discussion.
Let R be the set of real numbers.
Let the relation named "Rise<2>"
such that Rise<2> c R^2 = R x R,
be defined in the following way:
| Rise<2><x, y>
|
| iff
|
| [x = y] or [x < y]
Let the relation named "Fall<2>"
such that Fall<2> c R^2 = R x R,
be defined in the following way:
| Fall<2><x, y>
|
| iff
|
| [x > y] or [x = y]
There are clearly a number of redundancies
between the definitions of these relations,
but I prefer the symmetry of this approach.
The next pair of definitions will be otiose, too,
if viewed in the light of the comprehensive case
that follows after, but let us go gently for now.
Let the relation named "Rise<3>"
such that Rise<3> c R^3 = RxRxR,
be defined in the following way:
| Rise<3><x, y, z>
|
| iff
|
| Rise<2><x, y> and Rise<2><y, z>
Let the relation named "Fall<3>"
such that Fall<3> c R^3 = RxRxR,
be defined in the following way:
| Fall<3><x, y, z>
|
| iff
|
| Fall<2><x, y> and Fall<2><y, z>
Then Rise<3> and Fall<3> are "degenerate 3-adic relations"
insofar as each of them bears expression as a conjunction
whose conjuncts are expressions of 2-adic relations alone.
Just in order to complete the development
of this thought, let us then finish it so:
Let the relation Rise<k> c R^k
be defined in the following way:
| Rise<k><x<1>, ..., x<k>>
|
| iff
|
| Rise<2><x<1>, x<2>> and Rise<k-1><x<2>, ..., x<k>>
Let the relation Fall<k> c R^k
be defined in the following way:
| Fall<k><x<1>, ..., x<k>>
|
| iff
|
| Fall<2><x<1>, x<2>> and Fall<k-1><x<2>, ..., x<k>>
If there was a point to writing out this last step,
I think that it may well have been how easy it was
not to write, not literally to "write" at all, but
simply to "cut and paste" the definitions from the
boolean case, and then but to change the parameter
B into the parameter R at a mere one place in each.
Let us then push on, in a retrograde way, returning to the orbit
of those very first relations that got us into the midst of this
quandary in the first place, to wit, the relations in medias res,
the relations of betwixt and between and all of their sundry kin.
But let us this time place the paltry special relations on which
we fixed the first time around back within the setting of a much
broader and a much more systematically examined context, that is,
an extended family of related relations or variations on a theme.
I hope that you will be able to recall that cousin of
the Between relation that we took up here once before,
and that you will be able to recognize its characters,
even if I now disguise it under a new name and partly
dissemble them under a new manner of parameterization.
Where you might take the name "IO" to mean "in order",
it is the relation defined on three real numbers thus:
Let the relation named "IO<213>"
such that IO<213> c R^3 = RxRxR,
be defined in the following way:
| IO<213><x, a, b> iff [a < x < b],
|
| equivalently,
|
| IO<213><x, a, b> iff [a < x] and [x < b].
Corresponding to the 3-adic relation IO<213> c R^3 = RxRxR,
there is a "proposition", a function io<213> : R^3 -> B,
that I will describe, until a better name comes along,
as the "relation map" that is "dual to" the relation.
It is also known as the "indicator" of that relation.
Consider the boolean analogue or the logical variant of IO,
with real domains : R now replaced by boolean domains : B.
The boolean analogue of the ordering "<" is the implication "=>",
so the logical variant of the relation IO<213> is given this way:
Let the relation named "IO<213>"
such that IO<213> c B^3 = BxBxB,
be defined in the following way:
| IO<213><x, a, b>
|
| iff
|
| [a => x] and [x => b]
When it does not risk any confusion,
one can express this also like this:
| IO<213><x, a, b>
|
| iff
|
| a => x => b
Corresponding to the 3-adic relation IO<213> c B^3 = BxBxB,
there is a "proposition", a function io<213> : B^3 -> B,
that I will describe, until a better name comes along,
as the "relation map" that is "dual to" the relation.
It is also known as the "indicator" of that relation.
At this point I want to try and get away with a bit
of additional flexibility in the syntax that I use,
reusing some of the same names for what are distinct
but closely related types of mathematical objects.
In particular, I would like to have the license
to speak a bit more loosely about these objects,
to ignore the distinction between "relations" of
the form Q c X<1> x ... x X<k> and "relation maps"
of the form q : X<1> x ... x X<k> -> B, and even
on sundry informal occasions to use the very same
names for them -- The Horror! -- hoping to let the
context determine the appropriate type of object,
except where it may be necessary to maintain this
distinction in order to avoid risking confusion.
In order to keep track of all of the players -- not to mention all of the refs! --
it may help to re-introduce a diagram that I have used many times before, as a
kind of a play-book or programme, to sort out the burgeoning teams of objects
and the cryptic arrays of signs that we need to follow throughout the course
of this rather extended into overtime game:
--------------------------------///--------------------------------------
Objective Framework (OF) Interpretive Framework (IF)
--------------------------------///--------------------------------------
Formal or Mathematical Objects Formal or Mathematical Signs & Texts
--------------------------------///--------------------------------------
Propositions Expressions
(Logical) (Propositional)
• •
| |
| |
• •
/ \ / \
/ \ / \
• • • •
Sets Maps Set Names Map Names
(Geometric) (Functional) (Geometric) (Functional)
--------------------------------///--------------------------------------
B^k B^k -> B "IO<213>" "io<213>"
R^k R^k -> B "IO<213>" "io<213>"
X^k X^k -> B "Q" "q"
--------------------------------///--------------------------------------
Matthew West wrote to Adam Pease:
| I think there are two key issues here.
|
| 1. When you use a larger relation as a primitive,
| you will have more types of relation. Whereas if
| you analyse them down to more fundamental relations,
| you may have more relations, but there will be fewer
| types of relation. This is usually an advantage.
| Indeed we have found that there is reuse at the
| individual relation level too, which means an
| effective reduction in repetition (with the
| opportunity for inconsistency that gives).
|
| 2. When you analyse to more fundamental concepts
| you give yourself the opportunity to be able to make
| inferences that arise from teh more fundamental level.
|
| In my view it is OK to have more complex relations provided
| they are rigourously defined in terms of underlying concepts.
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
What Matthew says here makes a lot of sense to me.
By way of illustrating the application of these heuristic principles
in the case of Adam Pease's Between relation, we might consider the
following analysis:
Given a =/= b, I will pull the usual trick and say,
"without loss of generality" (WOLOG), assume a < b.
Then:
| x is between a and b
|
| if and only if
|
| a < x and x < b
Now, if we are operating under what are likely to be
the default assumptions, the intended context, or the
standard interpretation of these statements, then the
sentence "x < y" invokes a dyadic relation LT c R x R,
where R = Reals, and this in turn corresponds to the
proposition lt : RxR -> B, where B = {0, 1} as usual.
This allows us to articulate the sentence "x is between a and b"
as invoking a certain 3-adic relation "1st between 2nd and 3rd",
or let us call it "IO<213>" for short, such that IO<213> c R^3,
and this in turn corresponds to the proposition io<213> : R^3 -> B.
Last but not least, recall that conjunction is just a function
that maps two propositions into a proposition, in other words,
a function of the form 'and' : (X -> B) x (X -> B) -> (X -> B).
Now here's a good question: What is X?
To be specific, is it R^2 or is it R^3?
We appear to have a little bit of a problem
matching up the divers pieces of the puzzle.
What this requires is a little gimmick that I call a "tacit extension".
In this case, we need a way of taking the function lt : R^2 -> B and
using it to construct two different functions of type : R^3 -> B.
Thus we need a couple of functions on functions, both having this form:
te : (R<1> x R<2> -> B) -> (R<1'> x R<2'> x R<3'> -> B),
Here we must now distinguish particular copies of R
in the cartesian products RxR = R^2 and RxRxR = R^3.
| Tacit extension 21 is defined by: (te<21>(f))(x, a, b) = f(a, x).
|
| Tacit extension 13 is defined by: (te<13>(f))(x, a, b) = f(x, b).
Applying these tacit extensions to lt we get:
| (te<21>(lt))(x, a, b) = lt<21>(x, a, b) = lt(a, x)
|
| (te<13>(lt))(x, a, b) = lt<13>(x, a, b) = lt(x, b)
In effect, the tacit extension of the "less than" map,
given three arguments, just compares the proper pair
of them, with a "don't care" condition on the other.
Putting all of these pieces together, we have this picture:
lt(a, x) . . lt(x, b)
| |
| |
te<21> o o te<13>
| |
| |
lt<21>(x, a, b) . . lt<13>(x, a, b)
\ /
\ /
\ /
[and]
|
|
|
.
io<213>(x, a, b)
This gives a functional decomposition of the proposition io<213>
making use of two different applications of the proposition lt,
a couple of tacit extensions te<21> and te<13>, and the reusable
function 'and' that connects the tacit extensions of lt together.
What is the use of all of this? -- especially in view of the fact
that we did not reduce the maximum arity of the relations involved?
In sum, we started with a 3-adic relation map io<213> : R^3 -> B,
getting a pair of 2-adic relation maps of the form lt : R^2 -> B,
plus two tacit extensions of the form te : (R^2 -> B) -> (R^3 -> B),
and a 3-adic relation of the shape 'and' : (R^3 -> B)^2 -> (R^3 -> B).
Well, the advantage, over the long haul, comes precisely from the fact
that the seemingly more complex pieces that we reached in the analysis
are pieces that are highly reusable in situation after situation, and
so it is worth the overhead, eventually, that it takes to understand
these recurring components as thoroughly as possible.
That brings an end to these Legends of the Fall,
And so I wish a gentle night to you one and all.
Jon Awbrey
¤~~~~~~~~~¤~~~~~~~~~¤~EVIHCRA~¤~~~~~~~~~¤~~~~~~~~~¤
Reductions Among Relations
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
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤