relation composition

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

2 Definition

• 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 2-adic 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 2-adic 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

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, 2-adic and 3-adic in the present case.

See main entry (http://planetmath.org/AlgebraicRepresentationOfRelationComposition) for details.

5 Matrix representation

See main entry (http://planetmath.org/MatrixRepresentationOfRelationComposition) for details.

6 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 , 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 2013-10-24 16:58:43 Last modified on 2013-10-24 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