PlanetMath: algebraic representation of relation composition

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (230)
Orphanage
Unclass'd
Unproven (519)
Corrections (17)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

algebraic representation of relation composition

(Example)

The transition from a geometric picture of relation composition to an algebraic formulation is accomplished through the introduction of coordinates, in other words, identifiable names for the objects that are related through the various forms of relations, 2-adic and 3-adic in the present case. Adding coordinates to the running Example produces the following Figure:

o-------------------------------------------------o
| . . . . . . . . . . . . . . . . . . . . . . . . |
| . . . . . . . . . . . .o. . . . . . . . . . . . |
| . . . . . . . . . . . /|\ . . . . . . . . . . . |
| . . . . . . . . . . ./.|.\. . . . . . . . . . . |
| . . . . . . . . . . / .|. \ . . . . . . . . . . |
| . . . . . . . . . ./. .|. .\. . . . . . . . . . |
| . . . . . . . . . / . .|. . \ . . . . . . . . . |
| . . . . . . . . ./. . .|. . .\. . . . . . . . . |
| . . . . . . . . / . . .|. . . \ . . . . . . . . |
| . . . . . . . .o. . . .o. . . .o. . . . . . . . |
| . . . . . . . .|\ . . / \ . . /|. . . . . . . . |
| . . . . . . . .|.\. ./.F.\. ./.|. . . . . . . . |
| . . . . . . . .|. \ / .*. \ / .|. . . . . . . . |
| . . . . . . . .|. .\. /*\ ./. .|. . . . . . . . |
| . . . . . . . .|. / \//*\\/ \ .|. . . . . . . . |
| . . . . . . . .|./. /\/ \/\ .\.|. . . . . . . . |
| . . . . . . . .|/ .///\ /\\\. \|. . . . . . . . |
| . . . .o. . . .X. /// .Y. \\\ .Z. . . .o. . . . |
| . . . .|\ . . .7\///. .|. .\\\/7. . . /|. . . . |
| . . . .|.\. . . 6// . .|. . \\6 . . ./.|. . . . |
| . . . .|. \ . .//5\ . .|. . /5\\. . / .|. . . . |
| . . . .|. .\. /// 4\. .|. ./4 \\\ ./. .|. . . . |
| . . . .|. . \///. .3\ .|. /3. .\\\/ . .|. . . . |
| . . . .|. . /\/ . . 2\.|./2 . . \/\ . .|. . . . |
| . . . .|. .*//\ . . .1\|/1. . . /\\*. .|. . . . |
| . . . .X. .*/ .Y. . . .o. . . .Y .\*. .Z. . . . |
| . . . .7\ .*. .|7 . . . . . . 7| . *. /7. . . . |
| . . . . 6\.G. .|6 . . . . . . 6| . H /6 . . . . |
| . . . . .5\ . .|5 . . . . . . 5| . ./5. . . . . |
| . . . . . 4\. .|4 . . . . . . 4| . /4 . . . . . |
| . . . . . .3\ .|3 . . . . . . 3| ./3. . . . . . |
| . . . . . . 2\.|2 . . . . . . 2| /2 . . . . . . |
| . . . . . . .1\|1 . . . . . . 1|/1. . . . . . . |
| . . . . . . . .o. . . . . . . .o. . . . . . . . |
| . . . . . . . . . . . . . . . . . . . . . . . . |
o-------------------------------------------------o
Figure 7. F as the Intersection of tau(G) and tau(H)

Thinking of relations in operational terms is facilitated by using a variant notation for tuples and sets of tuples, namely, the ordered pair is written , the ordered triple is written , and so on, and a set of tuples is conceived as a logical-algebraic sum, which can be written out in the smaller finite cases in forms like $a\mathrm{:}b + b\mathrm{:}c + c\mathrm{:}d$ and so on.

For example, translating the relations $F \subseteq X \times Y \times Z$ , $G \subseteq X \times Y$ , $H \subseteq Y \times Z$ into this notation produces the following summary of the data:

$\begin{displaymath}\begin{array}{ccccccc} F & = & 4:3:4 & + & 4:4:4 & + & 4:5:4 ... ...4 & + & 4:5 \ H & = & 3:4 & + & 4:4 & + & 5:4 \ \end{array}\end{displaymath}$

As often happens with abstract notations for functions and relations, the type information, in this case, the fact that and live in different spaces, is left implicit in the context of use.

Let us now verify that all of the proposed definitions, formulas, and other relationships check out against the concrete data of the current 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 a couple of 2-adic relations in terms of the medial projection of the intersection of their tacit extensions:

$G \circ H = \mathrm{proj}_{XZ}(\tau_{XY}^Z(G)\ \cap\ \tau_{YZ}^X(H)).$

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

