12,080
edits
Changes
MyWikiBiz, Author Your Legacy — Thursday April 18, 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]].
In [[logic]] and [[mathematics]], '''relation composition''', or the composition of [[relation (mathematics)|relations]], is the generalization of [[function composition]], or the composition of [[function (mathematics)|functions]].
In logic and mathematics, '''relation composition''', or the composition of [[relation (mathematics)|relations]], is the generalization of function composition, or the composition of functions.
==Preliminaries==
==Preliminaries==
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 2-adic and 3-adic 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 2-adic and 3-adic relations.
As an incidental observation on usage, there are many different conventions of [[syntax]] for denoting the application and composition of relations, with perhaps even more options in general use than are common for the application and composition of [[function (mathematics)|functions]]. In this case there is little chance of standardization, since the convenience of conventions is relative to the context of use, and the same writers use different styles of syntax in different settings, depending on the ease of analysis and computation.
As an incidental observation on usage, there are many different conventions of syntax for denoting the application and composition of relations, with perhaps even more options in general use than are common for the application and composition of functions. In this case there is little chance of standardization, since the convenience of conventions is relative to the context of use, and the same writers use different styles of syntax in different settings, depending on the ease of analysis and computation.
{| align="center" cellpadding="4" width="90%"
{| align="center" cellpadding="4" width="90%"
|-
|-
|
|
<p>The second dimension of variation in syntax has to do with the automatic assumptions in place about the associations of terms in the absence of associations marked by parentheses. This becomes a significant factor with relations in general because the usual property of [[associativity]] is lost as both the complexities of compositions and the dimensions of relations increase.</p>
<p>The second dimension of variation in syntax has to do with the automatic assumptions in place about the associations of terms in the absence of associations marked by parentheses. This becomes a significant factor with relations in general because the usual property of associativity is lost as both the complexities of compositions and the dimensions of relations increase.</p>
|}
|}
|}
|}
Note on notation. The ordinary symbol for functional composition is the ''[[composition sign]]'', a small circle "<math>\circ</math>" written between the names of the functions being composed, as <math>f \circ g,</math> but the sign is often omitted if there is no risk of confusing the composition of functions with their algebraic product. In contexts where both compositions and products occur, either the composition is marked on each occasion or else the product is marked by means of a ''center dot'' "<math>\cdot</math>", as <math>f \cdot g.</math>
Note on notation. The ordinary symbol for functional composition is the ''composition sign'', a small circle "<math>\circ</math>" written between the names of the functions being composed, as <math>f \circ g,</math> but the sign is often omitted if there is no risk of confusing the composition of functions with their algebraic product. In contexts where both compositions and products occur, either the composition is marked on each occasion or else the product is marked by means of a ''center dot'' "<math>\cdot</math>", as <math>f \cdot g.</math>
Generalizing the paradigm along parallel lines, the ''composition'' of a pair of 2-adic relations is formulated in the following two ways:
Generalizing the paradigm along parallel lines, the ''composition'' of a pair of 2-adic relations is formulated in the following two ways:
==Geometric construction==
==Geometric construction==
There is a neat way of defining relational compositions in geometric terms, not only showing their relationship to the [[projection (set theory)|projection]] operations that come with any [[cartesian product]], but also suggesting natural directions for generalizing relational compositions beyond the 2-adic case, and even beyond relations that have any fixed [[arity]], in effect, to the general case of [[formal language]]s as generalized relations.
There is a neat way of defining relational compositions in geometric terms, not only showing their relationship to the projection operations that come with any cartesian product, but also suggesting natural directions for generalizing relational compositions beyond the 2-adic case, and even beyond relations that have any fixed arity, in effect, to the general case of formal languages as generalized relations.
This way of looking at relational compositions is sometimes referred to as [[Alfred Tarski|Tarski]]'s Trick (T<sup>2</sup>), on account of his having put it to especially good use in his work (Ulam and Bednarek, 1977). It supplies the imagination with a geometric way of visualizing the relational composition of a pair of 2-adic relations, doing this by attaching concrete imagery to the basic [[set theory|set-theoretic]] operations, namely, [[intersection (set theory)|intersection]]s, [[projection (set theory)|projection]]s, and a certain class of operations [[inverse relation|inverse]] to projections, here called ''[[tacit extension]]s''.
This way of looking at relational compositions is sometimes referred to as Tarski's Trick, on account of his having put it to especially good use in his work (Ulam and Bednarek, 1977). It supplies the imagination with a geometric way of visualizing the relational composition of a pair of 2-adic relations, doing this by attaching concrete imagery to the basic set-theoretic operations, namely, intersections, projections, and a certain class of operations inverse to projections, here called ''tacit extensions''.
The stage is set for Tarski's trick by highlighting the links between two topics that are likely to appear wholly unrelated at first, namely:
The stage is set for Tarski's trick by highlighting the links between two topics that are likely to appear wholly unrelated at first, namely:
:* The use of logical [[conjunction]], as denoted by the symbol "∧" in expressions of the form ''F''(''x'', ''y'', ''z'') = ''G''(''x'', ''y'') ∧ ''H''(''y'', ''z''), to define a 3-adic relation ''F'' in terms of a pair of 2-adic relations ''G'' and ''H''.
:* The use of [[logical conjunction]], as denoted by the symbol "∧" in expressions of the form ''F''(''x'', ''y'', ''z'') = ''G''(''x'', ''y'') ∧ ''H''(''y'', ''z''), to define a 3-adic relation ''F'' in terms of a pair of 2-adic relations ''G'' and ''H''.
:* The concepts of 2-adic ''[[projection (set theory)|projection]]'' and ''projective determination'', that are invoked in the 'weak' notion of ''projective reducibility''.
:* The concepts of 2-adic ''projection'' and ''projective determination'', that are invoked in the “weak” notion of ''projective reducibility''.
The relational composition ''G'' ο ''H'' of a pair of 2-adic relations ''G'' and ''H'' will be constructed in three stages, first, by taking the tacit extensions of ''G'' and ''H'' to 3-adic relations that reside in the same space, next, by taking the intersection of these extensions, tantamount to the maximal 3-adic relation that is consistent with the ''prima facie'' 2-adic relation data, finally, by projecting this intersection on a suitable plane to form a third 2-adic relation, constituting in fact the relational composition ''G'' ο ''H'' of the relations ''G'' and ''H''.
The relational composition ''G'' ο ''H'' of a pair of 2-adic relations ''G'' and ''H'' will be constructed in three stages, first, by taking the tacit extensions of ''G'' and ''H'' to 3-adic relations that reside in the same space, next, by taking the intersection of these extensions, tantamount to the maximal 3-adic relation that is consistent with the ''prima facie'' 2-adic relation data, finally, by projecting this intersection on a suitable plane to form a third 2-adic relation, constituting in fact the relational composition ''G'' ο ''H'' of the relations ''G'' and ''H''.
The construction of a relational composition in a specifically mathematical setting normally begins with [[relation (mathematics)|mathematical relations]] at a higher level of abstraction than the corresponding objects in linguistic or logical settings. This is due to the fact that mathematical objects are typically specified only ''up to [[isomorphism]]'' as the conventional saying goes, that is, any objects that have the 'same form' are generally regarded as the being the same thing, for most all intents and mathematical purposes. Thus, the mathematical construction of a relational composition begins by default with a pair of 2-adic relations that reside, without loss of generality, in the same plane, say, ''G'', ''H'' ⊆ ''X'' × ''Y'', as depicted in Figure 1.
The construction of a relational composition in a specifically mathematical setting normally begins with [[relation (mathematics)|mathematical relations]] at a higher level of abstraction than the corresponding objects in linguistic or logical settings. This is due to the fact that mathematical objects are typically specified only ''up to isomorphism'' as the conventional saying goes, that is, any objects that have the 'same form' are generally regarded as the being the same thing, for most all intents and mathematical purposes. Thus, the mathematical construction of a relational composition begins by default with a pair of 2-adic relations that reside, without loss of generality, in the same plane, say, ''G'', ''H'' ⊆ ''X'' × ''Y'', as depicted in Figure 1.
{| align="center" border="0" cellpadding="10"
|
<pre>
o-------------------------------------------------o
| |
| o o |
| |\ |\ |
| | \ | \ |
| | \ | \ |
| | \ | \ |
| | \ | \ |
| | \ | \ |
| | * \ | * \ |
| X * Y X * Y |
| \ * | \ * | |
| \ G | \ H | |
| \ | \ | |
| \ | \ | |
| \ | \ | |
| \ | \ | |
| \| \| |
| o o |
| |
o-------------------------------------------------o
Figure 1. Dyadic Relations G, H c X x Y
</pre>
|}
The 2-adic relations ''G'' and ''H'' cannot be composed at all at this point, not without additional information or further stipulation. In order for their relational composition to be possible, one of two types of cases has to happen:
The 2-adic relations ''G'' and ''H'' cannot be composed at all at this point, not without additional information or further stipulation. In order for their relational composition to be possible, one of two types of cases has to happen:
Whether you view isomorphic things to be the same things or not, you still have to specify the exact isomorphisms that are needed to transform any given representation of a thing into a required representation of the same thing. Let us imagine that we have done this, and say how later:
Whether you view isomorphic things to be the same things or not, you still have to specify the exact isomorphisms that are needed to transform any given representation of a thing into a required representation of the same thing. Let us imagine that we have done this, and say how later:
{| align="center" border="0" cellpadding="10"
|
<pre>
o-------------------------------------------------o
| |
| o o |
| |\ /| |
| | \ / | |
| | \ / | |
| | \ / | |
| | \ / | |
| | \ / | |
| | * \ / * | |
| X * Y Y * Z |
| \ * | | * / |
| \ G | | Ĥ / |
| \ | | / |
| \ | | / |
| \ | | / |
| \ | | / |
| \| |/ |
| o o |
| |
o-------------------------------------------------o
Figure 2. Dyadic Relations G c X x Y and Ĥ c Y x Z
</pre>
|}
With the required spaces carefully swept out, the stage is set for the presentation of Tarski's trick, and the invocation of the following symbolic formula, claimed to be a definition of the relational composition ''P'' ο ''Q'' of a pair of 2-adic relations ''P'', ''Q'' ⊆ ''X'' × ''X''.
With the required spaces carefully swept out, the stage is set for the presentation of Tarski's trick, and the invocation of the following symbolic formula, claimed to be a definition of the relational composition ''P'' ο ''Q'' of a pair of 2-adic relations ''P'', ''Q'' ⊆ ''X'' × ''X''.
:* ''F''(''x'', ''y'', ''z'') = ''G''(''x'', ''y'') ∧ ''H''(''y'', ''z'').
:* ''F''(''x'', ''y'', ''z'') = ''G''(''x'', ''y'') ∧ ''H''(''y'', ''z'').
{| align="center" border="0" cellpadding="10"
|
<pre>
o-------------------------------------------------o
| |
| o |
| /|\ |
| / | \ |
| / | \ |
| / | \ |
| / | \ |
| / | \ |
| / | \ |
| o o o |
| |\ / \ /| |
| | \ / F \ / | |
| | \ / * \ / | |
| | \ /*\ / | |
| | / \//*\\/ \ | |
| | / /\/ \/\ \ | |
| |/ ///\ /\\\ \| |
| o X /// Y \\\ Z o |
| |\ \/// | \\\/ /| |
| | \ /// | \\\ / | |
| | \ ///\ | /\\\ / | |
| | \ /// \ | / \\\ / | |
| | \/// \ | / \\\/ | |
| | /\/ \ | / \/\ | |
| | *//\ \|/ /\\* | |
| X */ Y o Y \* Z |
| \ * | | * / |
| \ G | | H / |
| \ | | / |
| \ | | / |
| \ | | / |
| \ | | / |
| \| |/ |
| o o |
| |
o-------------------------------------------------o
Figure 3. Projections of F onto G and H
</pre>
|}
To interpret the Figure, visualize the 3-adic relation ''F'' ⊆ ''X'' × ''Y'' × ''Z'' as a body in ''XYZ''-space, while ''G'' is a figure in ''XY''-space and ''H'' is a figure in ''YZ''-space.
To interpret the Figure, visualize the 3-adic relation ''F'' ⊆ ''X'' × ''Y'' × ''Z'' as a body in ''XYZ''-space, while ''G'' is a figure in ''XY''-space and ''H'' is a figure in ''YZ''-space.
Geometric illustrations of ''te''(''G'') and ''te''(''H'') are afforded by Figures 4 and 5, respectively.
Geometric illustrations of ''te''(''G'') and ''te''(''H'') are afforded by Figures 4 and 5, respectively.
{| align="center" border="0" cellpadding="10"
|
<pre>
o-------------------------------------------------o
| |
| o |
| /|\ |
| / | \ |
| / | \ |
| / | \ |
| / | \ |
| / | \ |
| / | * \ |
| o o ** o |
| |\ / \*** /| |
| | \ / *** / | |
| | \ / ***\ / | |
| | \ *** / | |
| | / \*** / \ | |
| | / *** / \ | |
| |/ ***\ / \| |
| o X /** Y Z o |
| |\ \//* | / /| |
| | \ /// | / / | |
| | \ ///\ | / / | |
| | \ /// \ | / / | |
| | \/// \ | / / | |
| | /\/ \ | / / | |
| | *//\ \|/ / * | |
| X */ Y o Y * Z |
| \ * | | * / |
| \ G | | H / |
| \ | | / |
| \ | | / |
| \ | | / |
| \ | | / |
| \| |/ |
| o o |
| |
o-------------------------------------------------o
Figure 4. Tacit Extension of G to X x Y x Z
Figure 4. Tacit Extension of G to X x Y x Z
<br>
</pre>
|}
{| align="center" border="0" cellpadding="10"
|
<pre>
o-------------------------------------------------o
| |
| o |
| /|\ |
| / | \ |
| / | \ |
| / | \ |
| / | \ |
| / | \ |
| / * | \ |
| o ** o o |
| |\ ***/ \ /| |
| | \ *** \ / | |
| | \ /*** \ / | |
| | \ *** / | |
| | / \ ***/ \ | |
| | / \ *** \ | |
| |/ \ /*** \| |
| o X Y **\ Z o |
| |\ \ | *\\/ /| |
| | \ \ | \\\ / | |
| | \ \ | /\\\ / | |
| | \ \ | / \\\ / | |
| | \ \ | / \\\/ | |
| | \ \ | / \/\ | |
| | * \ \|/ /\\* | |
| X * Y o Y \* Z |
| \ * | | * / |
| \ G | | H / |
| \ | | / |
| \ | | / |
| \ | | / |
| \ | | / |
| \| |/ |
| o o |
| |
o-------------------------------------------------o
Figure 5. Tacit Extension of H to X x Y x Z
</pre>
|}
A geometric interpretation can now be given that fleshes out in graphic form the meaning of a formula like the following:
A geometric interpretation can now be given that fleshes out in graphic form the meaning of a formula like the following:
The conjunction that is indicated by "∧" corresponds as usual to an intersection of two sets, however, in this case it is the intersection of the tacit extensions ''te''(''G'') and ''te''(''H'').
The conjunction that is indicated by "∧" corresponds as usual to an intersection of two sets, however, in this case it is the intersection of the tacit extensions ''te''(''G'') and ''te''(''H'').
{| align="center" border="0" cellpadding="10"
|
<pre>
o-------------------------------------------------o
| |
| o |
| /|\ |
| / | \ |
| / | \ |
| / | \ |
| / | \ |
| / | \ |
| / | \ |
| o o o |
| |\ / \ /| |
| | \ / F \ / | |
| | \ / * \ / | |
| | \ /*\ / | |
| | / \//*\\/ \ | |
| | / /\/ \/\ \ | |
| |/ ///\ /\\\ \| |
| o X /// Y \\\ Z o |
| |\ \/// | \\\/ /| |
| | \ /// | \\\ / | |
| | \ ///\ | /\\\ / | |
| | \ /// \ | / \\\ / | |
| | \/// \ | / \\\/ | |
| | /\/ \ | / \/\ | |
| | *//\ \|/ /\\* | |
| X */ Y o Y \* Z |
| \ * | | * / |
| \ G | | H / |
| \ | | / |
| \ | | / |
| \ | | / |
| \ | | / |
| \| |/ |
| o o |
| |
o-------------------------------------------------o
Figure 6. F as the Intersection of te(G) and te(H)
</pre>
|}
==Algebraic construction==
==Algebraic construction==
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:
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:
{| align="center" border="0" cellpadding="10"
|
<pre>
o-------------------------------------------------o
| |
| o |
| /|\ |
| / | \ |
| / | \ |
| / | \ |
| / | \ |
| / | \ |
| / | \ |
| o 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 7. F as the Intersection of te(G) and te(H)
</pre>
|}
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 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.
Here is the big picture, with all of the pieces in place:
Here is the big picture, with all of the pieces in place:
{| align="center" border="0" cellpadding="10"
|
<pre>
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 |
| |\ \/// | \\\/ /| |
| | \ /// | \\\ / | |
| | \ ///\ | /\\\ / | |
| | \ /// \ | / \\\ / | |
| | \/// \ | / \\\/ | |
| | G/\/ \ | / \/\H | |
| | *//\ \|/ /\\* | |
| 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 (te(G) |^| te(H))
</pre>
|}
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.
Here is what ''G'' and ''H'' look like in the bigraph picture:
Here is what ''G'' and ''H'' look like in the bigraph picture:
{| align="center" border="0" cellpadding="10"
|
<pre>
o---------------------------------------o
| |
| 1 2 3 4 5 6 7 |
| o o o o o o o X |
| /|\ |
| / | \ G |
| / | \ |
| o o o o o o o X |
| 1 2 3 4 5 6 7 |
| |
o---------------------------------------o
Figure 9. G = 4:3 + 4:4 + 4:5
</pre>
|-
|
<pre>
o---------------------------------------o
| |
| 1 2 3 4 5 6 7 |
| o o o o o o o X |
| \ | / |
| \ | / H |
| \|/ |
| o o o o o o o X |
| 1 2 3 4 5 6 7 |
| |
o---------------------------------------o
Figure 10. H = 3:4 + 4:4 + 5:4
</pre>
|}
These graphs may be read to say:
These graphs may be read to say:
Here's how it looks in pictures:
Here's how it looks in pictures:
{| align="center" border="0" cellpadding="10"
|
<pre>
o---------------------------------------o
| |
| 1 2 3 4 5 6 7 |
| o o o o o o o X |
| /|\ |
| / | \ G |
| / | \ |
| o o o o o o o X |
| \ | / |
| \ | / H |
| \|/ |
| o o o o o o o X |
| 1 2 3 4 5 6 7 |
| |
o---------------------------------------o
Figure 11. G Followed By H
</pre>
|-
|
<pre>
o---------------------------------------o
| |
| 1 2 3 4 5 6 7 |
| o o o o o o o X |
| | |
| | G o H |
| | |
| o o o o o o o X |
| 1 2 3 4 5 6 7 |
| |
o---------------------------------------o
Figure 12. G Composed With H
</pre>
|}
Once again we find that ''G'' ο ''H'' = 4:4.
Once again we find that ''G'' ο ''H'' = 4:4.
Here are the bigraph pictures:
Here are the bigraph pictures:
{| align="center" border="0" cellpadding="10"
|
<pre>
o---------------------------------------o
| |
| 1 2 3 4 5 6 7 |
| o o o o o o o X |
| /|\ /|\ /|\ |
| / | \ / | \ / | \ M |
| / | \ / | \ / | \ |
| o o o o o o o X |
| 1 2 3 4 5 6 7 |
| |
o---------------------------------------o
Figure 13. Dyadic Relation M
</pre>
|-
|
<pre>
o---------------------------------------o
| |
| 1 2 3 4 5 6 7 |
| o o o o o o o X |
| | / | / \ | \ | |
| | / | / \ | \ | N |
| |/ |/ \| \| |
| o o o o o o o X |
| 1 2 3 4 5 6 7 |
| |
o---------------------------------------o
Figure 14. Dyadic Relation N
</pre>
|}
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 ''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''.
Here's how it looks in pictures:
Here's how it looks in pictures:
{| align="center" border="0" cellpadding="10"
|
<pre>
o---------------------------------------o
| |
| 1 2 3 4 5 6 7 |
| o o o o o o o X |
| /|\ /|\ /|\ |
| / | \ / | \ / | \ M |
| / | \ / | \ / | \ |
| o o o o o o o X |
| | / | / \ | \ | |
| | / | / \ | \ | N |
| |/ |/ \| \| |
| o o o o o o o X |
| 1 2 3 4 5 6 7 |
| |
o---------------------------------------o
Figure 15. M Followed By N
</pre>
|-
|
<pre>
o---------------------------------------o
| |
| 1 2 3 4 5 6 7 |
| o o o o o o o X |
| / \ / \ / \ |
| / \ / \ / \ M o N |
| / \ / \ / \ |
| o o o o o o o X |
| 1 2 3 4 5 6 7 |
| |
o---------------------------------------o
Figure 16. M Composed With N
</pre>
|}
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.
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 ''M'' and ''N'', namely, the composition ''N'' ο ''M'', that takes ''M'' and ''N'' in the opposite order. Here is the graphic computation:
{| align="center" border="0" cellpadding="10"
|
<pre>
o---------------------------------------o
| |
| 1 2 3 4 5 6 7 |
| o o o o o o o X |
| | / | / \ | \ | |
| | / | / \ | \ | N |
| |/ |/ \| \| |
| o o o o o o o X |
| /|\ /|\ /|\ |
| / | \ / | \ / | \ M |
| / | \ / | \ / | \ |
| o o o o o o o X |
| 1 2 3 4 5 6 7 |
| |
o---------------------------------------o
Figure 17. N Followed By M
</pre>
|-
|
<pre>
o---------------------------------------o
| |
| 1 2 3 4 5 6 7 |
| o o o o o o o X |
| |
| N o M |
| |
| o o o o o o o X |
| 1 2 3 4 5 6 7 |
| |
o---------------------------------------o
Figure 18. N Composed With M
</pre>
|}
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, ''N'' ο ''M'' = 0. This example affords sufficient evidence that relational composition, just like its kindred, matrix multiplication, is a ''[[non-commutative]]'' algebraic operation.
{{col-begin}}
{{col-begin}}
{{col-break}}
{{col-break}}
* [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]
{{col-break}}
{{col-break}}
* [http://p2pfoundation.net/Relation_Composition Relation Composition @ P2P Foundation]
* [http://beta.wikiversity.org/wiki/Relation_composition Relation Composition @ Wikiversity Beta]
* [http://ref.subwiki.org/wiki/Relation_composition Relation Composition @ Subject Wikis]
* [http://ref.subwiki.org/wiki/Relation_composition Relation Composition @ Subject Wikis]
{{col-end}}
{{col-end}}
===Related articles===
===Related articles===
* [http://mywikibiz.com/Directory:Jon_Awbrey/Papers/Semiotic_Information Jon Awbrey, “Semiotic Information”]
{{col-begin}}
{{col-break}}
* [http://mywikibiz.com/Directory:Jon_Awbrey/Papers/Introduction_to_Inquiry_Driven_Systems Jon Awbrey, “Introduction To Inquiry Driven Systems”]
* [http://intersci.ss.uci.edu/wiki/index.php/Cactus_Language Cactus Language]
* [http://intersci.ss.uci.edu/wiki/index.php/Futures_Of_Logical_Graphs Futures Of Logical Graphs]
* [http://mywikibiz.com/Directory:Jon_Awbrey/Essays/Prospects_For_Inquiry_Driven_Systems Jon Awbrey, “Prospects For Inquiry Driven Systems”]
* [http://intersci.ss.uci.edu/wiki/index.php/Propositional_Equation_Reasoning_Systems Propositional Equation Reasoning Systems]
{{col-break}}
* [http://mywikibiz.com/Directory:Jon_Awbrey/Papers/Inquiry_Driven_Systems Jon Awbrey, “Inquiry Driven Systems : Inquiry Into Inquiry”]
* [http://intersci.ss.uci.edu/wiki/index.php/Differential_Logic_:_Introduction Differential Logic : Introduction]
* [http://intersci.ss.uci.edu/wiki/index.php/Differential_Propositional_Calculus Differential Propositional Calculus]
* [http://mywikibiz.com/Directory:Jon_Awbrey/Papers/Propositional_Equation_Reasoning_Systems Jon Awbrey, “Propositional Equation Reasoning Systems”]
* [http://intersci.ss.uci.edu/wiki/index.php/Differential_Logic_and_Dynamic_Systems_2.0 Differential Logic and Dynamic Systems]
{{col-break}}
* [http://mywikibiz.com/Directory:Jon_Awbrey/Papers/Differential_Logic_:_Introduction Jon Awbrey, “Differential Logic : Introduction”]
* [http://intersci.ss.uci.edu/wiki/index.php/Introduction_to_Inquiry_Driven_Systems Introduction to Inquiry Driven Systems]
* [http://intersci.ss.uci.edu/wiki/index.php/Prospects_for_Inquiry_Driven_Systems Prospects for Inquiry Driven Systems]
* [http://planetmath.org/encyclopedia/DifferentialPropositionalCalculus.html Jon Awbrey, “Differential Propositional Calculus”]
* [http://intersci.ss.uci.edu/wiki/index.php/Inquiry_Driven_Systems Inquiry Driven Systems : Inquiry Into Inquiry]
{{col-end}}
* [http://mywikibiz.com/Directory:Jon_Awbrey/Papers/Differential_Logic_and_Dynamic_Systems_2.0 Jon Awbrey, “Differential Logic and Dynamic Systems”]
==Document history==
==Document history==
* [http://mywikibiz.com/Relation_composition Relation Composition], [http://mywikibiz.com/ MyWikiBiz]
* [http://mywikibiz.com/Relation_composition Relation Composition], [http://mywikibiz.com/ MyWikiBiz]
* [http://mathweb.org/wiki/Relation_composition Relation Composition], [http://mathweb.org/wiki/ MathWeb Wiki]
* [http://mathweb.org/wiki/Relation_composition Relation Composition], [http://mathweb.org/wiki/ MathWeb Wiki]
{{col-break}}
* [http://p2pfoundation.net/Relation_Composition Relation Composition], [http://p2pfoundation.net/ P2P Foundation]
* [http://p2pfoundation.net/Relation_Composition Relation Composition], [http://p2pfoundation.net/ P2P Foundation]
* [http://semanticweb.org/wiki/Relation_composition Relation Composition], [http://semanticweb.org/ Semantic Web]
{{col-break}}
{{col-break}}
* [http://planetmath.org/RelationComposition Relation Composition], [http://planetmath.org/ PlanetMath]
* [http://planetmath.org/RelationComposition Relation Composition], [http://planetmath.org/ PlanetMath]
* [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]
{{col-end}}
{{col-end}}
[[Category:Combinatorics]]
[[Category:Combinatorics]]
[[Category:Computer Science]]
[[Category:Computer Science]]
[[Category:Discrete Mathematics]]
[[Category:Discrete Mathematics]]
[[Category:Formal Sciences]]
[[Category:Formal Sciences]]
[[Category:Inquiry]]
[[Category:Logic]]
[[Category:Logic]]
[[Category:Mathematics]]
[[Category:Mathematics]]
[[Category:Relation Theory]]
[[Category:Relation Theory]]
[[Category:Set Theory]]
[[Category:Set Theory]]
