12,080
edits
Changes
MyWikiBiz, Author Your Legacy — Sunday April 28, 2024
Jump to navigationJump to searchupdate
<font size="3">☞</font> This page belongs to resource collections on [[Logic Live|Logic]] and [[Inquiry Live|Inquiry]].
<font size="3">☞</font> This page belongs to resource collections on [[Logic Live|Logic]] and [[Inquiry Live|Inquiry]].
'''Relation composition''', or the composition of [[relation (mathematics)|relations]], is the generalization of function composition, or the composition of functions. The following treatment of relation composition takes the “strongly typed” approach to relations that is outlined in the article on [[relation theory]].
==Preliminaries==
==Preliminaries==
There are several ways to formalize the subject matter of relations. Relations and their combinations may be described in the logic of relative terms, in set theories of various kinds, and through a broadening of category theory from functions to relations in general.
The first order of business is to define the operation on [[relation (mathematics)|relations]] that is variously known as the ''composition of relations'', ''relational composition'', or ''relative multiplication''. In approaching the more general constructions, it pays to begin with the composition of dyadic and triadic relations.
The first order of business is to define the operation on [[relation (mathematics)|relations]] that is variously known as the ''composition of relations'', ''relational composition'', or ''relative multiplication''. In approaching the more general constructions, it pays to begin with the composition of dyadic and triadic relations.
|}
|}
Thinking of relations in operational terms is facilitated by using a variant notation for tuples and sets of tuples, namely, the ordered pair (''x'', ''y'') is written ''x'':''y'', the ordered triple (''x'', ''y'', ''z'') is written ''x'':''y'':''z'', 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'':''b'' + ''b'':''c'' + ''c'':''d'' and so on.
Thinking of relations in operational terms is facilitated by using variant notations for ordered tuples and sets of ordered tuples, namely, the ordered pair <math>(x, y)\!</math> is written <math>x\!:\!y,\!</math> the ordered triple <math>(x, y, z)\!</math> is written <math>x\!:\!y\!:\!z,\!</math> 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 <math>a\!:\!b ~+~ b\!:\!c ~+~ c\!:\!d\!</math> and so on.
For example, translating the relations ''F'' ⊆ ''X'' × ''Y'' × ''Z'', ''G'' ⊆ ''X'' × ''Y'', ''H'' ⊆ ''Y'' × ''Z'' into this notation produces the following summary of the data:
For example, translating the relations <math>F \subseteq X \times Y \times Z, ~ G \subseteq X \times Y, ~ H \subseteq Y \times Z\!</math> into this notation produces the following summary of the data:
{| cellpadding=8 style="text-align:center"
{| align="center" cellpadding="8" width="90%"
| || ''F'' || = || 4:3:4 || + || 4:4:4 || + || 4:5:4
|
<math>\begin{matrix}
F & = & 4:3:4 & + & 4:4:4 & + & 4:5:4
\\
G & = & 4:3 & + & 4:4 & + & 4:5
\\
H & = & 3:4 & + & 4:4 & + & 5:4
\end{matrix}</math>
|}
|}
As often happens with abstract notations for functions and relations, the ''type information'', in this case, the fact that ''G'' and ''H'' live in different spaces, is left implicit in the context of use.
As often happens with abstract notations for functions and relations, the ''type information'', in this case, the fact that <math>G\!</math> and <math>H\!</math> 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 dyadic relations in terms of the medial projection of the intersection of their tacit extensions:
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 dyadic relations in terms of the medial projection of the intersection of their tacit extensions:
{| align="center" cellpadding="8" width="90%"
|
<math>G \circ H ~=~ \mathrm{proj}_{XZ} (\mathrm{te}_{XY}^Z (G) ~\cap~ \mathrm{te}_{YZ}^X (H)).\!</math>
|}
Here is the big picture, with all of the pieces in place:
Here is the big picture, with all the pieces in place:
{| align="center" border="0" cellpadding="10"
{| align="center" border="0" cellpadding="10"
|}
|}
All that remains is to check the following collection of data and derivations against the situation represented in Figure 8.
All that remains is to check the following collection of data and derivations against the situation represented in Figure 8.
{| cellpadding=8 style="text-align:center"
{| align="center" cellpadding="8" width="90%"
| || ''F'' || = || 4:3:4 || + || 4:4:4 || + || 4:5:4
|
<math>\begin{matrix}
F & = & 4:3:4 & + & 4:4:4 & + & 4:5:4
\\
G & = & 4:3 & + & 4:4 & + & 4:5
\\
H & = & 3:4 & + & 4:4 & + & 5:4
\end{matrix}</math>
|}
|}
{| cellpadding=8 style="text-align:center"
{| align="center" cellpadding="8" width="90%"
| || ''G'' ο ''H'' || = || (4:3 + 4:4 + 4:5)(3:4 + 4:4 + 5:4)
|
<math>\begin{matrix}
G \circ H & = & (4\!:\!3 ~+~ 4\!:\!4 ~+~ 4\!:\!5)(3\!:\!4 ~+~ 4\!:\!4 ~+~ 5\!:\!4)
\\[6pt]
& = & 4:4
\end{matrix}</math>
|}
|}
{| cellpadding=8 style="text-align:center"
{| align="center" cellpadding="8" width="90%"
| || ''te''(''G'') || = || ''te''<sub>''XY''</sub><sup>''Z''</sup>(''G'')
|
<math>\begin{matrix}
\mathrm{te}(G) & = & \mathrm{te}_{XY}^Z (G)
\\[4pt]
& = & \displaystyle\sum_{z=1}^7 (4\!:\!3\!:\!z ~+~ 4\!:\!4\!:\!z ~+~ 4\!:\!5\!:\!z)
\end{matrix}</math>
|}
|}
{| cellpadding=8 style="text-align:center"
{| align="center" cellpadding="8" width="90%"
| || ''te''(''G'') || = || 4:3:1 || + || 4:4:1 || + || 4:5:1 || +
|
<math>\begin{matrix}
\mathrm{te}(G)
& = & 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
\end{matrix}</math>
|}
|}
{| cellpadding=8 style="text-align:center"
{| align="center" cellpadding="8" width="90%"
| || ''te''(''H'') || = || ''te''<sub>''YZ''</sub><sup>''X''</sup>(''H'')
|
<math>\begin{matrix}
\mathrm{te}(H) & = & \mathrm{te}_{YZ}^X (H)
\\[4pt]
& = & \displaystyle\sum_{x=1}^7 (x\!:\!3\!:\!4 ~+~ x\!:\!4\!:\!4 ~+~ x\!:\!5\!:\!4)
\end{matrix}</math>
|}
|}
{| cellpadding=8 style="text-align:center"
{| align="center" cellpadding="8" width="90%"
| || ''te''(''H'') || = || 1:3:4 || + || 1:4:4 || + || 1:5:4 || +
|
<math>\begin{matrix}
\mathrm{te}(H)
& = & 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
\end{matrix}</math>
|}
|}
{|
{| align="center" cellpadding="8" width="90%"
|
| align="center" | ''te''(''G'') ∩ ''te''(''H'')
<math>\begin{array}{ccl}
\mathrm{te}(G) \cap \mathrm{te}(H)
& = & 4\!:\!3:\!4 ~+~ 4\!:\!4\!:\!4 ~+~ 4\!:\!5\!:\!4
\\[4pt]
G \circ H
& = & \mathrm{proj}_{XZ} (\mathrm{te}(G) \cap \mathrm{te}(H))
\\[4pt]
& = & \mathrm{proj}_{XZ} (4\!:\!3:\!4 ~+~ 4\!:\!4\!:\!4 ~+~ 4\!:\!5\!:\!4)
\\[4pt]
& = & 4:4
\end{array}</math>
|}
|}
==Matrix representation==
==Matrix representation==
We have it within our reach to pick up another way of representing dyadic relations, namely, the representation as [[logical matrix|logical matrices]], and also to grasp the analogy between relational composition and ordinary [[matrix multiplication]] as it appears in [[linear algebra]].
We have it within our reach to pick up another way of representing dyadic relations, namely, the representation as ''[[logical matrix|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'' ο ''H'' of the dyadic relations ''G'' and ''H''.
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 <math>G \circ H\!</math> of the dyadic relations <math>G\!</math> and <math>H.\!</math>
Here is the setup that we had before:
Here is the setup that we had before:
{| cellpadding=8 style="text-align:center"
{| align="center" cellpadding="8" width="90%"
| || ''X'' || = || {1, 2, 3, 4, 5, 6, 7}
| <math>\begin{matrix}X & = & \{ 1, 2, 3, 4, 5, 6, 7 \}\end{matrix}</math>
|}
|}
{| cellpadding=8 style="text-align:center"
{| align="center" cellpadding="8" width="90%"
| || ''G'' || = || 4:3 || + || 4:4 || + || 4:5 || ⊆ || ''X'' × ''X''
|
<math>\begin{matrix}
G & = & 4:3 & + & 4:4 & + & 4:5 & \subseteq & X \times X
\\
H & = & 3:4 & + & 4:4 & + & 5:4 & \subseteq & X \times X
\end{matrix}</math>
|}
|}
Let us recall the rule for finding the relational composition of a pair of dyadic relations. Given the dyadic relations ''P'' ⊆ ''X'' × ''Y'', ''Q'' ⊆ ''Y'' × ''Z'', the relational composition of ''P'' and ''Q'', in that order, is written as ''P'' ο ''Q'' or more simply as ''PQ'' and obtained as follows:
Let us recall the rule for finding the relational composition of a pair of dyadic relations. Given the dyadic relations <math>P \subseteq X \times Y\!</math> and <math>Q \subseteq Y \times Z,\!</math> the composition of <math>P ~\text{on}~ Q\!</math> is written as <math>P \circ Q,\!</math> or more simply as <math>PQ,\!</math> and obtained as follows:
To compute ''PQ'', in general, where ''P'' and ''Q'' are dyadic relations, simply multiply out the two sums in the ordinary distributive algebraic way, but subject to the following rule for finding the product of two elementary relations of shapes ''a'':''b'' and ''c'':''d''.
To compute <math>PQ,\!</math> in general, where <math>P\!</math> and <math>Q\!</math> are dyadic relations, simply multiply out the two sums in the ordinary distributive algebraic way, but subject to the following rule for finding the product of two elementary relations of shapes <math>a:b\!</math> and <math>c:d.\!</math>
{| cellpadding=8 style="text-align:center"
{| align="center" cellpadding="8" width="90%"
| || (a:b)(c:d) || = || (a:d) || if b = c
|
<math>\begin{matrix}
(a:b)(c:d) & = & (a:d) & \text{if}~ b = c
\\
(a:b)(c:d) & = & 0 & \text{otherwise}
\end{matrix}</math>
|}
|}
To find the relational composition ''G'' ο ''H'', one may begin by writing it as a quasi-algebraic product:
To find the relational composition <math>G \circ H,\!</math> one may begin by writing it as a quasi-algebraic product:
{| cellpadding=8 style="text-align:center"
{| align="center" cellpadding="8" width="90%"
| || ''G'' ο ''H'' || = || (4:3 + 4:4 + 4:5)(3:4 + 4:4 + 5:4)
|
<math>\begin{matrix}
G \circ H & = & (4\!:\!3 ~+~ 4\!:\!4 ~+~ 4\!:\!5)(3\!:\!4 ~+~ 4\!:\!4 ~+~ 5\!:\!4)
\end{matrix}</math>
|}
|}
Multiplying this out in accord with the applicable form of distributive law one obtains the following expansion:
Multiplying this out in accord with the applicable form of distributive law one obtains the following expansion:
{| cellpadding=8 style="text-align:center"
{| align="center" cellpadding="8" width="90%"
| || ''G'' ο ''H'' || = || (4:3)(3:4) || + || (4:3)(4:4) || + || (4:3)(5:4) || +
|
<math>\begin{matrix}
G \circ 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)
\end{matrix}</math>
|}
|}
Applying the rule that determines the product of elementary relations produces the following array:
Applying the rule that determines the product of elementary relations produces the following array:
{| cellpadding=8 style="text-align:center"
{| align="center" cellpadding="8" width="90%"
| || ''G'' ο ''H'' || = || (4:4) || + || 0 || + || 0 || +
|
<math>\begin{matrix}
G \circ H
& = & 4:4 & + & 0 & + & 0 & +
\\
& & 0 & + & 4:4 & + & 0 & +
\\
& & 0 & + & 0 & + & 4:4
\end{matrix}</math>
|}
|}
Since the plus sign in this context represents an operation of logical disjunction or set-theoretic aggregation, all of the positive multiplicites count as one, and this gives the ultimate result:
Since the plus sign in this context represents an operation of logical disjunction or set-theoretic aggregation, all of the positive multiplicites count as one, and this gives the ultimate result:
{| cellpadding=8 style="text-align:center"
{| align="center" cellpadding="8" width="90%"
| || ''G'' ο ''H'' || = || (4:4)
| <math>\begin{matrix}G \circ H & = & 4:4\end{matrix}</math>
|}
|}
With an eye toward extracting a general formula for relation composition, viewed here on analogy to algebraic multiplication, let us examine what we did in multiplying the dyadic relations ''G'' and ''H'' together to obtain their relational composite ''G'' o ''H''.
With an eye toward extracting a general formula for relation composition, viewed here on analogy to algebraic multiplication, let us examine what we did in multiplying the dyadic relations <math>G\!</math> and <math>H\!</math> together to obtain their relational composite <math>G \circ H.\!</math>
Given the space ''X'' = {1, 2, 3, 4, 5, 6, 7}, whose cardinality |''X''| is 7, there are |''X'' × ''X''| = |''X''| · |''X''| = 7 · 7 = 49 elementary relations of the form ''i'':''j'', where ''i'' and ''j'' range over the space ''X''. Although they might be organized in many different ways, it is convenient to regard the collection of elementary relations as being arranged in a lexicographic block of the following form:
Given the space <math>X = \{ 1, 2, 3, 4, 5, 6, 7 \},\!</math> whose cardinality <math>|X|\!</math> is <math>7,\!</math> there are <math>|X \times X| = |X| \cdot |X|\!</math> <math>=\!</math> <math>7 \cdot 7 = 49\!</math> elementary relations of the form <math>i:j,\!</math> where <math>i\!</math> and <math>j\!</math> range over the space <math>X.\!</math> Although they might be organized in many different ways, it is convenient to regard the collection of elementary relations as arranged in a lexicographic block of the following form:
{| cellpadding=8 style="text-align:center"
{| align="center" cellpadding="8" width="90%"
| || 1:1 || 1:2 || 1:3 || 1:4 || 1:5 || 1:6 || 1:7
|
<math>\begin{matrix}
1\!:\!1 & 1\!:\!2 & 1\!:\!3 & 1\!:\!4 & 1\!:\!5 & 1\!:\!6 & 1\!:\!7
\\
2\!:\!1 & 2\!:\!2 & 2\!:\!3 & 2\!:\!4 & 2\!:\!5 & 2\!:\!6 & 2\!:\!7
\\
3\!:\!1 & 3\!:\!2 & 3\!:\!3 & 3\!:\!4 & 3\!:\!5 & 3\!:\!6 & 3\!:\!7
\\
4\!:\!1 & 4\!:\!2 & 4\!:\!3 & 4\!:\!4 & 4\!:\!5 & 4\!:\!6 & 4\!:\!7
\\
5\!:\!1 & 5\!:\!2 & 5\!:\!3 & 5\!:\!4 & 5\!:\!5 & 5\!:\!6 & 5\!:\!7
\\
6\!:\!1 & 6\!:\!2 & 6\!:\!3 & 6\!:\!4 & 6\!:\!5 & 6\!:\!6 & 6\!:\!7
\\
7\!:\!1 & 7\!:\!2 & 7\!:\!3 & 7\!:\!4 & 7\!:\!5 & 7\!:\!6 & 7\!:\!7
\end{matrix}</math>
|}
|}
The relations ''G'' and ''H'' may then be regarded as logical sums of the following forms:
The relations <math>G\!</math> and <math>H\!</math> may then be regarded as logical sums of the following forms:
{| cellpadding=8 style="text-align:center"
{| align="center" cellpadding="8" width="90%"
| || ''G'' || = || ∑<sub>''ij''</sub> ''G''<sub>''ij''</sub>(''i'':''j'')
|
<math>\begin{matrix}
G & = & \displaystyle\sum_{ij} G_{ij} (i\!:\!j)
\\[20pt]
H & = & \displaystyle\sum_{ij} H_{ij} (i\!:\!j)
\end{matrix}\!</math>
|}
|}
The notation ∑<sub>''ij''</sub> indicates a logical sum over the collection of elementary relations ''i'':''j'', while the factors ''G''<sub>''ij''</sub> and ''H''<sub>''ij''</sub> are values in the boolean domain '''B''' = {0, 1} that are known as the ''coefficients'' of the relations ''G'' and ''H'', respectively, with regard to the corresponding elementary relations ''i'':''j''.
The notation <math>\textstyle\sum_{ij}\!</math> indicates a logical sum over the collection of elementary relations <math>i\!:\!j\!</math> while the factors <math>G_{ij}\!</math> and <math>H_{ij}\!</math> are values in the ''[[boolean domain]]'' <math>\mathbb{B} = \{ 0, 1 \}~\!</math> that are called the ''coefficients'' of the relations <math>G\!</math> and <math>H,\!</math> respectively, with regard to the corresponding elementary relations <math>i\!:\!j.\!</math>
In general, for a dyadic relation ''L'', the coefficient ''L''<sub>''ij''</sub> of the elementary relation ''i'':''j'' in the relation ''L'' will be 0 or 1, respectively, as ''i'':''j'' is excluded from or included in ''L''.
In general, for a dyadic relation <math>L,\!</math> the coefficient <math>L_{ij}\!</math> of the elementary relation <math>i\!:\!j\!</math> in the relation <math>L\!</math> will be <math>0\!</math> or <math>1,\!</math> respectively, as <math>i\!:\!j\!</math> is excluded from or included in <math>L.\!</math>
With these conventions in place, the expansions of ''G'' and ''H'' may be written out as follows:
With these conventions in place, the expansions of <math>G\!</math> and <math>H\!</math> may be written out as follows:
{| cellpadding=6 style="text-align:center"
{| align="center" cellpadding="4" width="90%"
| || ''G'' || = || 4:3 || + || 4:4 || + || 4:5 || =
|
<math>\begin{matrix}G & = & 4:3 & + & 4:4 & + & 4:5 & =\end{matrix}</math>
|-
|-
|
|
<math>\begin{smallmatrix}
0 \cdot (1:1) & + & 0 \cdot (1:2) & + & 0 \cdot (1:3) & + & 0 \cdot (1:4) & + & 0 \cdot (1:5) & + & 0 \cdot (1:6) & + & 0 \cdot (1:7) & +
\\
0 \cdot (2:1) & + & 0 \cdot (2:2) & + & 0 \cdot (2:3) & + & 0 \cdot (2:4) & + & 0 \cdot (2:5) & + & 0 \cdot (2:6) & + & 0 \cdot (2:7) & +
\\
0 \cdot (3:1) & + & 0 \cdot (3:2) & + & 0 \cdot (3:3) & + & 0 \cdot (3:4) & + & 0 \cdot (3:5) & + & 0 \cdot (3:6) & + & 0 \cdot (3:7) & +
\\
0 \cdot (4:1) & + & 0 \cdot (4:2) & + & \mathbf{1} \cdot (4:3) & + & \mathbf{1} \cdot (4:4) & + & \mathbf{1} \cdot (4:5) & + & 0 \cdot (4:6) & + & 0 \cdot (4:7) & +
\\
0 \cdot (5:1) & + & 0 \cdot (5:2) & + & 0 \cdot (5:3) & + & 0 \cdot (5:4) & + & 0 \cdot (5:5) & + & 0 \cdot (5:6) & + & 0 \cdot (5:7) & +
\\
0 \cdot (6:1) & + & 0 \cdot (6:2) & + & 0 \cdot (6:3) & + & 0 \cdot (6:4) & + & 0 \cdot (6:5) & + & 0 \cdot (6:6) & + & 0 \cdot (6:7) & +
\\
0 \cdot (7:1) & + & 0 \cdot (7:2) & + & 0 \cdot (7:3) & + & 0 \cdot (7:4) & + & 0 \cdot (7:5) & + & 0 \cdot (7:6) & + & 0 \cdot (7:7)
\end{smallmatrix}</math>
|}
|}
{| cellpadding=6 style="text-align:center"
{| align="center" cellpadding="4" width="90%"
| || ''H'' || = || 3:4 || + || 4:4 || + || 5:4 || =
|
<math>\begin{matrix}H & = & 3:4 & + & 4:4 & + & 5:4 & =\end{matrix}</math>
|-
|-
|
|
<math>\begin{smallmatrix}
0 \cdot (1:1) & + & 0 \cdot (1:2) & + & 0 \cdot (1:3) & + & 0 \cdot (1:4) & + & 0 \cdot (1:5) & + & 0 \cdot (1:6) & + & 0 \cdot (1:7) & +
\\
0 \cdot (2:1) & + & 0 \cdot (2:2) & + & 0 \cdot (2:3) & + & 0 \cdot (2:4) & + & 0 \cdot (2:5) & + & 0 \cdot (2:6) & + & 0 \cdot (2:7) & +
\\
0 \cdot (3:1) & + & 0 \cdot (3:2) & + & 0 \cdot (3:3) & + & \mathbf{1} \cdot (3:4) & + & 0 \cdot (3:5) & + & 0 \cdot (3:6) & + & 0 \cdot (3:7) & +
\\
0 \cdot (4:1) & + & 0 \cdot (4:2) & + & 0 \cdot (4:3) & + & \mathbf{1} \cdot (4:4) & + & 0 \cdot (4:5) & + & 0 \cdot (4:6) & + & 0 \cdot (4:7) & +
\\
0 \cdot (5:1) & + & 0 \cdot (5:2) & + & 0 \cdot (5:3) & + & \mathbf{1} \cdot (5:4) & + & 0 \cdot (5:5) & + & 0 \cdot (5:6) & + & 0 \cdot (5:7) & +
\\
0 \cdot (6:1) & + & 0 \cdot (6:2) & + & 0 \cdot (6:3) & + & 0 \cdot (6:4) & + & 0 \cdot (6:5) & + & 0 \cdot (6:6) & + & 0 \cdot (6:7) & +
\\
0 \cdot (7:1) & + & 0 \cdot (7:2) & + & 0 \cdot (7:3) & + & 0 \cdot (7:4) & + & 0 \cdot (7:5) & + & 0 \cdot (7:6) & + & 0 \cdot (7:7)
\end{smallmatrix}</math>
|}
|}
Stripping down to the bare essentials, one obtains the following matrices of coefficients for the relations ''G'' and ''H''.
Stripping down to the bare essentials, one obtains the following matrices of coefficients for the relations <math>G\!</math> and <math>H.\!</math>
{| style="text-align:center; width=30%"
{| align="center" cellpadding="8" width="90%"
| style="width:20px" | || ''G'' || =
|
<math>G ~=~ \begin{pmatrix}
0 & 0 & 0 & 0 & 0 & 0 & 0
\\
0 & 0 & 0 & 0 & 0 & 0 & 0
\\
0 & 0 & 0 & 0 & 0 & 0 & 0
\\
0 & 0 & 1 & 1 & 1 & 0 & 0
\\
0 & 0 & 0 & 0 & 0 & 0 & 0
\\
0 & 0 & 0 & 0 & 0 & 0 & 0
\\
0 & 0 & 0 & 0 & 0 & 0 & 0
\end{pmatrix}</math>
|}
|}
{| style="text-align:center; width=30%"
{| align="center" cellpadding="8" width="90%"
| style="width:20px" | || ''H'' || =
|
<math>H ~=~ \begin{pmatrix}
0 & 0 & 0 & 0 & 0 & 0 & 0
\\
0 & 0 & 0 & 0 & 0 & 0 & 0
\\
0 & 0 & 0 & 1 & 0 & 0 & 0
\\
0 & 0 & 0 & 1 & 0 & 0 & 0
\\
0 & 0 & 0 & 1 & 0 & 0 & 0
\\
0 & 0 & 0 & 0 & 0 & 0 & 0
\\
0 & 0 & 0 & 0 & 0 & 0 & 0
\end{pmatrix}</math>
|}
|}
These are the logical matrix representations of the dyadic relations ''G'' and ''H''.
These are the logical matrix representations of the dyadic relations <math>G\!</math> and <math>H.\!</math>
If the dyadic relations ''G'' and ''H'' are viewed as logical sums, then their relational composition ''G'' ο ''H'' can be regarded as a product of sums, a fact that can be indicated as follows:
If the dyadic relations <math>G\!</math> and <math>H\!</math> are viewed as logical sums then their relational composition <math>G \circ H\!</math> can be regarded as a product of sums, a fact that can be indicated as follows:
{| align="center" cellpadding="8" width="90%"
| <math>G \circ H ~=~ (\sum_{ij} G_{ij} (i\!:\!j))(\sum_{ij} H_{ij} (i\!:\!j)).\!</math>
|}
The composite relation ''G'' ο ''H'' is itself a dyadic relation over the same space ''X'', in other words, ''G'' ο ''H'' ⊆ ''X'' × ''X'', and this means that ''G'' ο ''H'' must be amenable to being written as a logical sum of the following form:
The composite relation <math>G \circ H\!</math> is itself a dyadic relation over the same space <math>X,\!</math> in other words, <math>G \circ H \subseteq X \times X,\!</math> and this means that <math>G \circ H\!</math> must be amenable to being written as a logical sum of the following form:
{| align="center" cellpadding="8" width="90%"
| <math>G \circ H ~=~ \sum_{ij} (G \circ H)_{ij} (i\!:\!j).\!</math>
|}
In this formula, (''G'' ο ''H'')<sub>''ij''</sub> is the coefficient of ''G'' ο ''H'' with respect to the elementary relation ''i'':''j''.
In this formula, <math>(G \circ H)_{ij}\!</math> is the coefficient of <math>G \circ H\!</math> with respect to the elementary relation <math>i\!:\!j.\!</math>
One of the best ways to reason out what ''G'' ο ''H'' should be is to ask oneself what its coefficient (''G'' ο ''H'')<sub>''ij''</sub> should be for each of the elementary relations ''i'':''j'' in turn.
One of the best ways to reason out what <math>G \circ H\!</math> should be is to ask oneself what its coefficient <math>(G \circ H)_{ij}\!</math> should be for each of the elementary relations <math>i\!:\!j\!</math> in turn.
So let us pose the question:
So let us pose the question:
{| align="center" cellpadding="8" width="90%"
| <math>(G \circ H)_{ij} ~=~ ?\!</math>
|}
In order to answer this question, it helps to realize that the indicated product given above can be written in the following equivalent form:
In order to answer this question, it helps to realize that the indicated product given above can be written in the following equivalent form:
{| align="center" cellpadding="8" width="90%"
| <math>G \circ H ~=~ (\sum_{ik} G_{ik} (i\!:\!k))(\sum_{kj} H_{kj} (k\!:\!j)).\!</math>
|}
A moment's thought will tell us that (''G'' ο ''H'')<sub>''ij''</sub> = 1 if and only if there is an element ''k'' in ''X'' such that ''G''<sub>''ik''</sub> = 1 and ''H''<sub>''kj''</sub> = 1.
A moment's thought will tell us that <math>(G \circ H)_{ij} = 1\!</math> if and only if there is an element <math>k\!</math> in <math>X\!</math> such that <math>G_{ik} = 1\!</math> and <math>H_{kj} = 1.\!</math>
Consequently, we have the result:
Consequently, we have the result:
{| align="center" cellpadding="8" width="90%"
| <math>(G \circ H)_{ij} ~=~ \sum_{k} G_{ik} H_{kj}.\!</math>
|}
This follows from the properties of boolean arithmetic, specifically, from the fact that the product ''G''<sub>''ik''</sub>''H''<sub>''kj''</sub> is 1 if and only if both ''G''<sub>''ik''</sub> and ''H''<sub>''kj''</sub> are 1, and from the fact that ∑<sub>''k''</sub> ''F''<sub>''k''</sub> is equal to 1 just in case some ''F''<sub>''k''</sub> is 1.
This follows from the properties of boolean arithmetic, specifically, from the fact that the product <math>G_{ik} H_{kj}\!</math> is <math>1\!</math> if and only if both <math>G_{ik}\!</math> and <math>H_{kj}\!</math> are <math>1\!</math> and from the fact that <math>\textstyle\sum_{k} F_{k}\!</math> is equal to <math>1\!</math> just in case some <math>F_{k}\!</math> is <math>1.\!</math>
All that remains in order to obtain a computational formula for the relational composite ''G'' ο ''H'' of the dyadic relations ''G'' and ''H'' is to collect the coefficients (''G'' ο ''H'')<sub>''ij''</sub> over the appropriate basis of elementary relations ''i'':''j'', as ''i'' and ''j'' range through ''X''.
All that remains in order to obtain a computational formula for the relational composite <math>G \circ H\!</math> of the dyadic relations <math>G\!</math> and <math>H\!</math> is to collect the coefficients <math>(G \circ H)_{ij}\!</math> as <math>i\!</math> and <math>j\!</math> range over <math>X.\!</math>
{| align="center" cellpadding="8" width="90%"
|
<math>\begin{matrix}G \circ H
& = & \displaystyle \sum_{ij} (G \circ H)_{ij} (i\!:\!j)
& = & \displaystyle \sum_{ij} (\sum_{k} G_{ik} H_{kj}) (i\!:\!j).
\end{matrix}</math>
|}
This is the logical analogue of matrix multiplication in linear algebra, the difference in the logical setting being that all of the operations performed on coefficients take place in a system of boolean arithmetic where summation corresponds to logical disjunction and multiplication corresponds to logical conjunction.
This is the logical analogue of matrix multiplication in linear algebra, the difference in the logical setting being that all of the operations performed on coefficients take place in a system of boolean arithmetic where summation corresponds to logical disjunction and multiplication corresponds to logical conjunction.
By way of disentangling this formula, one may notice that the form ∑<sub>''k''</sub> (''G''<sub>''ik''</sub>''H''<sub>''kj''</sub>) is what is usually called a "scalar product". In this case it is the scalar product of the ''i''<sup>th</sup> row of ''G'' with the ''j''<sup>th</sup> column of ''H''.
By way of disentangling this formula, one may notice that the form <math>\textstyle \sum_{k} G_{ik} H_{kj}\!</math> is what is usually called a ''scalar product''. In this case it is the scalar product of the <math>i^\text{th}\!</math> row of <math>G\!</math> with the <math>j^\text{th}\!</math> column of <math>H.\!</math>
To make this statement more concrete, let us go back to the particular examples of ''G'' and ''H'' that we came in with:
To make this statement more concrete, let us go back to the examples of <math>G\!</math> and <math>H\!</math> we came in with:
{| style="text-align:center; width=30%"
{| align="center" cellpadding="8" width="90%"
| style="width:20px" | || ''G'' || =
|
<math>G ~=~ \begin{pmatrix}
0 & 0 & 0 & 0 & 0 & 0 & 0
\\
0 & 0 & 0 & 0 & 0 & 0 & 0
\\
0 & 0 & 0 & 0 & 0 & 0 & 0
\\
0 & 0 & 1 & 1 & 1 & 0 & 0
\\
0 & 0 & 0 & 0 & 0 & 0 & 0
\\
0 & 0 & 0 & 0 & 0 & 0 & 0
\\
0 & 0 & 0 & 0 & 0 & 0 & 0
\end{pmatrix}</math>
|}
|}
{| style="text-align:center; width=30%"
{| align="center" cellpadding="8" width="90%"
| style="width:20px" | || ''H'' || =
|
<math>H ~=~ \begin{pmatrix}
0 & 0 & 0 & 0 & 0 & 0 & 0
\\
0 & 0 & 0 & 0 & 0 & 0 & 0
\\
0 & 0 & 0 & 1 & 0 & 0 & 0
\\
0 & 0 & 0 & 1 & 0 & 0 & 0
\\
0 & 0 & 0 & 1 & 0 & 0 & 0
\\
0 & 0 & 0 & 0 & 0 & 0 & 0
\\
0 & 0 & 0 & 0 & 0 & 0 & 0
\end{pmatrix}</math>
|}
|}
The formula for computing ''G'' ο ''H'' says the following:
The formula for computing <math>G \circ H\!</math> says the following:
{| cellpadding="2"
{| align="center" cellpadding="8" width="90%"
|
<math>\begin{array}{ccl}
(G \circ H)_{ij}
& = & \text{the}~ {ij}^\text{th} ~\text{entry in the matrix representation for}~ G \circ H
\\[2pt]
& = & \text{the entry in the}~ {i}^\text{th} ~\text{row and the}~ {j}^\text{th} ~\text{column of}~ G \circ H
\\[2pt]
& = & \text{the scalar product of the}~ {i}^\text{th} ~\text{row of}~ G ~\text{with the}~ {j}^\text{th} ~\text{column of}~ H
\\[2pt]
& = & \sum_{k} G_{ik} H_{kj}
\end{array}</math>
|}
|}
As it happens, it is possible to make exceedingly light work of this example, since there is only one row of ''G'' and one column of ''H'' that are not all zeroes. Taking the scalar product, in a logical way, of the fourth row of ''G'' with the fourth column of ''H'' produces the sole non-zero entry for the matrix of ''G'' ο ''H''.
As it happens, it is possible to make exceedingly light work of this example, since there is only one row of <math>G\!</math> and one column of <math>H\!</math> that are not all zeroes. Taking the scalar product, in a logical way, of the fourth row of <math>G\!</math> with the fourth column of <math>H\!</math> produces the sole non-zero entry for the matrix of <math>G \circ H.\!</math>
{| cellpadding="2px" style="text-align:center"
{| align="center" cellpadding="8" width="90%"
|
<math>G \circ H ~=~ \begin{pmatrix}
0 & 0 & 0 & 0 & 0 & 0 & 0
\\
0 & 0 & 0 & 0 & 0 & 0 & 0
\\
0 & 0 & 0 & 0 & 0 & 0 & 0
\\
0 & 0 & 0 & 1 & 0 & 0 & 0
\\
0 & 0 & 0 & 0 & 0 & 0 & 0
\\
0 & 0 & 0 & 0 & 0 & 0 & 0
\\
0 & 0 & 0 & 0 & 0 & 0 & 0
\end{pmatrix}</math>
|}
|}
==Graph-theoretic picture==
==Graph-theoretic picture==
There is another form of representation for dyadic relations that is useful to keep in mind, especially for its ability to render the logic of many complex formulas almost instantly understandable to the mind's eye. This is the representation in terms of ''[[bipartite graph]]s'', or ''bigraphs'' for short.
There is another form of representation for dyadic relations that is useful to keep in mind, especially for its ability to render the logic of many complex formulas almost instantly understandable to the mind's eye. This is the representation in terms of ''bipartite graphs'', or ''bigraphs'' for short.
Here is what ''G'' and ''H'' look like in the bigraph picture:
Here is what <math>G\!</math> and <math>H\!</math> look like in the bigraph picture:
{| align="center" border="0" cellpadding="10"
{| align="center" border="0" cellpadding="10"
These graphs may be read to say:
These graphs may be read to say:
To form the composite relation ''G'' ο ''H'', one simply follows the bigraph for ''G'' by the bigraph for ''H'', here arranging the bigraphs in order down the page, and then treats any non-empty set of paths of length two between two nodes as being equivalent to a single directed edge between those nodes in the composite bigraph for ''G'' ο ''H''.
{| align="center" cellpadding="8" width="90%"
|
<math>\begin{matrix}
G ~\text{puts}~ 4 ~\text{in relation to}~ 3, 4, 5.
\\[2pt]
H ~\text{puts}~ 3, 4, 5 ~\text{in relation to}~ 4.
\end{matrix}</math>
|}
To form the composite relation <math>G \circ H,\!</math> one simply follows the bigraph for <math>G\!</math> by the bigraph for <math>H,\!</math> here arranging the bigraphs in order down the page, and then treats any non-empty set of paths of length two between two nodes as being equivalent to a single directed edge between those nodes in the composite bigraph for <math>G \circ H.\!</math>
Here's how it looks in pictures:
Here's how it looks in pictures:
|}
|}
Once again we find that ''G'' ο ''H'' = 4:4.
Once again we find that <math>G \circ H = 4:4.\!</math>
We have now seen three different representations of dyadic relations. If one has a strong preference for letters, or numbers, or pictures, then one may be tempted to take one or another of these as being canonical, but each of them will be found to have its peculiar advantages and disadvantages in any given application, and the maximum advantage is therefore approached by keeping all three of them in mind.
We have now seen three different representations of dyadic relations. If one has a strong preference for letters, or numbers, or pictures, then one may be tempted to take one or another of these as being canonical, but each of them will be found to have its peculiar advantages and disadvantages in any given application, and the maximum advantage is therefore approached by keeping all three of them in mind.
To see the promised utility of the bigraph picture of dyadic relations, let us devise a slightly more complex example of a composition problem, and use it to illustrate the logic of the matrix multiplication formula.
To see the promised utility of the bigraph picture of dyadic relations, let us devise a slightly more complex example of a composition problem, and use it to illustrate the logic of the matrix multiplication formula.
Keeping to the same space ''X'' = {1, 2, 3, 4, 5, 6, 7}, define the dyadic relations ''M'', ''N'' ⊆ ''X'' × ''X'' as follows:
Keeping to the same space <math>X = \{ 1, 2, 3, 4, 5, 6, 7 \},\!</math> define the dyadic relations <math>M, N \subseteq X \times X\!</math> as follows:
{| cellpadding="2px" style="text-align:center"
{| align="center" cellpadding="8" width="90%"
|
<math>\begin{array}{*{19}{c}}
M & = &
2\!:\!1 & + & 2\!:\!2 & + & 2\!:\!3 & + & 4\!:\!3 & + & 4\!:\!4 & + & 4\!:\!5 & + & 6\!:\!5 & + & 6\!:\!6 & + & 6\!:\!7
\\[2pt]
N & = &
1\!:\!1 & + & 2\!:\!1 & + & 3\!:\!3 & + & 4\!:\!3 & ~ & + & ~ & 4\!:\!5 & + & 5\!:\!5 & + & 6\!:\!7 & + & 7\!:\!7
\end{array}</math>
|}
|}
|}
|}
To form the composite relation ''M'' ο ''N'', one simply follows the bigraph for ''M'' by the bigraph for ''N'', here arranging the bigraphs in order down the page, and then counts any non-empty set of paths of length two between two nodes as being equivalent to a single directed edge between those two nodes in the composite bigraph for ''M'' ο ''N''.
To form the composite relation <math>M \circ N,\!</math> one simply follows the bigraph for <math>M\!</math> by the bigraph for <math>N,\!</math> arranging the bigraphs in order down the page, and then counts any non-empty set of paths of length two between two nodes as being equivalent to a single directed edge between those two nodes in the composite bigraph for <math>M \circ N.\!</math>
Here's how it looks in pictures:
Here's how it looks in pictures:
Let us hark back to that mysterious matrix multiplication formula, and see how it appears in the light of the bigraph representation.
Let us hark back to that mysterious matrix multiplication formula, and see how it appears in the light of the bigraph representation.
The coefficient of the composition ''M'' ο ''N'' between ''i'' and ''j'' in ''X'' is given as follows:
The coefficient of the composition <math>M \circ N\!</math> between <math>i\!</math> and <math>j\!</math> in <math>X\!</math> is given as follows:
{| align="center" cellpadding="8" width="90%"
| <math>(M \circ N)_{ij} ~=~ \sum_{k} M_{ik} N_{kj}\!</math>
|}
Graphically interpreted, this is a ''sum over paths''. Starting at the node ''i'', ''M''<sub>''ik''</sub> being 1 indicates that there is an edge in the bigraph of ''M'' from node ''i'' to node ''k'', and ''N''<sub>''kj''</sub> being 1 indicates that there is an edge in the bigraph of ''N'' from node ''k'' to node ''j''. So the ∑<sub>''k''</sub> ranges over all possible intermediaries ''k'', ascending from 0 to 1 just as soon as there happens to be some path of length two between nodes ''i'' and ''j''.
Graphically interpreted, this is a ''sum over paths''. Starting at the node <math>i,\!</math> <math>M_{ik}\!</math> being <math>1\!</math> indicates that there is an edge in the bigraph of <math>M\!</math> from node <math>i\!</math> to node <math>k\!</math> and <math>N_{kj}\!</math> being <math>1\!</math> indicates that there is an edge in the bigraph of <math>N\!</math> from node <math>k\!</math> to node <math>j.\!</math> So the <math>\textstyle\sum_{k}\!</math> ranges over all possible intermediaries <math>k,\!</math> ascending from <math>0\!</math> to <math>1\!</math> just as soon as there happens to be a path of length two between nodes <math>i\!</math> and <math>j.\!</math>
It is instructive at this point to compute the other possible composition that can be formed from ''M'' and ''N'', namely, the composition ''N'' ο ''M'', that takes ''M'' and ''N'' in the opposite order. Here is the graphic computation:
It is instructive at this point to compute the other possible composition that can be formed from <math>M\!</math> and <math>N,\!</math> namely, the composition <math>N \circ M,\!</math> that takes <math>M\!</math> and <math>N\!</math> in the opposite order. Here is the graphic computation:
{| align="center" border="0" cellpadding="10"
{| align="center" border="0" cellpadding="10"
|}
|}
In sum, ''N'' ο ''M'' = 0. This example affords sufficient evidence that relational composition, just like its kindred, matrix multiplication, is a ''[[non-commutative]]'' algebraic operation.
In sum, <math>N \circ M = 0.\!</math> This example affords sufficient evidence that relational composition, just like its kindred, matrix multiplication, is a ''non-commutative'' algebraic operation.
==References==
==References==
* [[Stanislaw Marcin Ulam|Ulam, S.M.]] and [[Al Bednarek|Bednarek, A.R.]], "On the Theory of Relational Structures and Schemata for Parallel Computation" (1977), pp. 477-508 in A.R. Bednarek and Françoise Ulam (eds.), ''Analogies Between Analogies: The Mathematical Reports of S.M. Ulam and His Los Alamos Collaborators'', University of California Press, Berkeley, CA, 1990.
* Ulam, S.M., and Bednarek, A.R., “On the Theory of Relational Structures and Schemata for Parallel Computation” (1977), pp. 477–508 in A.R. Bednarek and Françoise Ulam (eds.), ''Analogies Between Analogies : The Mathematical Reports of S.M. Ulam and His Los Alamos Collaborators'', University of California Press, Berkeley, CA, 1990.
==Bibliography==
==Bibliography==
* [[Mathematical Society of Japan]], ''Encyclopedic Dictionary of Mathematics'', 2nd edition, 2 vols., Kiyosi Itô (ed.), MIT Press, Cambridge, MA, 1993.
* Mathematical Society of Japan, ''Encyclopedic Dictionary of Mathematics'', 2nd edition, 2 volumes., Kiyosi Itô (ed.), MIT Press, Cambridge, MA, 1993.
* Mili, A., Desharnais, J., Mili, F., with Frappier, M., ''Computer Program Construction'', Oxford University Press, New York, NY, 1994. — Introduction to Tarskian relation theory and its applications within the relational programming paradigm.
* Mili, A., Desharnais, J., Mili, F., with Frappier, M., ''Computer Program Construction'', Oxford University Press, New York, NY, 1994.
* [[Stanislaw Marcin Ulam|Ulam, S.M.]], ''Analogies Between Analogies: The Mathematical Reports of S.M. Ulam and His Los Alamos Collaborators'', A.R. Bednarek and Françoise Ulam (eds.), University of California Press, Berkeley, CA, 1990.
* Ulam, S.M., ''Analogies Between Analogies : The Mathematical Reports of S.M. Ulam and His Los Alamos Collaborators'', A.R. Bednarek and Françoise Ulam (eds.), University of California Press, Berkeley, CA, 1990.
==Syllabus==
==Syllabus==
===Focal nodes===
===Focal nodes===
* [[Inquiry Live]]
* [[Inquiry Live]]
* [[Logic Live]]
* [[Logic Live]]
===Peer nodes===
===Peer nodes===
* [http://intersci.ss.uci.edu/wiki/index.php/Relation_composition Relation Composition @ InterSciWiki]
* [http://intersci.ss.uci.edu/wiki/index.php/Relation_composition Relation Composition @ InterSciWiki]
* [http://mywikibiz.com/Relation_composition Relation Composition @ MyWikiBiz]
* [http://mywikibiz.com/Relation_composition Relation Composition @ MyWikiBiz]
* [http://ref.subwiki.org/wiki/Relation_composition Relation Composition @ Subject Wikis]
* [http://en.wikiversity.org/wiki/Relation_composition Relation Composition @ Wikiversity]
* [http://beta.wikiversity.org/wiki/Relation_composition Relation Composition @ Wikiversity Beta]
* [http://beta.wikiversity.org/wiki/Relation_composition Relation Composition @ Wikiversity Beta]
===Logical operators===
===Logical operators===
Portions of the above article were adapted from the following sources under the [[GNU Free Documentation License]], under other applicable licenses, or by permission of the copyright holders.
Portions of the above article were adapted from the following sources under the [[GNU Free Documentation License]], under other applicable licenses, or by permission of the copyright holders.
* [http://intersci.ss.uci.edu/wiki/index.php/Relation_composition Relation Composition], [http://intersci.ss.uci.edu/ InterSciWiki]
* [http://mywikibiz.com/Relation_composition Relation Composition], [http://mywikibiz.com/ MyWikiBiz]
* [http://mywikibiz.com/Relation_composition Relation Composition], [http://mywikibiz.com/ MyWikiBiz]
* [http://semanticweb.org/wiki/Relation_composition Relation Composition], [http://semanticweb.org/ Semantic Web]
* [http://semanticweb.org/wiki/Relation_composition Relation Composition], [http://semanticweb.org/ Semantic Web]
* [http://ref.subwiki.org/wiki/Relation_composition Relation Composition], [http://ref.subwiki.org/ Subject Wikis]
* [http://planetmath.org/RelationComposition Relation Composition], [http://planetmath.org/ PlanetMath]
* [http://wikinfo.org/w/index.php/Relation_composition Relation Composition], [http://wikinfo.org/w/ Wikinfo]
* [http://en.wikiversity.org/wiki/Relation_composition Relation Composition], [http://en.wikiversity.org/ Wikiversity]
* [http://beta.wikiversity.org/wiki/Relation_composition Relation Composition], [http://beta.wikiversity.org/ Wikiversity Beta]
* [http://en.wikipedia.org/w/index.php?title=Relation_composition&oldid=43467878 Relation Composition], [http://en.wikipedia.org/ Wikipedia]
* [http://en.wikipedia.org/w/index.php?title=Relation_composition&oldid=43467878 Relation Composition], [http://en.wikipedia.org/ Wikipedia]
[[Category:Combinatorics]]
[[Category:Combinatorics]]
