12,080
edits
Changes
TeX
==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 dyadic and triadic 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 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.
|}
|}
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 dyadic relations is formulated in the following two ways:
{| align="center" cellpadding="4" width="90%"
{| align="center" cellpadding="4" width="90%"
==Geometric construction==
==Geometric construction==
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.
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 dyadic 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 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''.
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 dyadic 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 <math>\land,\!</math> in expressions of the form <math>F(x, y, z) = G(x, y) \land H(y, z),\!</math> to define a triadic relation <math>F\!</math> in terms of a pair of dyadic relations <math>G\!</math> and <math>H.\!</math>
:* The concepts of 2-adic ''projection'' and ''projective determination'', that are invoked in the “weak” notion of ''projective reducibility''.
:* The concepts of dyadic ''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 <math>G \circ H\!</math> of a pair of dyadic relations <math>G\!</math> and <math>H\!</math> will be constructed in three stages, first, by taking the tacit extensions of <math>G\!</math> and <math>H\!</math> to triadic relations that reside in the same space, next, by taking the intersection of these extensions, tantamount to the maximal triadic relation that is consistent with the ''prima facie'' dyadic relation data, finally, by projecting this intersection on a suitable plane to form a third dyadic relation, constituting in fact the relational composition <math>G \circ H\!</math> of the relations <math>G\!</math> and <math>H.\!</math>
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 dyadic relations that reside, without loss of generality, in the same plane, say, <math>G, H \subseteq X \times Y,\!</math> as shown in Figure 1.
{| align="center" border="0" cellpadding="10"
{| align="center" border="0" cellpadding="10"
|}
|}
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 dyadic relations <math>G\!</math> and <math>H\!</math> 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 first type of case occurs when ''X'' = ''Y''. In this case, both of the compositions ''G'' ο ''H'' and ''H'' ο ''G'' are defined.
:* The first type of case occurs when <math>X = Y.\!</math> In this case, both of the compositions <math>G \circ H\!</math> and <math>H \circ G\!</math> are defined.
:* The second type of case occurs when ''X'' and ''Y'' are distinct, but when it nevertheless makes sense to speak of a 2-adic relation ''Ĥ'' that is isomorphic to ''H'', but living in the plane ''YZ'', that is, in the space of the cartesian product ''Y'' × ''Z'', for some set ''Z''.
:* The second type of case occurs when <math>X\!</math> and <math>Y\!</math> are distinct, but when it nevertheless makes sense to speak of a dyadic relation <math>\hat{H}\!</math> that is isomorphic to <math>H,\!</math> but living in the plane <math>YZ,\!</math> that is, in the space of the cartesian product <math>Y \times Z,\!</math> for some set <math>Z.\!</math>
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:
|}
|}
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 <math>P \circ Q\!</math> of a pair of dyadic relations <math>P, Q
\subseteq X \times X.\!</math>
: '''Definition.''' ''P'' ο ''Q'' = ''proj''<sub>13</sub> (''P'' × ''X'' ∩ ''X'' × ''Q'').
: '''Definition.''' <math>P \circ Q = \mathrm{proj}_{13} (P \times X ~\cap~ X \times Q).\!</math>
To get this drift of this definition, one needs to understand that it's written within a school of thought that holds that all 2-adic relations are, 'without loss of generality', covered well enough, 'for all practical purposes', under the aegis of subsets of a suitable cartesian square, and thus of the form ''L'' ⊆ ''X'' × ''X''. So, if one has started out with a 2-adic relation of the shape ''L'' ⊆ ''U'' × ''V'', one merely lets ''X'' = ''U'' ∪ ''V'', trading in the initial ''L'' for a new ''L'' ⊆ ''X'' × ''X'' as need be.
To get this drift of this definition one needs to understand that it comes from a point of view that regards all dyadic relations as covered well enough by subsets of a suitable cartesian square and thus of the form <math>L \subseteq X \times X.\!</math> So, if one has started out with a dyadic relation of the shape <math>L \subseteq U \times V,\!</math> one merely lets <math>X = U \cup V,\!</math> trading in the initial <math>L\!</math> for a new <math>L \subseteq X \times X\!</math> as need be.
The projection ''proj''<sub>13</sub> is just the projection of the cartesian cube ''X'' × ''X'' × ''X'' on the space of shape ''X'' × ''X'' that is spanned by the first and the third domains, but since they now have the same names and the same contents it is necessary to distinguish them by numbering their relational places.
The projection <math>\mathrm{proj}_{13}\!</math> is just the projection of the cartesian cube <math>X \times X \times X\!</math> on the space of shape <math>X \times X\!</math> that is spanned by the first and the third domains, but since they now have the same names and the same contents it is necessary to distinguish them by numbering their relational places.
Finally, the notation of the cartesian product sign "×" is extended to signify two other products with respect to a 2-adic relation ''L'' ⊆ ''X'' × ''X'' and a subset ''W'' ⊆ ''X'', as follows:
Finally, the notation of the cartesian product sign “<math>\times\!</math>” is extended to signify two other products with respect to a dyadic relation <math>L \subseteq X \times X\!</math> and a subset <math>W \subseteq X,\!</math> as follows:
: '''Definition.''' ''L'' × ''W'' = {(''x'', ''y'', ''z'') ∈ ''X''<sup>3</sup> : (''x'', ''y'') ∈ ''L'' ∧ ''z'' ∈ ''W''}.
: '''Definition.''' <math>L \times W ~=~ \{ (x, y, z) \in X^3 ~:~ (x, y) \in L ~\mathrm{and}~ z \in W \}.\!</math>
: '''Definition.''' ''W'' × ''L'' = {(''x'', ''y'', ''z'') ∈ ''X''<sup>3</sup> : ''x'' ∈ ''W'' ∧ (''y'', ''z'') ∈ ''L''}.
: '''Definition.''' <math>W \times L ~=~ \{ (x, y, z) \in X^3 ~:~ x \in W ~\mathrm{and}~ (y, z) \in L \}.\!</math>
Applying these definitions to the case ''P'', ''Q'' ⊆ ''X'' × ''X'', the two 2-adic relations whose relational composition ''P'' ο ''Q'' ⊆ ''X'' × ''X'' is about to be defined, one finds:
Applying these definitions to the case <math>P, Q \subseteq X \times X,\!</math> the two dyadic relations whose relational composition <math>P \circ Q \subseteq X \times X\!</math> is about to be defined, one finds:
: ''P'' × ''X'' = {(''x'', ''y'', ''z'') ∈ ''X''<sup>3</sup> : (''x'', ''y'') ∈ ''P'' ∧ ''z'' ∈ ''X''},
: <math>P \times X ~=~ \{ (x, y, z) \in X^3 ~:~ (x, y) \in P ~\mathrm{and}~ z \in X \},\!</math>
: ''X'' × ''Q'' = {(''x'', ''y'', ''z'') ∈ ''X''<sup>3</sup> : ''x'' ∈ ''X'' ∧ (''y'', ''z'') ∈ ''Q''}.
: <math>X \times Q ~=~ \{ (x, y, z) \in X^3 ~:~ x \in X ~\mathrm{and}~ (y, z) \in Q \}.\!</math>
These are just the appropriate special cases of the tacit extensions already defined.
These are just the appropriate special cases of the tacit extensions already defined.
: ''P'' × ''X'' = ''te''<sub>12</sub><sup>3</sup>(''P''),
: <math>P \times X ~=~ \mathrm{te}_{12}^3 (P),~\!</math>
: ''X'' × ''Q'' = ''te''<sub>23</sub><sup>1</sup>(''Q'').
: <math>X \times Q ~=~ \mathrm{te}_{23}^1 (Q).~\!</math>
In summary, then, the expression:
In summary, then, the expression:
: ''proj''<sub>13</sub>(''P'' × ''X'' ∩ ''X'' × ''Q'')
: <math>\mathrm{proj}_{13} (P \times X ~\cap~ X \times Q)\!</math>
is equivalent to the expression:
is equivalent to the expression:
: ''proj''<sub>13</sub>(''te''<sub>12</sub><sup>3</sup>(''P'') ∩ ''te''<sub>23</sub><sup>1</sup>(''Q''))
: <math>\mathrm{proj}_{13} (\mathrm{te}_{12}^3 (P) ~\cap~ \mathrm{te}_{23}^1 (Q))\!</math>
and this form is generalized — although, relative to one's school of thought, perhaps inessentially so — by the form that was given above as follows:
and this form is generalized — although, relative to one's school of thought, perhaps inessentially so — by the form that was given above as follows:
: '''Definition.''' ''P'' ο ''Q'' = ''proj''<sub>''XZ''</sub>(''te''<sub>''XY''</sub><sup>''Z''</sup>(''P'') ∩ ''te''<sub>''YZ''</sub><sup>''X''</sup>(''Q'')).
: '''Definition.''' <math>P \circ Q ~=~ \mathrm{proj}_{XZ} (\mathrm{te}_{XY}^Z (P) ~\cap~ \mathrm{te}_{YZ}^X (Q)).\!</math>
Figure 3 presents a geometric picture of what is involved in formulating a definition of the 3-adic relation ''F'' ⊆ ''X'' × ''Y'' × ''Z'' by way of a conjunction of the 2-adic relation ''G'' ⊆ ''X'' × ''Y'' and the 2-adic relation ''H'' ⊆ ''Y'' × ''Z'', as done for example by means of an expression of the following form:
Figure 3 presents a geometric picture of what is involved in formulating a definition of the triadic relation <math>F \subseteq X \times Y \times Z\!</math> by way of a conjunction between the dyadic relation <math>G \subseteq X \times Y\!</math> and the dyadic relation <math>H \subseteq Y \times Z,\!</math> as done for example by means of an expression of the following form:
:* ''F''(''x'', ''y'', ''z'') = ''G''(''x'', ''y'') ∧ ''H''(''y'', ''z'').
:* <math>F(x, y, z) ~=~ G(x, y) \land H(y, z).\!</math>
{| align="center" border="0" cellpadding="10"
{| align="center" border="0" cellpadding="10"
|}
|}
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 triadic relation <math>F \subseteq X \times Y \times Z\!</math> as a body in <math>XYZ\!</math>-space, while <math>G\!</math> is a figure in <math>XY\!</math>-space and <math>H\!</math> is a figure in <math>YZ\!</math>-space.
The 2-adic '''projections''' that accompany a 3-adic relation over ''X'', ''Y'', ''Z'' are defined as follows:
The dyadic '''projections''' that accompany a triadic relation over <math>X, Y, Z\!</math> are defined as follows:
:* ''proj''<sub>''XY''</sub>(''L'') = {(''x'', ''y'') ∈ ''X'' × ''Y'' : (∃ ''z'' ∈ ''Z'') (''x'', ''y'', ''z'') ∈ ''L''},
:* <math>\mathrm{proj}_{XY} (L) ~=~ \{ (x, y) \in X \times Y : (x, y, z) \in L ~\text{for some}~ z \in Z) \},\!</math>
:* ''proj''<sub>''XZ''</sub>(''L'') = {(''x'', ''z'') ∈ ''X'' × ''Z'' : (∃ ''y'' ∈ ''Y'') (''x'', ''y'', ''z'') ∈ ''L''},
:* <math>\mathrm{proj}_{XZ} (L) ~=~ \{ (x, z) \in X \times Z : (x, y, z) \in L ~\text{for some}~ y \in Y) \},\!</math>
:* ''proj''<sub>''YZ''</sub>(''L'') = {(''y'', ''z'') ∈ ''Y'' × ''Z'' : (∃ ''x'' ∈ ''X'') (''x'', ''y'', ''z'') ∈ ''L''}.
:* <math>\mathrm{proj}_{YZ} (L) ~=~ \{ (y, z) \in Y \times Z : (x, y, z) \in L ~\text{for some}~ x \in X) \}.\!</math>
For many purposes it suffices to indicate the 2-adic projections of a 3-adic relation ''L'' by means of the briefer equivalents listed here:
For many purposes it suffices to indicate the dyadic projections of a triadic relation <math>L\!</math> by means of the briefer equivalents listed next:
:* ''L''<sub>''XY''</sub> = ''proj''<sub>''XY''</sub>(''L''),
:* <math>L_{XY} ~=~ \mathrm{proj}_{XY}(L),\!</math>
:* ''L''<sub>''XZ''</sub> = ''proj''<sub>''XZ''</sub>(''L''),
:* <math>L_{XZ} ~=~ \mathrm{proj}_{XZ}(L),\!</math>
:* ''L''<sub>''YZ''</sub> = ''proj''<sub>''YZ''</sub>(''L'').
:* <math>L_{YZ} ~=~ \mathrm{proj}_{YZ}(L).\!</math>
In light of these definitions, ''proj''<sub>''XY''</sub> is a mapping from the set <font face=signature>L</font><sub>''XYZ''</sub> of 3-adic relations over ''X'', ''Y'', ''Z'' to the set <font face=signature>L</font><sub>''XY''</sub> of 2-adic relations over ''X'' and ''Y'', with similar relationships holding for the other projections. To formalize these relationships in a concise but explicit manner, it serves to add a few more definitions.
In light of these definitions, <math>\mathrm{proj}_{XY}\!</math> is a mapping from the set <math>\mathcal{L}_{XYZ}\!</math> of triadic relations over the domains <math>X, Y, Z\!</math> to the set <math>\mathcal{L}_{XY}\!</math> of dyadic relations over the domains <math>X, Y,\!</math> with similar relationships holding for the other projections. To formalize these relationships in a concise but explicit manner, it serves to add a few more definitions.
The set <font face=signature>L</font><sub>''XYZ''</sub>, whose membership is just the 3-adic relations over ''X'', ''Y'', ''Z'', can be recognized as the set of all subsets of the cartesian product ''X'' × ''Y'' × ''Z'', also known as the '''power set''' of ''X'' × ''Y'' × ''Z'', and notated here as ''Pow''(''X'' × ''Y'' × ''Z'').
The set <math>\mathcal{L}_{XYZ},~\!</math> whose members are just the triadic relations over <math>X, Y, Z,\!</math> can be recognized as the set of all subsets of the cartesian product <math>X \times Y \times Z,\!</math> also known as the ''power set'' of <math>X \times Y \times Z,\!</math> and notated here as <math>\mathrm{Pow} (X \times Y \times Z).\!</math>
:* <font face=signature>L</font><sub>''XYZ''</sub> = {''L'' : ''L'' ⊆ ''X'' × ''Y'' × ''Z''} = ''Pow''(''X'' × ''Y'' × ''Z'').
:* <math>\mathcal{L}_{XYZ} ~=~ \{ L : L \subseteq X \times Y \times Z \} ~=~ \mathrm{Pow} (X \times Y \times Z).\!</math>
Likewise, the power sets of the pairwise cartesian products encompass all of the 2-adic relations on pairs of distinct domains that can be chosen from {''X'', ''Y'', ''Z''}.
Likewise, the power sets of the pairwise cartesian products encompass all the dyadic relations on pairs of distinct domains that can be chosen from <math>\{ X, Y, Z \}.\!</math>
:* <font face=signature>L</font><sub>''XY''</sub> = {''L'' : ''L'' ⊆ ''X'' × ''Y''} = ''Pow''(''X'' × ''Y''),
:* <math>\mathcal{L}_{XY} ~=~ \{L : L \subseteq X \times Y \} ~=~ \mathrm{Pow} (X \times Y),~\!</math>
:* <font face=signature>L</font><sub>''XZ''</sub> = {''L'' : ''L'' ⊆ ''X'' × ''Z''} = ''Pow''(''X'' × ''Z''),
:* <math>\mathcal{L}_{XZ} ~=~ \{L : L \subseteq X \times Z \} ~=~ \mathrm{Pow} (X \times Z),~\!</math>
:* <font face=signature>L</font><sub>''YZ''</sub> = {''L'' : ''L'' ⊆ ''Y'' × ''Z''} = ''Pow''(''Y'' × ''Z'').
:* <math>\mathcal{L}_{YZ} ~=~ \{L : L \subseteq Y \times Z \} ~=~ \mathrm{Pow} (Y \times Z).~\!</math>
In mathematics, the inverse relation corresponding to a projection map is usually called an '''extension'''. To avoid confusion with other senses of the word, however, it is probably best for the sake of this discussion to stick with the more specific term '''tacit extension'''.
In mathematics, the inverse relation corresponding to a projection map is usually called an ''extension''. To avoid confusion with other senses of the word, however, it is probably best for the sake of this discussion to stick with the more specific term ''tacit extension''.
Given three sets, <math>X, Y, Z,\!</math> and three dyadic relations,
:* ''te''<sub>''XY''</sub><sup>''Z''</sup>(''U'') = {(''x'', ''y'', ''z'') : (''x'', ''y'') ∈ ''U''}
:* <math>U \subseteq X \times Y,~\!</math>
:* ''te''<sub>''XZ''</sub><sup>''Y''</sup>(''V'') = {(''x'', ''y'', ''z'') : (''x'', ''z'') ∈ ''V''}
:* <math>V \subseteq X \times Z,~\!</math>
:* ''te''<sub>''YZ''</sub><sup>''X''</sup>(''W'') = {(''x'', ''y'', ''z'') : (''y'', ''z'') ∈ ''W''}
:* <math>W \subseteq Y \times Z,~\!</math>
the ''tacit extensions'', <math>\mathrm{te}_{XY}^Z, \mathrm{te}_{XZ}^Y, \mathrm{te}_{YZ}^X,~\!</math> of <math>U, V, W,\!</math> respectively, are defined as follows:
:* <math>\mathrm{te}_{XY}^Z (U) ~=~ \{ (x, y, z) : (x, y) \in U \},\!</math>
Geometric illustrations of ''te''(''G'') and ''te''(''H'') are afforded by Figures 4 and 5, respectively.
:* <math>\mathrm{te}_{XZ}^Y (V) ~=~ \{ (x, y, z) : (x, z) \in V \},\!</math>
:* <math>\mathrm{te}_{YZ}^X (W) ~=~ \{ (x, y, z) : (y, z) \in W \}.\!</math>
So long as the intended indices attaching to the tacit extensions can be gathered from context, it is usually clear enough to use the abbreviated forms, <math>\mathrm{te}(U), \mathrm{te}(V), \mathrm{te}(W).\!</math>
The definition and illustration of relational composition presently under way makes use of the tacit extension of <math>G \subseteq X \times Y\!</math> to <math>\mathrm{te}(G) \subseteq X \times Y
\times Z\!</math> and the tacit extension of <math>H \subseteq Y \times Z\!</math> to <math>\mathrm{te}(H) \subseteq X \times Y \times Z,\!</math> only.
Geometric illustrations of <math>\mathrm{te}(G)\!</math> and <math>\mathrm{te}(H)\!</math> are afforded by Figures 4 and 5, respectively.
{| align="center" border="0" cellpadding="10"
{| align="center" border="0" cellpadding="10"
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:
:* ''F''(''x'', ''y'', ''z'') = ''G''(''x'', ''y'') ∧ ''H''(''y'', ''z'').
:* <math>F(x, y, z) ~=~ G(x, y) \land H(y, z).\!</math>
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 “<math>\land\!</math>” corresponds as usual to an intersection of two sets, however, in this case it is the intersection of the tacit extensions <math>\mathrm{te}(G)\!</math> and <math>\mathrm{te}(H).\!</math>
{| align="center" border="0" cellpadding="10"
{| align="center" border="0" cellpadding="10"
==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, dyadic and triadic in the present case. Adding coordinates to the running Example produces the following Figure:
{| align="center" border="0" cellpadding="10"
{| align="center" border="0" cellpadding="10"
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 ''G'' and ''H'' 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:
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:
: ''G'' ο ''H'' = ''proj''<sub>''XZ''</sub>(''te''<sub>''XY''</sub><sup>''Z''</sup>(''G'') ∩ ''te''<sub>''YZ''</sub><sup>''X''</sup>(''H'')).
: ''G'' ο ''H'' = ''proj''<sub>''XZ''</sub>(''te''<sub>''XY''</sub><sup>''Z''</sup>(''G'') ∩ ''te''<sub>''YZ''</sub><sup>''X''</sup>(''H'')).
==Matrix representation==
==Matrix representation==
We have it within our reach to pick up another way of representing 2-adic 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 2-adic 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 ''G'' ο ''H'' of the dyadic relations ''G'' and ''H''.
Here is the setup that we had before:
Here is the setup that we had before:
|}
|}
Let us recall the rule for finding the relational composition of a pair of 2-adic relations. Given the 2-adic 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 ''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:
To compute ''PQ'', in general, where ''P'' and ''Q'' are 2-adic 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 ''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''.
{| cellpadding=8 style="text-align:center"
{| cellpadding=8 style="text-align:center"
|}
|}
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 2-adic 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 ''G'' and ''H'' together to obtain their relational composite ''G'' o ''H''.
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 ''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:
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 ∑<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''.
In general, for a 2-adic 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 ''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''.
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 ''G'' and ''H'' may be written out as follows:
|}
|}
These are the logical matrix representations of the 2-adic relations ''G'' and ''H''.
These are the logical matrix representations of the dyadic relations ''G'' and ''H''.
If the 2-adic 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 ''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:
: ''G'' ο ''H'' = (∑<sub>''ij''</sub> ''G''<sub>''ij''</sub>(''i'':''j''))(∑<sub>''ij''</sub> ''H''<sub>''ij''</sub>(''i'':''j'')).
: ''G'' ο ''H'' = (∑<sub>''ij''</sub> ''G''<sub>''ij''</sub>(''i'':''j''))(∑<sub>''ij''</sub> ''H''<sub>''ij''</sub>(''i'':''j'')).
The composite relation ''G'' ο ''H'' is itself a 2-adic 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 ''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:
: ''G'' ο ''H'' = ∑<sub>''ij''</sub> (''G'' ο ''H'')<sub>''ij''</sub>(''i'':''j'').
: ''G'' ο ''H'' = ∑<sub>''ij''</sub> (''G'' ο ''H'')<sub>''ij''</sub>(''i'':''j'').
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 ''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.
All that remains in order to obtain a computational formula for the relational composite ''G'' ο ''H'' of the 2-adic 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 ''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''.
: ''G'' ο ''H'' = ∑<sub>''ij''</sub> (''G'' ο ''H'')<sub>''ij''</sub>(''i'':''j'') = ∑<sub>''ij''</sub>(∑<sub>''k''</sub> ''G''<sub>''ik''</sub>''H''<sub>''kj''</sub>)(''i'':''j'').
: ''G'' ο ''H'' = ∑<sub>''ij''</sub> (''G'' ο ''H'')<sub>''ij''</sub>(''i'':''j'') = ∑<sub>''ij''</sub>(∑<sub>''k''</sub> ''G''<sub>''ik''</sub>''H''<sub>''kj''</sub>)(''i'':''j'').
==Graph-theoretic picture==
==Graph-theoretic picture==
There is another form of representation for 2-adic 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 graph]]s'', or ''bigraphs'' for short.
Here is what ''G'' and ''H'' look like in the bigraph picture:
Here is what ''G'' and ''H'' look like in the bigraph picture:
Once again we find that ''G'' ο ''H'' = 4:4.
Once again we find that ''G'' ο ''H'' = 4:4.
We have now seen three different representations of 2-adic 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 2-adic 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 2-adic relations ''M'', ''N'' ⊆ ''X'' × ''X'' as follows:
Keeping to the same space ''X'' = {1, 2, 3, 4, 5, 6, 7}, define the dyadic relations ''M'', ''N'' ⊆ ''X'' × ''X'' as follows:
{| cellpadding="2px" style="text-align:center"
{| cellpadding="2px" style="text-align:center"