Changes

MyWikiBiz, Author Your Legacy — Friday March 29, 2024
Jump to navigationJump to search
235 bytes added ,  20:16, 24 October 2015
update with TeX formatting
Line 976: Line 976:  
==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"
Line 1,015: Line 1,015:     
These graphs may be read to say:
 
These graphs may be read to say:
:* ''G'' puts 4 in relation to 3, 4, 5.
  −
:* ''H'' puts 3, 4, 5 in relation to 4.
     −
To form the composite relation ''G''&nbsp;&omicron;&nbsp;''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''&nbsp;&omicron;&nbsp;''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:
Line 1,060: Line 1,067:  
|}
 
|}
   −
Once again we find that ''G''&nbsp;&omicron;&nbsp;''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.
Line 1,066: Line 1,073:  
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'',&nbsp;''N''&nbsp;&sube;&nbsp;''X''&nbsp;&times;&nbsp;''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%"
| style="width:20px" | &nbsp;
+
|
| ''M''
+
<math>\begin{array}{*{19}{c}}
| &nbsp;
+
M & = &
| =
+
2\!:\!1 & + & 2\!:\!2 & + & 2\!:\!3 & + & 4\!:\!3 & + & 4\!:\!4 & + & 4\!:\!5 & + & 6\!:\!5 & + & 6\!:\!6 & + & 6\!:\!7
| &nbsp;
+
\\[2pt]
| 2:1
+
N & = &
| +
+
1\!:\!1 & + & 2\!:\!1 & + & 3\!:\!3 & + & 4\!:\!3 & ~ &    +   & ~ & 4\!:\!5 & + & 5\!:\!5 & + & 6\!:\!7 & + & 7\!:\!7
| 2:2
+
\end{array}</math>
| +
  −
| 2:3
  −
| +
  −
| 4:3
  −
| +
  −
| 4:4
  −
| +
  −
| 4:5
  −
| +
  −
| 6:5
  −
| +
  −
| 6:6
  −
| +
  −
| 6:7
  −
|-
  −
| &nbsp;
  −
| ''N''
  −
| &nbsp;
  −
| =
  −
| &nbsp;
  −
| 1:1
  −
| +
  −
| 2:1
  −
| +
  −
| 3:3
  −
| +
  −
| 4:3
  −
| &nbsp;
  −
| +
  −
| &nbsp;
  −
| 4:5
  −
| +
  −
| 5:5
  −
| +
  −
| 6:7
  −
| +
  −
| 7:7
   
|}
 
|}
   Line 1,152: Line 1,122:  
|}
 
|}
   −
To form the composite relation ''M''&nbsp;&omicron;&nbsp;''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''&nbsp;&omicron;&nbsp;''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:
Line 1,196: Line 1,166:  
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''&nbsp;&omicron;&nbsp;''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:
   −
: (''M''&nbsp;&omicron;&nbsp;''N'')<sub>''ij''</sub> = &sum;<sub>''k''</sub>(''M''<sub>''ik''</sub>''N''<sub>''kj''</sub>)
+
{| 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 &sum;<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''&nbsp;&omicron;&nbsp;''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"
Line 1,242: Line 1,214:  
|}
 
|}
   −
In sum, ''N''&nbsp;&omicron;&nbsp;''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., &ldquo;On the Theory of Relational Structures and Schemata for Parallel Computation&rdquo; (1977), pp. 477&ndash;508 in A.R. Bednarek and Françoise Ulam (eds.), ''Analogies Between Analogies : The Mathematical Reports of S.M. Ulam and His Los&nbsp;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&nbsp;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&nbsp;Alamos Collaborators'', A.R. Bednarek and Françoise Ulam (eds.), University of California Press, Berkeley, CA, 1990.
    
==Syllabus==
 
==Syllabus==
12,080

edits

Navigation menu