o-------------------------------------------------o
| . . . . . . . . . . . . . . . . . . . . . . . . |
| . . . . . . . . . . . .o. . . . . . . . . . . . |
| . . . . . . . . . . . / \ . . . . . . . . . . . |
| . . . . . . . . . . ./. .\. . . . . . . . . . . |
| . . . . . . . . . . / . . \ . . . . . . . . . . |
| . . . . . . . . . ./. . . .\. . . . . . . . . . |
| . . . . . . . . . / . . . . \ . . . . . . . . . |
| . . . . . . . . ./. . . . . .\. . . . . . . . . |
| . . . . . . . . / . .G o H. . \ . . . . . . . . |
| . . . . . . . .X. . . .*. . . .Z. . . . . . . . |
| . . . . . . . .7\ . . /|\ . . /7. . . . . . . . |
| . . . . . . . . 6\. ./.|.\. ./6 . . . . . . . . |
| . . . . . . . . .5\ / .|. \ /5. . . . . . . . . |
| . . . . . . . . . 4@. .|. .@4 . . . . . . . . . |
| . . . . . . . . . .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\|.\\@5 . . . . . . 5@// |/5. . . . . |
| . . . . . 4@. \@4 . . . . . . 4@/. @4 . . . . . |
| . . . . . .3\ .@3 . . . . . . 3@ ./3. . . . . . |
| . . . . . . 2\.|2 . . . . . . 2| /2 . . . . . . |
| . . . . . . .1\|1 . . . . . . 1|/1. . . . . . . |
| . . . . . . . .o. . . . . . . .o. . . . . . . . |
| . . . . . . . . . . . . . . . . . . . . . . . . |
o-------------------------------------------------o
Figure 8. G o H = proj_XZ (tau(G) |^| tau(H))

All that remains is to check the following collection of data and derivations against the situation represented in Figure 8.

$\begin{displaymath}\begin{array}{ccccccc} F & = & 4:3:4 & + & 4:4:4 & + & 4:5:4 ... ...4 & + & 4:5 \ H & = & 3:4 & + & 4:4 & + & 5:4 \ \end{array}\end{displaymath}$

$\begin{displaymath}\begin{array}{lcc} G \circ H & = & (4\mbox{:}3 + 4\mbox{:}4 +... ...+ 4\mbox{:}4 + 5\mbox{:}4) \ & = & 4\mbox{:}4 \ \end{array}\end{displaymath}$

$\begin{displaymath}\begin{array}{lcc} \tau(G) & = & \tau_{XY}^Z(G) \ & = & \su... ...}z + 4\mbox{:}4\mbox{:}z + 4\mbox{:}5\mbox{:}z) \ \end{array}\end{displaymath}$

$\begin{displaymath}\begin{array}{lccccccc} \tau(G) & = & 4\mbox{:}3\mbox{:}1 & +... ...4\mbox{:}4\mbox{:}7 & + & 4\mbox{:}5\mbox{:}7 & \ \end{array}\end{displaymath}$

$\begin{displaymath}\begin{array}{lcc} \tau(H) & = & \tau_{YZ}^X(H) \ & = & \su... ...}4 + x\mbox{:}4\mbox{:}4 + x\mbox{:}5\mbox{:}4) \ \end{array}\end{displaymath}$

$\begin{displaymath}\begin{array}{lccccccc} \tau(H) & = & 1\mbox{:}3\mbox{:}4 & +... ...7\mbox{:}4\mbox{:}4 & + & 7\mbox{:}5\mbox{:}4 & \ \end{array}\end{displaymath}$

$\begin{displaymath}\begin{array}{cll} \tau(G) \cap \tau(H) & = & 4\mbox{:}3\mbox... ...4\mbox{:}4 + 4\mbox{:}5\mbox{:}4) \ & = & 4:4 \ \end{array}\end{displaymath}$

"algebraic representation of relation composition" is owned by Jon Awbrey.

(view preamble)

Log in to rate this entry.
(view current ratings)

Cross-references: derivations, collection, place, tacit extensions, projection, composition, current, formulas, definitions, information, functions, finite, ordered pair, tuples, terms, running, relations, objects, coordinates, algebraic, relation composition
There is 1 reference to this entry.

This is version 2 of algebraic representation of relation composition, born on 2008-02-22, modified 2008-02-22.
Object id is 10311, canonical name is AlgebraicRepresentationOfRelationComposition.
Accessed 370 times total.

Classification:

AMS MSC:	03B10 (Mathematical logic and foundations :: General logic :: Classical first-order logic)
	03E20 (Mathematical logic and foundations :: Set theory :: Other classical set theory )
	05B20 (Combinatorics :: Designs and configurations :: Matrices )
	05B30 (Combinatorics :: Designs and configurations :: Other designs, configurations)
	05C65 (Combinatorics :: Graph theory :: Hypergraphs)
	08A02 (General algebraic systems :: Algebraic structures :: Relational systems, laws of composition)
	68P15 (Computer science :: Theory of data :: Database theory)
	68R01 (Computer science :: Discrete mathematics in relation to computer science :: General)

Pending Errata and Addenda

None.

Discussion

forum policy

No messages.

Interact

post | correct | update request | add example | add (any)