relation composition
Relation composition^{}, or the composition of 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 entry on relation theory (http://planetmath.org/RelationTheory).
Contents:
1 Preliminaries
The first order of business is to define the operation on 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 2adic and 3adic 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.
 •

•
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.

•
These two factors together generate the following four styles of syntax:
Left application, Left association (LALA).
Left application, Right association (LARA).
Right application, Left association (RALA).
Right application, Right association (RARA).
2 Definition
A notion of relational composition is to be defined that generalizes the usual notion of functional^{} composition:

•
Composing on the right, $f:X\to Y$ followed by $g:Y\to Z$ results in a composite function formulated as $fg:X\to Z$.

•
Composing on the left, $f:X\to Y$ followed by $g:Y\to Z$ results in a composite function formulated as $gf:X\to Z$.
Note on notation. The ordinary symbol for functional composition is the composition sign, a small circle “$\circ $” written between the names of the functions being composed, as $f\circ g$, 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 raised dot sign “$\cdot $”, as $f\cdot g$.
Generalizing the paradigm along parallel lines, the composition of a pair of 2adic relations is formulated in the following two ways:

•
Composing on the right, $P\subseteq X\times Y$ followed by $Q\subseteq Y\times Z$ results in a composite relation formulated as $PQ\subseteq X\times Z$.

•
Composing on the left, $P\subseteq X\times Y$ followed by $Q\subseteq Y\times Z$ results in a composite relation formulated as $QP\subseteq X\times Z$.
In the rest of this discussion 2adic relations will be composed on the right, leading to the following definition of $PQ=P\circ Q$ for the composable pair of relations, $P\subseteq X\times Y$ and $Q\subseteq Y\times Z$.
Definition. $P\circ Q=\{(x,z)\in X\times Z:(x,y)\in P\mathrm{and}(y,z)\in Q\}.$
3 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 2adic 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 Alfred Tarski 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 2adic relations, doing this by attaching concrete imagery to the basic settheoretic operations, namely, intersections^{}, projections, and a certain class of operations inverse^{} to projections, here called tacit extensions (http://planetmath.org/TacitExtension).
See main entry (http://planetmath.org/GeometricRepresentationOfRelationComposition) for details.
4 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, 2adic and 3adic in the present case.
See main entry (http://planetmath.org/AlgebraicRepresentationOfRelationComposition) for details.
5 Matrix representation
We have it within our reach to pick up another way of representing 2adic relations, namely, the representation as logical matrices^{}, and also to grasp the analogy^{} between relational composition and ordinary matrix multiplication^{} as it appears in linear algebra.
See main entry (http://planetmath.org/MatrixRepresentationOfRelationComposition) for details.
6 Graphtheoretic picture
There is another form of representation for 2adic 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^{} (http://planetmath.org/BipartiteGraph), or bigraphs for short.
See main entry (http://planetmath.org/GraphTheoreticRepresentationOfRelationComposition) for details.
7 Relation reduction
See main entry (http://planetmath.org/RelationReduction) for details.
8 References

•
Ulam, Stanislaw Marcin; and Bednarek, A.R. (1977), “On the Theory of Relational Structures and Schemata for Parallel Computation”. Reprinted, pp. 477–508 in Ulam (1990).

•
Ulam, Stanislaw Marcin (1990), 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.
Title  relation composition 
Canonical name  RelationComposition 
Date of creation  20131024 16:58:43 
Last modified on  20131024 16:58:43 
Owner  Jon Awbrey (15246) 
Last modified by  Jon Awbrey (15246) 
Numerical id  40 
Author  Jon Awbrey (15246) 
Entry type  Topic 
Classification  msc 68R01 
Classification  msc 68P15 
Classification  msc 08A02 
Classification  msc 05C65 
Classification  msc 05B30 
Classification  msc 05B20 
Classification  msc 03E20 
Classification  msc 03B10 
Synonym  composition of relations 
Synonym  relational composition 
Synonym  relative multiplication 
Related topic  RelationTheory 
Related topic  RelationConstruction 
Related topic  RelationReduction 
Related topic  TacitExtension 
Related topic  LogicalMatrix 
Defines  relation composition 