SUO: RE: Reductions Among Relations

["West, Matthew MR SSI-GREA-UK" <Matthew.R.West@is.shell.com>]

Dear Jon,

> 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 far as I can make out neither of these are what I consider I do
or what Pat has described. So any arguments about them are largely
irrelevant to what I might want to say on the subject.

Regards  
      Matthew
===============================================================
Matthew West                    http://www.matthew-west.org.uk/

Principal Consultant                   Shell Visiting Professor
Operations & Asset Management            The Keyworth Institute
Shell Services International            The University of Leeds
http://www.shellservices.com/  http://www.keyworth.leeds.ac.uk/

H3229, Shell Centre, London, SE1 7NA, UK.
Tel: +44 207 934 4490 Fax: 7929 Mobile: +44 7796 336538
=============================================================== 

> -----Original Message-----
> From: Jon Awbrey [mailto:jawbrey@oakland.edu]
> Sent: 20 March 2001 21:32
> To: Arisbe; Complexity Group; SemioCom; Stand Up Ontology
> Cc: Josiah Lee Auspitz; Paul R Chernoff; Lisa Cox; Pat Hayes; John F
> Sowa; West, Matthew MR SSI-GREA-UK
> Subject: 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
> 
> ¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
>