ONT Re: Reductions Among Relations
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
RAR. Note 5
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
Projective Reduction of Triadic Relations (cont.)
Projectively Irreducible Triadic Relations, or
Triadic Relations Irreducible Over Projections:
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.
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 pairs
| of the form <x, y> in X x Y:
|
| <0, 0>
| <0, 1>
| <1, 0>
| <1, 1>
| (L_0)_XZ has these four pairs
| of the form <x, z> in X x Z:
|
| <0, 0>
| <0, 1>
| <1, 1>
| <1, 0>
| (L_0)_YZ has these four pairs
| of the form <y, z> in Y x Z:
|
| <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 pairs
| of the form <x, y> in X x Y:
|
| <0, 0>
| <0, 1>
| <1, 0>
| <1, 1>
| (L_1)_XZ has these four pairs
| of the form <x, z> in X x Z:
|
| <0, 1>
| <0, 0>
| <1, 0>
| <1, 1>
| (L_1)_YZ 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 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 form an indiscernible couplet
of "triadic relations irreducible over projections"
or "projectively irreducible triadic relations".
Jon Awbrey
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o