A New Kind of Science: The NKS Forum > Pure NKS > Reductions Among Relations
Author
Jon Awbrey

Registered: Feb 2004
Posts: 551

Reductions Among Relations

RAR. Note 1

For the sake of several ongoing threads
it will be necessary to introduce some
concepts from the theory of relations.

It is convenient to take up these concepts in
the context of discussing the general problem
of "reductions among relations" (RAR).

One of the things that keeps the general problem
of "reductions among relations" (RAR) from being
fully well-defined is that it would be necessary
to survey all of the conceivable ways of "getting
new relations from old" in order to say precisely
what is meant by the claim that "the relation L is
reducible to the set of relations {L_j : j in J}".
In other words, this amounts to claiming that if
you had a set of ostensibly simpler relations L_j,
for j in some set J, that this collection of data
would somehow or other fix the original relation L
that you were seeking to analyze, to determine,
to specify, or to synthesize.

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:

• Reduction Under Composition
• Reduction Under Projections

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.

Jon Awbrey

Report this post to a moderator | IP: Logged

04-27-2004 04:06 AM
Jon Awbrey

Registered: Feb 2004
Posts: 551

Reductions Among Relations

RAR. Note 2

1. Projective Reduction of Relations in General

I'll start out with the "projective reduction" of relations,
partly because it is easier to understand at the outset and
more visually intuitive, but also because there are several
tools that we need for the study of compositional reduction
that develop rather naturally within 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 type of picture, which pretty much says it all,
in that "one picture is worth a thousand words" sort of way.

Picture a k-adic relation L as a body in a k-dimensional space X.
If the k axes of X are the relational domains 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
X = X_1 x ... x X_k.

Let J be a subset of {1, ..., k}, and let X_J = {X_j : j in J}.
Then the "projection" of a point x in X on the subspace of X
that is generated by X_J is denoted by "Proj_J (x)".

By extension, the projection of any relation L on that subspace
is denoted by "Proj_J (L)", or still more simply, by "Proj_J 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?

Jon Awbrey

Last edited by Jon Awbrey on 04-28-2004 at 02:26 PM

Report this post to a moderator | IP: Logged

04-27-2004 04:44 AM
Jon Awbrey

Registered: Feb 2004
Posts: 551

Reductions Among Relations

RAR. Note 3

2. 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

Suppose that L c X x Y x Z 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 already
introduced, and compressing it a bit in passing, one denotes
these projections in any one of the following ways, depending
on which alternative is the most convenient in a given context:

• Proj_{X,Y} (L) = Proj_{1,2} (L) = Proj_XY L = Proj_12 L = L_XY = L_12.

• Proj_{X,Z} (L) = Proj_{1,3} (L) = Proj_XZ L = Proj_13 L = L_XZ = L_13.

• 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, one says that
L is "not reducible to" or "not reconstructible from"
its 2-dimensional projections if and only if there
exists a distinct relation L' such that L and L'
have exactly the same projections on exactly
the same planes.

Jon Awbrey

Last edited by Jon Awbrey on 04-27-2004 at 04:14 PM

Report this post to a moderator | IP: Logged

04-27-2004 05:04 AM
Jon Awbrey

Registered: Feb 2004
Posts: 551

Reductions Among Relations

RAR. Note 4

2. Projective Reduction of Triadic Relations (cont.)

It serves to develop a few concrete examples of 3-adic relations,
solid enough to reflect the lights of these various perspectives.

I will re-introduce here a couple of 3-adic relations
that I have often used as examples of "sign relations".
For now we are only interested in their properties as
3-adic relations, in the light of projective reduction.

The 3-adic relations L(A) and L(B) are defined as follows:

L(A) and L(B) are subsets of the cartesian product O x S x I, where
O = {A, B}, S = {"A", "B", "i", "u"}, and I = {"A", "B", "i", "u"}.

L(A) has the following eight triples
of the form <o, s, i> in O x S x I:

<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 O x S x I:

<A, "A", "A">
<A, "A", "u">
<A, "u", "A">
<A, "u", "u">
<B, "B", "B">
<B, "B", "i">
<B, "i", "B">
<B, "i", "i">

The next series of Tables illustrates the projection operations
by means of their actions on the sign relations L(A) and L(B).

Taking the 2-adic projections of L(A)
one obtains the following set of data:

L(A)_OS has these four pairs
of the form <o, s> in O x S:

<A, "A">
<A, "i">
<B, "B">
<B, "u">

L(A)_OI has these four pairs
of the form <o, i> in O x I:

<A, "A">
<A, "i">
<B, "B">
<B, "u">

L(A)_SI has these eight pairs
of the form <s, i> in S x I:

<"A", "A">
<"A", "i">
<"i", "A">
<"i", "i">
<"B", "B">
<"B", "u">
<"u", "B">
<"u", "u">

Taking the 2-adic projections of L(B)
one obtains the following set of data:

L(B)_OS has these four pairs
of the form <o, s> in O x S:

<A, "A">
<A, "u">
<B, "B">
<B, "i">

L(B)_OI has these four pairs
of the form <o, i> in O x I:

<A, "A">
<A, "u">
<B, "B">
<B, "i">

L(B)_SI has these eight pairs
of the form <s, i> in S x I:

<"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, at least enough to
tell L(A) and L(B) apart, can be derived from their 2-adic faces.

However, we are not done yet. In order to say that
a 3-adic relation L c O x S x I is "reducible to" or
"reconstructible from" 2-dimensional projective data,
we would need to show that no distinct L' c O x S x I
exists such that L and L' have identical projections,
and this takes a more comprehensive investigation of
the variety of all possible relations on O x S x I.

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 S x I. 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 = eight 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 S x I. In all,
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

