SUO: Reductions Among Relations
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
"Reductions Among Relations" (RAR) Interest Group:
Here is the carded out and less tangled up braiding
of the threads that we wove on this theme last Fall,
as I promised, or maybe you thought threadend y'all.
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
Note 1
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
Here are some notes on the topic of
"Reductions Among Relations" (RAR).
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.
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
Note 2
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
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
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
Note 3
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
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.
In the meantime, try to contain yourselves.
Jon Awbrey
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