SUO: Re: Projectively Irreducible Triadic Relations
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
Tom,
We need to be clear about one thing before we proceed any further.
We are now talking about the "projective" reducibility of relations,
and this is a weaker sort of reducibility than the "compositional"
reducibility, which is the fundamental type of reduction. You can
tell that it's weaker because it requires a crutch, and the crutch
is shaped like this:
x y
o o
\ /
&
|
o
x&y
For example, when a 3-adic relation L is projectively reducible
to a set of 2-adic relations {L_j}, it doesn't really count as
reducing L to nothing else but the {L_j}, as one is effectively
given a 3-adic relation to use in the construction, namely, the
3-adic relation corresponding to the connective & : B x B -> B,
where B = {0, 1} and "&" is "and".
As always, it remains true that no 3-adic relation can be written
as a composition of 2-adic relations, because 2-adic relations are
closed under relational composition.
To continue ...
o---------------------------------------------------------------------o
| Metable Metabolosis |
o-----------------------------o---------------------------------------o
| Standard Mathematical, | Tom's translation into the language |
| A La Cartesian Language | of relational databases |
o-----------------------------o---------------------------------------o
| k-adic relation | table with k columns |
o-----------------------------o---------------------------------------o
| k-tuple | row of a table with k columns |
o-----------------------------o---------------------------------------o
| relation(s) | table(s) in a relational database |
o-----------------------------o---------------------------------------o
| 1-adic projection | result of a relational PROJECT |
| | operation on a table, that |
| | leaves just one column |
o-----------------------------o---------------------------------------o
| a k-tuple is defined | a row of a table with k columns |
| to be determined by its | is defined to be determined by the |
| 1-adic projection data, | (ordered) set of relational PROJECT |
| but a k-adic relation in | operations, each of which results in |
| general is not determined | a single column instance of the table,|
| by its m-adic projection | but a table with k columns in general |
| data for any m < k. | is not determined by the (ordered) set|
| | of m PROJECT operations on that table,|
| | for any m > k. |
o-----------------------------o---------------------------------------o
> I should be comfortable with Jon's language here, since I am comfortable
> with the language in which the mathematical basis of Codd's relational
> theory is stated. But since I found myself scratching my head over that
> last instance of Jon's language listed above, I thought I'd translate
> into a less rigorous but more comfortable language, that of working
> relational databases. However, it didn't help.
Let's adopt the strategy that has always been recommended to me, picking a few
concrete and simple examples, applying our several forms of language to them,
and trying in this way to see if we are talking about the same things.
Here are some examples of that I have discussed before in this forum.
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
L_0 and L_1. Examples of 2-projectively irreducible 3-adic relations.
The first two relations, L_0 and L_1, are examples of 3-adic relations
that are not reconstructine from their 2-adic projection data, and
so they are called 2-projectively irreducible 3-adic relations.
In this discussion, given a 3-adic relation L c X x Y x Z,
L_XY = p_12 (L) is the 2-adic projection of L on the XY-plane,
L_XZ = p_13 (L) is the 2-adic projection of L on the XZ-plane,
L_YZ = p_23 (L) is the 2-adic projection of L on the YZ-plane.
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 X x Y x Z is isomorphic to B x B x B = B^3.
For lack of a good isomorphism symbol, I will often 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".
| 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 2-adic 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 c B^3 are defined by the following equations,
with algebraic operations taking place 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 B x B and expressible by way of
the universal constant proposition 1 : B x B -> 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".
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
Okay, let's begin by checking whether we have the same concepts
of 1-adic and 2-adic projections as applied to 3-adic relations.
Jon Awbrey
> One problem is "determined by", appearing (twice) in Jon's
> statement and in my paraphrase. What does it mean?
>
> Second problem is the purported demonstration of the claim.
> I just don't follow it.
>
> My own thoughts about the difference between a row of a table (a tuple) and
> the table itself (a relation) is that the former is part of the extension of
> the relation, while the latter (more specifically, the set membership
> conditions which define it) represents the intension of the relation. Next,
> that one cannot always infer the intensional rules from the extensional
> instances because, at any given moment, the set of all those instances may
> not define the boundary conditions of all those rules. To take a simple
> example, if one column of the table is a status-code column, whose domain is
> the letters A - X inclusive, it might be that the status-code value of P is
> not instantiated in any tuple. Or: a column might be defined as nullable,
> although all of the current rows have a value in that column. In short: that
> intensional rules might be inferrable from the full Cartesian Product of a
> set of columns (if we knew it was the full Cartesian Product), but are not
> inferrable from any subset of the full Cartesian Product.
>
> So Jon, can you re-cast your points demonstrating that last claim of yours
> listed above, in my language of working databases? If not, can you give it
> another try in your own language?
>
> Tom
>
> o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
>
> John,
>
> This is the most valiant effort that I have seen so far,
> but the problem with this form of exposition is that it
> tends to focus the learner's attention exclusively on a
> single triple <John, Book, Mary> in the 3-adic relation
> commonly indicated by the rheme "___ gives ___ to ___".
> And no matter how you syntacticize the description or
> graphicize the depiction of that single triple, which
> latter task CG's naturally do beautifully, that triple
> is not the 3-adic relation "Gives", but only a single
> instance of it.
>
> I am very much in favor of "concrete and simple examples" (CASE's).
> But a CASE of something that is not a k-adic relation, but only a
> CASE of a single k-tuple, will be of rather limited use in trying
> to understand what a k-adic relation really is, namely, a subset
> of a k-fold cartesian product, when taken in extension, which is
> the most concrete and most simple way that it can be approached.
>
> In effect, you have presented a case of a CASE of a 3-adic relation, and
> so there is a way to go before giving a CASE of a 3-adic relation itself.
>
> Much of the confusion about the various kinds of reducibility among
> relations arises
> from fixating exclusively on single k-tuples in those relations, instead of
> taking
> the relation, a set of k-tuples, as a whole. The k-tuple has properties
> that the
> k-adic relation does not, and the k-adic relation has properties that the
> k-tuple
> does not, as a moment's reflection is enough to make obvious.
>
> In particular, any single k-tuple x = <x_1, ..., x_k> in the cartesian
> product
> X = X_1 x ... x X_k is reconstructible from the functional results of its
> k projections 1st : X -> X_1, ..., kth : X -> X_k, that is, from the data
> 1st(x), ..., kth(x). Indeed, it is not so surprising that the k-tuple x
> is reconstructible from its k projections, since the k-fold product in
> category theory is constructed in just such a way as to make this so.
>
> These projections correspond to what many people call the "places" or
> "roles"
> in a k-place relation. For example, suppose that x = <John, Book, Mary> is
> a triple in the 3-adic relation G c X = X_1 x X_2 x X_3. Then, we have the
> 3 projections Donor : X -> X_1, Gift : X -> X_2, Recipient : X -> X_3, and
> we have the data that Donor(x) = John, Gift(x) = Book, Recipient(x) = Mary.
> The triple x = <John, Book, Mary> is nothing but the minimal sort of thing
> that is determined by this data.
>
> The projections of the form jth : X -> X_j are the "monadic projections".
> One may also define projections that extract any m-tuple, for m = 1 to k,
> from the k-tuple in a cartesian product. These are "m-adic projections">
>
> For example, if X = X_1 x X_2 x X_3, then we have the "dyadic projections":
>
> p_12 : X -> X_1 x X_2,
>
> p_13 : X -> X_1 x X_3,
>
> p_23 : X -> X_2 x X_3.
>
> Here we have one of the most important divergences in properties between
> a single k-tuple and a k-adic relation, namely, that a k-tuple is defined
> to be determined by its 1-adic projection data, but a k-adic relation in
> general is not determined by its m-adic projection data for any m < k.
>
> I said "in general". As it happens, some, by no means all, k-adic relations
> are determined by their m-adic projection data for certain values of m < k.
> One may call these "m-projectively degenerate k-adic relations".
>
> Hence, nothing but confusion will arise from continuing to extrapolate
> from the properties of k-tuples to the properties of k-adic relations.
>
> Since these issues have constant relevance to enfolding CG and FOL
> representations within the category-theoretic language of IFF, and
> since MacLane begins his text with this very same and this very
> important example of the cartesian product, I will append my
> current collection of links to excerpts from Cat.Work.Math.
>
> Jon Awbrey
>
> o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
>
> CAT. Category Theory -- Ontology List
>
> Introduction
>
> 01. http://suo.ieee.org/ontology/msg04789.html
> 02. http://suo.ieee.org/ontology/msg04790.html
> 03. http://suo.ieee.org/ontology/msg04791.html
> 04. http://suo.ieee.org/ontology/msg04792.html
> 05. http://suo.ieee.org/ontology/msg04793.html
> 06. http://suo.ieee.org/ontology/msg04794.html
> 07. http://suo.ieee.org/ontology/msg04795.html
>
> 1. Categories, Functors, and Natural Transformations
>
> 1.1. Axioms for Categories
>
> 08. http://suo.ieee.org/ontology/msg04796.html
> 09. http://suo.ieee.org/ontology/msg04892.html
> 10. http://suo.ieee.org/ontology/msg04893.html
>
> 1.2. Categories
>
> 11. http://suo.ieee.org/ontology/msg04894.html
> 12. http://suo.ieee.org/ontology/msg04895.html
> 13. http://suo.ieee.org/ontology/msg04896.html
> 14. http://suo.ieee.org/ontology/msg04897.html
> 15. http://suo.ieee.org/ontology/msg04898.html
> 16. http://suo.ieee.org/ontology/msg04899.html
>
> 1.3. Functors
>
> 17. http://suo.ieee.org/ontology/msg04900.html
> 18. http://suo.ieee.org/ontology/msg04901.html
> 19. http://suo.ieee.org/ontology/msg04903.html
> 20. http://suo.ieee.org/ontology/msg04904.html
> 21. http://suo.ieee.org/ontology/msg04905.html
> 22. http://suo.ieee.org/ontology/msg04906.html
>
> 1.4. Natural Transformations
>
> 23. http://suo.ieee.org/ontology/msg04907.html
> 24.
>
> The above material is excerpted from:
>
> | Saunders Mac Lane,
> |'Categories for the Working Mathematician',
> | 2nd edition, Springer, New York, NY, 1997.
>
> o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
>
> John F. Sowa wrote:
> >
> > Rich,
> >
> > I have spent so many years mapping propositions from one
> > notation for logic to another that I automatically "see"
> > the graph structure when I look at a formula in predicate
> > calculus. But after thinking about the problem, I came
> > to realize that many people believe that notations that
> > look different somehow represent things differently.
> >
> > To make the issues clearer, I'll translate the two graphs
> > to predicate calculus. The graph at the top of give.gif
> > maps to the following formula:
> >
> > (Ex)(Person(John) & Book(x) & Person(Mary) & Gives(John,x,Mary)).
> >
> > This uses a common convention of treating names as "constants"
> > and introducing "variables" for things that don't have names.
> > That convention is convenient for arithmetic, but it causes
> > all kinds of trouble with people, who usually have multiple
> > names -- e.g., 'John', 'John Kennedy', 'John F. Kennedy',
> > 'John Fitzgerald Kennedy', 'Jack', 'J. F. Kennedy', 'JFK'...
> > And that doesn't even begin to get into the issues of
> > ambiguities, aliases, etc.
> >
> > So I prefer to assign a variable to every concept node,
> > and to introduce a dyadic predicate to link the variable
> > to the name. This leaves open the question of whether
> > names are ambiguous or unique. It doesn't answer the
> > question, but at least it makes it explicit:
> >
> > (Ex)(Ey)(Ez)(Person(x) & HasName(x,'John') & Book(y)
> > & Person(z) & HasName(z,'Mary') & Gives(x,y,z)}.
> >
> > There we have a triadic relation of type Gives, which
> > has three connections labeled x, y, and z. By an accident
> > of history, those labels are called "variables", but they
> > don't actually vary. That is one of the hardest things
> > to teach beginners: variables in logic don't vary; they
> > are nothing more nor less than labels of connections.
> >
> > By using the same conventions, we can translate the
> > bottom graph to predicate calculus:
> >
> > (Ex)(Ey)(Ez)(Ez)(Person(x) & HasName(x,'John') & Book(y)
> > & Person(z) & HasName(z,'Mary') & Give(w)
> > & Agnt(w,x) & Thme(w,y) & Rcpt(w,z)).
> >
> > Now the triadic relation Gives(x,y,z) has been replaced
> > by a monadic relation Give, and three dyadic relations
> > Agnt, Thme, and Rcpt. But if you look at the graph,
> > there is still a three-way connection. Why?
> >
> > The point is that the fundamental structure of the
> > proposition does not change when you translate it from
> > one notation to another. In order to see the structure,
> > you have to trace through all the connections of all
> > the variables. Following is a little table of connections:
> >
> > x: (Ex), Person(x), HasName(x,'John'), Agnt(w,x)
> >
> > y: (Ey), Book(y), Thme(w,y)
> >
> > z: (Ez), Person(z), HasName(z,'Mary'), Rcpt(w,z)
> >
> > w: (Ew), Give(w), Agnt(w,x), Thme(w,y), Rcpt(w,z)
> >
> > This still doesn't look very clear, and the repetition
> > of predicates in different lines of the table is confusing.
> > So perhaps it would be better if we drew a graph that
> > would show the connections more clearly. That is the
> > graph named givepc.gif.
> >
> > To draw givepc.gif, I made only one copy of each variable,
> > and I attached all the things to that copy that appear
> > on its row of the table above. The graph named givepc.gif
> > is simply the formula in predicate calculus as it would be
> > seen from the point of view of the variables.
> >
> > The structure of the graph now looks very similar to the two
> > CGs in the diagram give.gif, but it looks as if w has 5
> > links attached to it. However, two of those links are not
> > really connections to other "things". One of them links
> > w to the backwards E, which asserts that something labeled w
> > exists, and another one links w to its type Give. Therefore,
> > this graph still has only a triadic connection of "things"
> > to "things".
> >
> > When you translate from one notation to another, all kinds
> > of syntactic features confuse the issue, but the underlying
> > pattern of connections remains the same. That is one reason
> > why Peirce and I and many other people believe that graphs
> > are a more explicit notation for showing the structure
> > of logic.
> >
> > John Sowa
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o