Jon Awbrey

Report this post to a moderator | IP: Logged

04-27-2004 02:20 PM
Jon Awbrey

Registered: Feb 2004
Posts: 551

Reductions Among Relations

RAR. Note 5

2. Projective Reduction of Triadic Relations (cont.)

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 3-adic 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.

We need a few preliminary definitions and notations:

B = {0, 1} will be taken algebraically as GF(2),
where the plus sign "+" indicates 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 X x Y x Z is isomorphic to B x B x B = B^3.
Lacking a good isomorphism symbol in Ascii, I will resort to writing
things like "X x Y x Z iso B x B x B" or even "X x Y x Z ~=~ B^3".

Consider the 3-adic relations L_0 and L_1 that are defined as follows:

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>

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:

The 2-adic projections of L_0 yield the following data:

Proj_12 (L_0) has these four pairs of the form <x, y> in X x Y:

<0, 0>
<0, 1>
<1, 0>
<1, 1>

Proj_13 (L_0) has these four pairs of the form <x, z> in X x Z:

<0, 0>
<0, 1>
<1, 1>
<1, 0>

Proj_23 (L_0) has these four pairs of the form <y, z> in Y x Z:

<0, 0>
<1, 1>
<0, 1>
<1, 0>

The 2-adic projections of L_1 yield the following data:

Proj_12 (L_1) has these four pairs of the form <x, y> in X x Y:

<0, 0>
<0, 1>
<1, 0>
<1, 1>

Proj_13 (L_1) has these four pairs of the form <x, z> in X x Z:

<0, 1>
<0, 0>
<1, 0>
<1, 1>

Proj_23 (L_1) has these four pairs of the form <y, z> in Y x Z:

<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 3-adic relations.
As sets, however, the order in which one lists the
elements is irrelevant, and so a simple comparison
of the corresponding data sets is enough to verify
that L_0 and L_1 have exactly the same projections
on each of the corresponding relational planes.

To summarize:

The relations L_0, L_1 c 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.

• 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.

• 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 formal
abstraction, constitute precisely the same 2-adic relation,
one which is isomorphic to the whole of B x B and which is
thus indicated by the constant proposition 1 : B x B -> B.
Written out in symbolic form, we have the following facts:

Proj_XY (L_0) = Proj_XY (L_1) = [| 1_XY |] ~=~ B x B

Proj_XZ (L_0) = Proj_XZ (L_1) = [| 1_XZ |] ~=~ B x B

Proj_YZ (L_0) = Proj_YZ (L_1) = [| 1_YZ |] ~=~ B x B

In short, L_0 and L_1 form an indiscernible couplet
of "3-adic relations irreducible over projections"

Jon Awbrey

Last edited by Jon Awbrey on 04-27-2004 at 04:32 PM

Report this post to a moderator | IP: Logged

04-27-2004 04:00 PM
Jon Awbrey

Registered: Feb 2004
Posts: 551

Reductions Among Relations

RAR. Note 6

2. Projective Reduction of Triadic Relations (concl.)

We have pursued the "projective analysis" of 3-adic relations,
tracing the pursuit through a ready crew of concrete examples,
just far enough to arrive at this clearly demonstrable result:

informatively reducible to, or
uniquely reconstructible from,

Jon Awbrey

Report this post to a moderator | IP: Logged

04-27-2004 04:44 PM
Jon Awbrey

Registered: Feb 2004
Posts: 551

Reductions Among Relations

RAR. Note 7

3. Compositional Analysis of Relations

to define what is standardly described as the "composition of relations".
For the time being I limit the discussion to 2-adic and 3-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 c X x Y and Q c Y x Z yield the "composite relation" PQ c X x Z.

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.

Jon Awbrey

Report this post to a moderator | IP: Logged

04-27-2004 05:12 PM
Jon Awbrey

Registered: Feb 2004
Posts: 551

Reductions Among Relations

RAR. Note 8

3. Compositional Analysis of Relations (cont.)

Let's take a moment to highlight the connections
between two topics that may appear unrelated at
first sight, namely:

• The use of logical conjunction to define a 3-adic relation F
in terms of a pair of 2-adic relations G and H. This use is
exemplified by the function of the connective symbol "&"
in the logical formula F(x, y, z) <=> G(x, y) & H(y, z).

• The concepts of 2-adic projection and projective determination
that are involved in the definition of projective reducibility.

We can begin by drawing a picture of what is really going on
when we define a relation F c X x Y x Z via a conjunction of
the relations G c X x Y and H c Y x Z, as we are very likely
to do by means of a logical expression of the following form:

F(x, y, z) <=> G(x, y) & H(y, z)

Figure 8 depicts the 3-adic relation F c X x Y x Z
as a body in XYZ-space, while the 2-adic relations
G c X x Y and H c Y x Z are shown as plane figures
in the XY-plane and the YZ-plane, respectively.

o-------------------------------------------------o
| ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` ` `o` ` ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` ` /|\ ` ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` `/`|`\` ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` / `|` \ ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` `/` `|` `\` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` / ` `|` ` \ ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` `/` ` `|` ` `\` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` / ` ` `|` ` ` \ ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `o` ` ` `o` ` ` `o` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `|\ ` ` / \ ` ` /|` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `|`\` `/`F`\` `/`|` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `|` \ / `*` \ / `|` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `|` `\` *** `/` `|` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `|` / \//*\\/ \ `|` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `|`/` /\/ \/\ `\`|` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `|/ `///\ /\\\` \|` ` ` ` ` ` ` ` |
| ` ` ` `o` ` ` `X` /// `Y` \\\ `Z` ` ` `o` ` ` ` |
| ` ` ` `|\ ` ` ` \///` `|` `\\\/ ` ` ` /|` ` ` ` |
| ` ` ` `|`\` ` ` /// ` `|` ` \\\ ` ` `/`|` ` ` ` |
| ` ` ` `|` \ ` `///\ ` `|` ` /\\\` ` / `|` ` ` ` |
| ` ` ` `|` `\` /// `\` `|` `/` \\\ `/` `|` ` ` ` |
| ` ` ` `|` ` \///` ` \ `|` / ` `\\\/ ` `|` ` ` ` |
| ` ` ` `|` ` /\/ ` ` `\`|`/` ` ` \/\ ` `|` ` ` ` |
| ` ` ` `|` `*//\ ` ` ` \|/ ` ` ` /\\*` `|` ` ` ` |
| ` ` ` `X` `*/ `Y` ` ` `o` ` ` `Y` \*` `Z` ` ` ` |
| ` ` ` ` \ `*` `|` ` ` ` ` ` ` `|` `*` / ` ` ` ` |
| ` ` ` ` `\`G` `|` ` ` ` ` ` ` `|` `H /` ` ` ` ` |
| ` ` ` ` ` \ ` `|` ` ` ` ` ` ` `|` ` / ` ` ` ` ` |
| ` ` ` ` ` `\` `|` ` ` ` ` ` ` `|` `/` ` ` ` ` ` |
| ` ` ` ` ` ` \ `|` ` ` ` ` ` ` `|` / ` ` ` ` ` ` |
| ` ` ` ` ` ` `\`|` ` ` ` ` ` ` `|`/` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` \|` ` ` ` ` ` ` `|/ ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `o` ` ` ` ` ` ` `o` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` |
o-------------------------------------------------o
Figure 8. Projections of F onto G and H

Jon Awbrey

Last edited by Jon Awbrey on 04-28-2004 at 02:28 PM

Report this post to a moderator | IP: Logged

04-27-2004 06:20 PM
Jon Awbrey

Registered: Feb 2004
Posts: 551

Reductions Among Relations

RAR. Note 9

3. Compositional Analysis of Relations (cont.)

The following definitions come into play at this point:

The "power set" of a set X, written here
as Pow(X), is the set of all subsets of X.

!L!_(X_1...X_k) is the set all of k-adic relations on the
indicated k-set of domains, X_1, ..., X_k. Since we are
taking an arbitrary k-adic relation L to be a subset of
some cartesian product, X = X_1 x ... x X_k, the set
of all k-adic relations of the indicated type is
given by the following formula:

!L!_(X_1...X_k) = Pow(X_1 x ... x X_k)

The 2-adic "projections" Proj_XY, Proj_XZ, Proj_YZ,
for any 3-adic relation L c X x Y x Z, along with
their respective equivalents L_XY, L_XZ, L_YZ,
are defined as follows:

• Proj_XY (L) = {<x, y> in X x Y : <x, y, z> in L for some z in Z}

• Proj_XZ (L) = {<x, z> in X x Z : <x, y, z> in L for some y in Y}

• Proj_YZ (L) = {<y, z> in Y x Z : <x, y, z> in L for some x in X}

In light of these definitions, Proj_XY is a mapping from
the space !L!_XYZ = Pow(X x Y x Z) of all 3-adic relations
on the domains X, Y, Z into the space !L!_XY = Pow(X x Y)
of all 2-adic relations on the domains X and Y. Corresponding
statements apply, mutatis mutandis, to each of the other two
projections, Proj_XZ and Proj_YZ. Thus we have the following:

• Proj_XY : !L!_XYZ -> !L!_XY

• Proj_XZ : !L!_XYZ -> !L!_XZ

• Proj_YZ : !L!_XYZ -> !L!_YZ

Jon Awbrey

Last edited by Jon Awbrey on 04-28-2004 at 12:28 PM

Report this post to a moderator | IP: Logged

04-27-2004 08:20 PM
Jon Awbrey

Registered: Feb 2004
Posts: 551

Reductions Among Relations

RAR. Note 10

3. Compositional Analysis of Relations (cont.)

No sooner do we run into a new computational operation than
we start to think about running it backwards, in other words,
to consider the kinds of operations that would act to invert
or reverse its action, at least, in some fashion or measure.

In mathematics, the inverse operation of a projection is usually
called an "extension", but in view of the many different types
of extension that one has to consider from context to context
I will try to lessen the risk of confusion by always using
a descriptive adjective to pick out the sense that I mean.

then there are a couple of different possibilities that
might answer for an "inverse projection", depending on
the context of application that we have in mind.

I will take the simplest tack first, and define
what I call the "tacit extensions" of relations.

Let us start out in a simple setting, say, one

For example, suppose we have the following 2-adic relations:

U c X x Y

V c X x Z

W c Y x Z

The "tacit extensions" TE_XY_Z, TE_XZ_Y, TE_YZ_X,
of the relations U c X x Y, V c X x Z, W c Y x Z,
respectively, are defined in the following manner:

TE_XY_Z (U) = {<x, y, z> : <x, y> in U}

TE_XZ_Y (V) = {<x, y, z> : <x, z> in V}

TE_YZ_X (W) = {<x, y, z> : <y, z> in W}

It will be clear enough to write TE(U), TE(V), TE(W),
respectively, so long as the contexts are understood.

Jon Awbrey

Report this post to a moderator | IP: Logged

04-28-2004 03:14 AM
Jon Awbrey

Registered: Feb 2004
Posts: 551

Reductions Among Relations

RAR. Note 11

3. Compositional Analysis of Relations (cont.)

Let us now examine how the operations of projection
and tacit extension are involved in the Example where
we sought to define a 3-adic relation F in terms of the
2-adic relations G and H by means of the logical formula
F(x, y, z) <=> G(x, y) & H(y, z). The definition involves
the tacit extension of G c X x Y to TE(G) c X x Y x Z and
the tacit extension of H c Y x Z to TE(H) c X x Y x Z.

Here are the snapshots:

o-------------------------------------------------o
| ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` ` `o` ` ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` ` /|\ ` ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` `/`|`\` ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` / `|` \ ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` `/` `|` `\` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` / ` `|` ` \ ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` `/` ` `|` ` `\` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` / ` ` `|` `*` \ ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `o` ` ` `o` **` `o` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `|\ ` ` / \***` /|` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `|`\` `/` *** `/`|` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `|` \ / `***\ / `|` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `|` `\` *** `/` `|` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `|` / \***` / \ `|` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `|`/` *** `/` `\`|` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `|/ `***\ / ` ` \|` ` ` ` ` ` ` ` |
| ` ` ` `o` ` ` `X` /** `Y` ` ` `Z` ` ` `o` ` ` ` |
| ` ` ` `|\ ` ` ` \//*` `|` ` ` / ` ` ` /|` ` ` ` |
| ` ` ` `|`\` ` ` /// ` `|` ` `/` ` ` `/`|` ` ` ` |
| ` ` ` `|` \ ` `///\ ` `|` ` / ` ` ` / `|` ` ` ` |
| ` ` ` `|` `\` /// `\` `|` `/` ` ` `/` `|` ` ` ` |
| ` ` ` `|` ` \///` ` \ `|` / ` ` ` / ` `|` ` ` ` |
| ` ` ` `|` ` /\/ ` ` `\`|`/` ` ` `/` ` `|` ` ` ` |
| ` ` ` `|` `*//\ ` ` ` \|/ ` ` ` / `*` `|` ` ` ` |
| ` ` ` `X` `*/ `Y` ` ` `o` ` ` `Y` `*` `Z` ` ` ` |
| ` ` ` ` \ `*` `|` ` ` ` ` ` ` `|` `*` / ` ` ` ` |
| ` ` ` ` `\`G` `|` ` ` ` ` ` ` `|` `H /` ` ` ` ` |
| ` ` ` ` ` \ ` `|` ` ` ` ` ` ` `|` ` / ` ` ` ` ` |
| ` ` ` ` ` `\` `|` ` ` ` ` ` ` `|` `/` ` ` ` ` ` |
| ` ` ` ` ` ` \ `|` ` ` ` ` ` ` `|` / ` ` ` ` ` ` |
| ` ` ` ` ` ` `\`|` ` ` ` ` ` ` `|`/` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` \|` ` ` ` ` ` ` `|/ ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `o` ` ` ` ` ` ` `o` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` |
o-------------------------------------------------o
Figure 11-a. Tacit Extension of G to X x Y x Z

o-------------------------------------------------o
| ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` ` `o` ` ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` ` /|\ ` ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` `/`|`\` ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` / `|` \ ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` `/` `|` `\` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` / ` `|` ` \ ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` `/` ` `|` ` `\` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` / `*` `|` ` ` \ ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `o` `** `o` ` ` `o` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `|\ `***/ \ ` ` /|` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `|`\` *** `\` `/`|` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `|` \ /***` \ / `|` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `|` `\` *** `/` `|` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `|` / \ `***/ \ `|` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `|`/` `\` *** `\`|` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `|/ ` ` \ /***` \|` ` ` ` ` ` ` ` |
| ` ` ` `o` ` ` `X` ` ` `Y` **\ `Z` ` ` `o` ` ` ` |
| ` ` ` `|\ ` ` ` \ ` ` `|` `*\\/ ` ` ` /|` ` ` ` |
| ` ` ` `|`\` ` ` `\` ` `|` ` \\\ ` ` `/`|` ` ` ` |
| ` ` ` `|` \ ` ` ` \ ` `|` ` /\\\` ` / `|` ` ` ` |
| ` ` ` `|` `\` ` ` `\` `|` `/` \\\ `/` `|` ` ` ` |
| ` ` ` `|` ` \ ` ` ` \ `|` / ` `\\\/ ` `|` ` ` ` |
| ` ` ` `|` ` `\` ` ` `\`|`/` ` ` \/\ ` `|` ` ` ` |
| ` ` ` `|` `*` \ ` ` ` \|/ ` ` ` /\\*` `|` ` ` ` |
| ` ` ` `X` `*` `Y` ` ` `o` ` ` `Y` \*` `Z` ` ` ` |
| ` ` ` ` \ `*` `|` ` ` ` ` ` ` `|` `*` / ` ` ` ` |
| ` ` ` ` `\`G` `|` ` ` ` ` ` ` `|` `H /` ` ` ` ` |
| ` ` ` ` ` \ ` `|` ` ` ` ` ` ` `|` ` / ` ` ` ` ` |
| ` ` ` ` ` `\` `|` ` ` ` ` ` ` `|` `/` ` ` ` ` ` |
| ` ` ` ` ` ` \ `|` ` ` ` ` ` ` `|` / ` ` ` ` ` ` |
| ` ` ` ` ` ` `\`|` ` ` ` ` ` ` `|`/` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` \|` ` ` ` ` ` ` `|/ ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `o` ` ` ` ` ` ` `o` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` |
o-------------------------------------------------o
Figure 11-b. Tacit Extension of H to X x Y x Z

Finally, we can now supply a visual interpretation
that helps us to see the meaning of a formula like:

F(x, y, z) <=> G(x, y) & H(y, z).

The conjunction that is indicated by "&" corresponds as usual
to an intersection of two sets, however, in this case it is
the intersection of the tacit extensions TE(G) and TE(H).

o-------------------------------------------------o
| ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` ` `o` ` ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` ` /|\ ` ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` `/`|`\` ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` / `|` \ ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` `/` `|` `\` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` / ` `|` ` \ ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` `/` ` `|` ` `\` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` / ` ` `|` ` ` \ ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `o` ` ` `o` ` ` `o` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `|\ ` ` / \ ` ` /|` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `|`\` `/`F`\` `/`|` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `|` \ / `*` \ / `|` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `|` `\` *** `/` `|` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `|` / \//*\\/ \ `|` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `|`/` /\/ \/\ `\`|` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `|/ `///\ /\\\` \|` ` ` ` ` ` ` ` |
| ` ` ` `o` ` ` `X` /// `Y` \\\ `Z` ` ` `o` ` ` ` |
| ` ` ` `|\ ` ` ` \///` `|` `\\\/ ` ` ` /|` ` ` ` |
| ` ` ` `|`\` ` ` /// ` `|` ` \\\ ` ` `/`|` ` ` ` |
| ` ` ` `|` \ ` `///\ ` `|` ` /\\\` ` / `|` ` ` ` |
| ` ` ` `|` `\` /// `\` `|` `/` \\\ `/` `|` ` ` ` |
| ` ` ` `|` ` \///` ` \ `|` / ` `\\\/ ` `|` ` ` ` |
| ` ` ` `|` ` /\/ ` ` `\`|`/` ` ` \/\ ` `|` ` ` ` |
| ` ` ` `|` `*//\ ` ` ` \|/ ` ` ` /\\*` `|` ` ` ` |
| ` ` ` `X` `*/ `Y` ` ` `o` ` ` `Y` \*` `Z` ` ` ` |
| ` ` ` ` \ `*` `|` ` ` ` ` ` ` `|` `*` / ` ` ` ` |
| ` ` ` ` `\`G` `|` ` ` ` ` ` ` `|` `H /` ` ` ` ` |
| ` ` ` ` ` \ ` `|` ` ` ` ` ` ` `|` ` / ` ` ` ` ` |
| ` ` ` ` ` `\` `|` ` ` ` ` ` ` `|` `/` ` ` ` ` ` |
| ` ` ` ` ` ` \ `|` ` ` ` ` ` ` `|` / ` ` ` ` ` ` |
| ` ` ` ` ` ` `\`|` ` ` ` ` ` ` `|`/` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` \|` ` ` ` ` ` ` `|/ ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `o` ` ` ` ` ` ` `o` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` |
o-------------------------------------------------o
Figure 11-c. F as the Intersection of TE(G) and TE(H)

Jon Awbrey

Report this post to a moderator | IP: Logged

04-28-2004 03:00 PM
Jon Awbrey

Registered: Feb 2004
Posts: 551

Reductions Among Relations

RAR. Note 12

3. Compositional Analysis of Relations (cont.)

Let us now look at a way of defining the relational composition of
2-adic relations by using the set-theoretic operational resources
of intersections, projections, and tacit extensions. To be more
specific, we will define the relational composition of a couple
of 2-adic relations in terms of their separate tacit extensions
to 3-adic relations, followed by the set intersection of these
tacit extensions, and then the projection of this intersection,
tantamount to the maximal 3-adic relation that is consistent
with the 'prima facie' 2-adic relational data, onto a third
2-adic relation, the computed composition of the first two.

I usually think of this definition of composition as "Tarski's Trick",
because I learned it from a paper of Ulam that attributes it to Tarski,
but I would not be surprised to find the same principle being used by
Peirce, De Morgan, or even Newton, for that matter.

| Ulam, S.M. & Bednarek, A.R., "On the Theory of Relational Structures
| and Schemata for Parallel Computation", original report dated 1977,
| Ulam & Bednarek (eds.), 'Analogies Between Analogies', pp. 477-508.
|
| Ulam, F. & Bednarek, A.R. (eds.),
|'Analogies Between Analogies: The Mathematical Reports of S.M. Ulam
| and his Los Alamos Collaborators', University of California Press,
| Berkeley, CA, 1990.

We begin with a pair of 2-adic relations G, H c X x Y.

o-------------------------------------------------o
| ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` |
| ` ` ` `o` ` ` ` ` ` ` ` ` ` ` `o` ` ` ` ` ` ` ` |
| ` ` ` `|\ ` ` ` ` ` ` ` ` ` ` `|\ ` ` ` ` ` ` ` |
| ` ` ` `|`\` ` ` ` ` ` ` ` ` ` `|`\` ` ` ` ` ` ` |
| ` ` ` `|` \ ` ` ` ` ` ` ` ` ` `|` \ ` ` ` ` ` ` |
| ` ` ` `|` `\` ` ` ` ` ` ` ` ` `|` `\` ` ` ` ` ` |
| ` ` ` `|` ` \ ` ` ` ` ` ` ` ` `|` ` \ ` ` ` ` ` |
| ` ` ` `|` ` `\` ` ` ` ` ` ` ` `|` ` `\` ` ` ` ` |
| ` ` ` `|` `*` \ ` ` ` ` ` ` ` `|` `*` \ ` ` ` ` |
| ` ` ` `X` `*` `Y` ` ` ` ` ` ` `X` `*` `Y` ` ` ` |
| ` ` ` ` \ `*` `|` ` ` ` ` ` ` ` \ `*` `|` ` ` ` |
| ` ` ` ` `\`G` `|` ` ` ` ` ` ` ` `\`H` `|` ` ` ` |
| ` ` ` ` ` \ ` `|` ` ` ` ` ` ` ` ` \ ` `|` ` ` ` |
| ` ` ` ` ` `\` `|` ` ` ` ` ` ` ` ` `\` `|` ` ` ` |
| ` ` ` ` ` ` \ `|` ` ` ` ` ` ` ` ` ` \ `|` ` ` ` |
| ` ` ` ` ` ` `\`|` ` ` ` ` ` ` ` ` ` `\`|` ` ` ` |
| ` ` ` ` ` ` ` \|` ` ` ` ` ` ` ` ` ` ` \|` ` ` ` |
| ` ` ` ` ` ` ` `o` ` ` ` ` ` ` ` ` ` ` `o` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` |
o-------------------------------------------------o
Figure 12-a. Dyadic Relations G, H c X x Y

Note that H is not exactly the same H that we had before,
because this H is presented in the same plane X x Y as G.
Whether you view isomorphic things to be the same things
or not, you still have to specify the exact isomorphisms
that are needed to transform any given representation of
a thing into a required representation of the same thing.
Let us imagine that we have done this, and say how later:

o-------------------------------------------------o
| ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` |
| ` ` ` `o` ` ` ` ` ` ` ` ` ` ` ` ` ` ` `o` ` ` ` |
| ` ` ` `|\ ` ` ` ` ` ` ` ` ` ` ` ` ` ` /|` ` ` ` |
| ` ` ` `|`\` ` ` ` ` ` ` ` ` ` ` ` ` `/`|` ` ` ` |
| ` ` ` `|` \ ` ` ` ` ` ` ` ` ` ` ` ` / `|` ` ` ` |
| ` ` ` `|` `\` ` ` ` ` ` ` ` ` ` ` `/` `|` ` ` ` |
| ` ` ` `|` ` \ ` ` ` ` ` ` ` ` ` ` / ` `|` ` ` ` |
| ` ` ` `|` ` `\` ` ` ` ` ` ` ` ` `/` ` `|` ` ` ` |
| ` ` ` `|` `*` \ ` ` ` ` ` ` ` ` / `*` `|` ` ` ` |
| ` ` ` `X` `*` `Y` ` ` ` ` ` ` `Y` `*` `Z` ` ` ` |
| ` ` ` ` \ `*` `|` ` ` ` ` ` ` `|` `*` / ` ` ` ` |
| ` ` ` ` `\`G` `|` ` ` ` ` ` ` `|` `H'/` ` ` ` ` |
| ` ` ` ` ` \ ` `|` ` ` ` ` ` ` `|` ` / ` ` ` ` ` |
| ` ` ` ` ` `\` `|` ` ` ` ` ` ` `|` `/` ` ` ` ` ` |
| ` ` ` ` ` ` \ `|` ` ` ` ` ` ` `|` / ` ` ` ` ` ` |
| ` ` ` ` ` ` `\`|` ` ` ` ` ` ` `|`/` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` \|` ` ` ` ` ` ` `|/ ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `o` ` ` ` ` ` ` `o` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` |
o-------------------------------------------------o
Figure 12-b. Dyadic Relations G c X x Y and H' c Y x Z

Jon Awbrey

Report this post to a moderator | IP: Logged

04-28-2004 04:44 PM
Jon Awbrey

Registered: Feb 2004
Posts: 551

Reductions Among Relations

RAR. Note 13

3. Compositional Analysis of Relations (cont.)

We continue with the trick already in progress,
whereby Ulam reports Tarski as describing the
relational composition P o Q of a couple of
2-adic relations P, Q c X x X in this way:

Definition. P o Q = Proj_13 (P x X |^| X x Q).

To get this drift of this definition, one needs
to understand that it's written within a school
of thought that holds that all 2-adic relations
are, "without loss of generality", covered well
enough, "for all practical purposes", under the
aegis of subsets of a suitable cartesian square,
and thus of the form L c X x X. So, if one has
started out with a 2-adic relation of the shape
L c U x V, one merely lets X = U |_| V, trading
in the initial L for a new L c X x X as need be.

Proj_13 is just the projection of the cartesian
cube X x X x X on the space of shape X x X that
is spanned by the first and the third domains,
but since they now have the same names and the
same contents it is necessary to distinguish
them by numbering their relational places.

Finally, the notation of the cartesian product sign "x"
is abused, or extended, depending on your point of view,
to signify a couple of other "products" with respect to
a 2-adic relation L c X x X and a subset W c X, like so:

Definition. L x W = {<x, y, z> in X^3 : <x, y> in L and z in W}.

Definition. W x L = {<x, y, z> in X^3 : x in W and <y, z> in L}.

Applying these definitions to the case P, Q c X x X,
the two 2-adic relations whose relational composition
P o Q c X x X is about to be defined, one obtains this:

P x X = {<x, y, z> in X^3 : <x, y> in P and z in X},

X x Q = {<x, y, z> in X^3 : x in X and <y, z> in Q}.

I hope it is clear that these are just
the appropriate special cases of the

P x X = TE_12_3 (P),

X x Q = TE_23_1 (Q).

In summary, then, the expression:

Proj_13 (P x X |^| X x Q)

is equivalent to the expression:

Proj_13 (TE_12_3 (P) |^| TE_23_1 (Q))

and this form is generalized -- although relative to
one's school of thought, perhaps inessentially so --
by the form from my school that I recite as follows:

Definition. P o Q = Proj_XZ (TE_XY_Z (P) |^| TE_YZ_X (Q)).

Jon Awbrey

Report this post to a moderator | IP: Logged

04-28-2004 06:18 PM
Jon Awbrey

Registered: Feb 2004
Posts: 551

Reductions Among Relations

RAR. Note 14

3. Compositional Analysis of Relations (concl.)

Let us now render the picture of our composition example
a little less impressionistic and a little more realistic
in the manner of its representation, and let us accomplish
this through the introduction of coordinates, in other words,
concrete names for the objects that we relate through various

Revising the Example along these lines
would give a Figure like the following:

o-------------------------------------------------o
| ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` ` `o` ` ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` ` /|\ ` ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` `/`|`\` ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` / `|` \ ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` `/` `|` `\` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` / ` `|` ` \ ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` `/` ` `|` ` `\` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` / ` ` `|` ` ` \ ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `o` ` ` `o` ` ` `o` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `|\ ` ` / \ ` ` /|` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `|`\` `/`F`\` `/`|` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `|` \ / `*` \ / `|` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `|` `\` /*\ `/` `|` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `|` / \//*\\/ \ `|` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `|`/` /\/ \/\ `\`|` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `|/ `///\ /\\\` \|` ` ` ` ` ` ` ` |
| ` ` ` `o` ` ` `X` /// `Y` \\\ `Z` ` ` `o` ` ` ` |
| ` ` ` `|\ ` ` `7\///` `|` `\\\/7` ` ` /|` ` ` ` |
| ` ` ` `|`\` ` ` 6// ` `|` ` \\6 ` ` `/`|` ` ` ` |
| ` ` ` `|` \ ` `//5\ ` `|` ` /5\\` ` / `|` ` ` ` |
| ` ` ` `|` `\` /// 4\` `|` `/4 \\\ `/` `|` ` ` ` |
| ` ` ` `|` ` \///` `3\ `|` /3` `\\\/ ` `|` ` ` ` |
| ` ` ` `|` `G/\/ ` ` 2\`|`/2 ` ` \/\H` `|` ` ` ` |
| ` ` ` `|` `*//\ ` ` `1\|/1` ` ` /\\*` `|` ` ` ` |
| ` ` ` `X` `*\ `Y` ` ` `o` ` ` `Y` /*` `Z` ` ` ` |
| ` ` ` `7\ `*\\`|7 ` ` ` ` ` ` 7|`//*` /7` ` ` ` |
| ` ` ` ` 6\`|\\\|6 ` ` ` ` ` ` 6|///|`/6 ` ` ` ` |
| ` ` ` ` `5\|`\\o5 ` ` ` ` ` ` 5o//`|/5` ` ` ` ` |
| ` ` ` ` ` 4o` \o4 ` ` ` ` ` ` 4o/ `o4 ` ` ` ` ` |
| ` ` ` ` ` `3\ `o3 ` ` ` ` ` ` 3o` /3` ` ` ` ` ` |
| ` ` ` ` ` ` 2\`|2 ` ` ` ` ` ` 2|`/2 ` ` ` ` ` ` |
| ` ` ` ` ` ` `1\|1 ` ` ` ` ` ` 1|/1` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `o` ` ` ` ` ` ` `o` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` |
o-------------------------------------------------o
Figure 14-a. F as the Intersection of TE(G) and TE(H)

By way of the representation that is accorded to us in
the medium of these coordinates, we have the following
information about F c X x Y x Z, G c X x Y, H c Y x Z.

F = 4:3:4 + 4:4:4 + 4:5:4

G = 4:3 + 4:4 + 4:5

H = 3:4 + 4:4 + 5:4

Let us now verify that all of the proposed definitions,
formulas, and other relationships check out against the
concrete data of the composition example. The ultimate
goal is to develop a clearer picture of what is going on
in the formula that expresses the relational composition
of 2-adic relations in terms of the extremal projection
of the intersection of their tacit 3-adic extensions:

G o H = Proj_XZ (TE_XY_Z (G) |^| TE_YZ_X (H)).

Here is the big picture, with all of the pieces:

o-------------------------------------------------o
| ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` ` `o` ` ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` ` / \ ` ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` `/` `\` ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` / ` ` \ ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` `/` ` ` `\` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` / ` ` ` ` \ ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` `/` ` ` ` ` `\` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` / ` `G o H` ` \ ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `X` ` ` `*` ` ` `Z` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `7\ ` ` /|\ ` ` /7` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` 6\` `/`|`\` `/6 ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` `5\ / `|` \ /5` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` 4o` `|` `o4 ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` `3\ `|` /3` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` 2\`|`/2 ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` `1\|/1` ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` ` `|` ` ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` ` `|` ` ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` ` `|` ` ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` ` `|` ` ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` ` /|\ ` ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` `/`|`\` ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` / `|` \ ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` `/` `|` `\` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` / ` `|` ` \ ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` `/` ` `|` ` `\` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` / ` ` `|` ` ` \ ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `o` ` ` `|` ` ` `o` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `|\ ` ` /|\ ` ` /|` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `|`\` `/`F`\` `/`|` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `|` \ / `*` \ / `|` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `|` `\` /*\ `/` `|` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `|` / \//*\\/ \ `|` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `|`/` /\/ \/\ `\`|` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `|/ `///\ /\\\` \|` ` ` ` ` ` ` ` |
| ` ` ` `o` ` ` `X` /// `Y` \\\ `Z` ` ` `o` ` ` ` |
| ` ` ` `|\ ` ` `7\///` `|` `\\\/7` ` ` /|` ` ` ` |
| ` ` ` `|`\` ` ` 6// ` `|` ` \\6 ` ` `/`|` ` ` ` |
| ` ` ` `|` \ ` `//5\ ` `|` ` /5\\` ` / `|` ` ` ` |
| ` ` ` `|` `\` /// 4\` `|` `/4 \\\ `/` `|` ` ` ` |
| ` ` ` `|` ` \///` `3\ `|` /3` `\\\/ ` `|` ` ` ` |
| ` ` ` `|` `G/\/ ` ` 2\`|`/2 ` ` \/\H` `|` ` ` ` |
| ` ` ` `|` `*//\ ` ` `1\|/1` ` ` /\\*` `|` ` ` ` |
| ` ` ` `X` `*\ `Y` ` ` `o` ` ` `Y` /*` `Z` ` ` ` |
| ` ` ` `7\ `*\\`|7 ` ` ` ` ` ` 7|`//*` /7` ` ` ` |
| ` ` ` ` 6\`|\\\|6 ` ` ` ` ` ` 6|///|`/6 ` ` ` ` |
| ` ` ` ` `5\|`\\o5 ` ` ` ` ` ` 5o//`|/5` ` ` ` ` |
| ` ` ` ` ` 4o` \o4 ` ` ` ` ` ` 4o/ `o4 ` ` ` ` ` |
| ` ` ` ` ` `3\ `o3 ` ` ` ` ` ` 3o` /3` ` ` ` ` ` |
| ` ` ` ` ` ` 2\`|2 ` ` ` ` ` ` 2|`/2 ` ` ` ` ` ` |
| ` ` ` ` ` ` `1\|1 ` ` ` ` ` ` 1|/1` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `o` ` ` ` ` ` ` `o` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` |
o-------------------------------------------------o
Figure 14-b. G o H = Proj_XZ (TE(G) |^| TE(H))

All that remains to do now is to check the following
set of data and derivations against this last Figure.

• F = 4:3:4 + 4:4:4 + 4:5:4

• G = 4:3 + 4:4 + 4:5

• H = 3:4 + 4:4 + 5:4

• G o H =

(4:3 + 4:4 + 4:5)(3:4 + 4:4 + 5:4) =

4:4

• TE(G) =

TE_XY_Z (G) =

Sum_(z = 1 to 7) (4:3:z + 4:4:z + 4:5:z) =

4:3:1 + 4:4:1 + 4:5:1 +
4:3:2 + 4:4:2 + 4:5:2 +
4:3:3 + 4:4:3 + 4:5:3 +
4:3:4 + 4:4:4 + 4:5:4 +
4:3:5 + 4:4:5 + 4:5:5 +
4:3:6 + 4:4:6 + 4:5:6 +
4:3:7 + 4:4:7 + 4:5:7

• TE(H) =

TE_YZ_X (H) =

Sum_(x = 1 to 7) (x:3:4 + x:4:4 + x:5:4) =

1:3:4 + 1:4:4 + 1:5:4 +
2:3:4 + 2:4:4 + 2:5:4 +
3:3:4 + 3:4:4 + 3:5:4 +
4:3:4 + 4:4:4 + 4:5:4 +
5:3:4 + 5:4:4 + 5:5:4 +
6:3:4 + 6:4:4 + 6:5:4 +
7:3:4 + 7:4:4 + 7:5:4

• TE(G) |^| TE(H) = 4:3:4 + 4:4:4 + 4:5:4

• G o H =

Proj_XZ (TE(G) |^| TE(H)) =

Proj_XZ (4:3:4 + 4:4:4 + 4:5:4) =

4:4

By my lights, anyway, it all checks.

Jon Awbrey

Report this post to a moderator | IP: Logged

04-28-2004 07:40 PM
Jon Awbrey

Registered: Feb 2004
Posts: 551

Reductions Among Relations

RAR. Note 15

4. Relational Composition as Logical Matrix Multiplication

We have it within our reach to pick up another way of representing
2-adic relations, namely, the representation as logical matrices,
and also to grasp the analogy between relational composition and
ordinary matrix multiplication as it appears in linear algebra.

First of all, while we still have the data of a very simple
concrete case in mind, let us reflect on what we did in our
last Example in order to find the composition G o H of the

Here is the set-up that we had before:

X = {1, 2, 3, 4, 5, 6, 7}

G = 4:3 + 4:4 + 4:5 c X x X

H = 3:4 + 4:4 + 5:4 c X x X

Let us recall the rule for finding the relational composition of a pair
of 2-adic relations. Given the 2-adic relations P c X x Y, Q c Y x Z,
the "relational composition" of P and Q, in that order, is commonly
denoted as "P o Q" or more simply as "PQ" and obtained as follows:

To compute PQ, in general, where P and Q are 2-adic relations,
simply multiply out the two sums in the ordinary distributive
algebraic way, only subject to the following rule for finding
the product of two elementary relations of shapes a:b and c:d.

(a:b)(c:d) = (a:d) if b = c,

(a:b)(c:d) = 0 otherwise.

To find the relational composition G o H,
we write it as a quasi-algebraic product:

G o H = (4:3 + 4:4 + 4:5)(3:4 + 4:4 + 5:4).

Multiplying this out in accord with the applicable form
of distributive law one obtains the following expansion:

G o H =

(4:3)(3:4) + (4:3)(4:4) + (4:3)(5:4) +
(4:4)(3:4) + (4:4)(4:4) + (4:4)(5:4) +
(4:5)(3:4) + (4:5)(4:4) + (4:5)(5:4)

Applying the rule that determines the product
of elementary relations, we obtain this array:

G o H =

4:4 + (0) + (0) +
(0) + 4:4 + (0) +
(0) + (0) + 4:4

logical disjunction or set-theoretic aggregation, all positive
multiplicities count as one, and so is rendered the end result:

G o H = 4:4

Jon Awbrey

Last edited by Jon Awbrey on 04-29-2004 at 03:00 PM

Report this post to a moderator | IP: Logged

04-28-2004 09:24 PM