# Relation composition

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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 article on relation theory.

## Preliminaries

There are several ways to formalize the subject matter of relations. Relations and their combinations may be described in the logic of relative terms, in set theories of various kinds, and through a broadening of category theory from functions to relations in general.

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

 The first dimension of variation in syntax has to do with the correspondence between the order of operation and the linear order of terms on the page. 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:

 LALA = left application, left association. LARA = left application, right association. RALA = right application, left association. RARA = right application, right association.

## Definition

A notion of relational composition is to be defined that generalizes the usual notion of functional composition:

 Composing on the right,  followed by  results in a composite function formulated as  Composing on the left,  followed by  results in a composite function formulated as 

Note on notation. The ordinary symbol for functional composition is the composition sign, a small circle "" written between the names of the functions being composed, as  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”, as 

Generalizing the paradigm along parallel lines, the composition of a pair of dyadic relations is formulated in the following two ways:

 Composing on the right,  followed by  results in a composite relation formulated as  Composing on the left,  followed by  results in a composite relation formulated as 

## 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 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 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 use of logical conjunction, as denoted by the symbol Failed to parse (Missing texvc executable; please see math/README to configure.):
in expressions of the form Failed to parse (Missing texvc executable; please see math/README to configure.):
to define a triadic relation  in terms of a pair of dyadic relations Failed to parse (Missing texvc executable; please see math/README to configure.):
and Failed to parse (Missing texvc executable; please see math/README to configure.):

• The concepts of dyadic projection and projective determination, that are invoked in the “weak” notion of projective reducibility.

The relational composition Failed to parse (Missing texvc executable; please see math/README to configure.):

of a pair of dyadic relations Failed to parse (Missing texvc executable; please see math/README to configure.):
and Failed to parse (Missing texvc executable; please see math/README to configure.):
will be constructed in three stages, first, by taking the tacit extensions of Failed to parse (Missing texvc executable; please see math/README to configure.):
and Failed to parse (Missing texvc executable; please see math/README to configure.):
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 Failed to parse (Missing texvc executable; please see math/README to configure.):
of the relations Failed to parse (Missing texvc executable; please see math/README to configure.):
and Failed to parse (Missing texvc executable; please see math/README to configure.):

The construction of a relational composition in a specifically mathematical setting normally begins with 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, Failed to parse (Missing texvc executable; please see math/README to configure.):

as shown in Figure 1.
 o-------------------------------------------------o | | | o o | | |\ |\ | | | \ | \ | | | \ | \ | | | \ | \ | | | \ | \ | | | \ | \ | | | * \ | * \ | | X * Y X * Y | | \ * | \ * | | | \ G | \ H | | | \ | \ | | | \ | \ | | | \ | \ | | | \ | \ | | | \| \| | | o o | | | o-------------------------------------------------o Figure 1. Dyadic Relations G, H c X x Y

and Failed to parse (Missing texvc executable; please see math/README to configure.):
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 Failed to parse (Missing texvc executable; please see math/README to configure.):
In this case, both of the compositions Failed to parse (Missing texvc executable; please see math/README to configure.):
and Failed to parse (Missing texvc executable; please see math/README to configure.):
are defined.
• The second type of case occurs when  and  are distinct, but when it nevertheless makes sense to speak of a dyadic relation Failed to parse (Missing texvc executable; please see math/README to configure.):
that is isomorphic to Failed to parse (Missing texvc executable; please see math/README to configure.):
but living in the plane Failed to parse (Missing texvc executable; please see math/README to configure.):
that is, in the space of the cartesian product Failed to parse (Missing texvc executable; please see math/README to configure.):
for some set Failed to parse (Missing texvc executable; please see math/README to configure.):

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:

 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

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 Failed to parse (Missing texvc executable; please see math/README to configure.):

of a pair of dyadic relations Failed to parse (Missing texvc executable; please see math/README to configure.):

Definition. Failed to parse (Missing texvc executable; please see math/README to configure.):

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 Failed to parse (Missing texvc executable; please see math/README to configure.):

So, if one has started out with a dyadic relation of the shape Failed to parse (Missing texvc executable; please see math/README to configure.):
one merely lets Failed to parse (Missing texvc executable; please see math/README to configure.):
trading in the initial  for a new Failed to parse (Missing texvc executable; please see math/README to configure.):
as need be.

The projection Failed to parse (Missing texvc executable; please see math/README to configure.):

is just the projection of the cartesian cube Failed to parse (Missing texvc executable; please see math/README to configure.):
on the space of shape Failed to parse (Missing texvc executable; please see math/README to configure.):
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 “Failed to parse (Missing texvc executable; please see math/README to configure.): ” is extended to signify two other products with respect to a dyadic relation Failed to parse (Missing texvc executable; please see math/README to configure.):

and a subset Failed to parse (Missing texvc executable; please see math/README to configure.):
as follows:
Definition. Failed to parse (Missing texvc executable; please see math/README to configure.):

Definition. Failed to parse (Missing texvc executable; please see math/README to configure.):

Applying these definitions to the case Failed to parse (Missing texvc executable; please see math/README to configure.):

the two dyadic relations whose relational composition Failed to parse (Missing texvc executable; please see math/README to configure.):
is about to be defined, one finds:

These are just the appropriate special cases of the tacit extensions already defined.

In summary, then, the expression:

is equivalent to the expression:

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. Failed to parse (Missing texvc executable; please see math/README to configure.):

Figure 3 presents a geometric picture of what is involved in formulating a definition of the triadic relation Failed to parse (Missing texvc executable; please see math/README to configure.):

by way of a conjunction between the dyadic relation Failed to parse (Missing texvc executable; please see math/README to configure.):
as done for example by means of an expression of the following form:
• Failed to parse (Missing texvc executable; please see math/README to configure.):

 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

To interpret the Figure, visualize the triadic relation Failed to parse (Missing texvc executable; please see math/README to configure.):

as a body in Failed to parse (Missing texvc executable; please see math/README to configure.):

-space, while Failed to parse (Missing texvc executable; please see math/README to configure.):

is a figure in Failed to parse (Missing texvc executable; please see math/README to configure.):

-space and Failed to parse (Missing texvc executable; please see math/README to configure.):

is a figure in Failed to parse (Missing texvc executable; please see math/README to configure.):

-space.

are defined as follows:
• Failed to parse (Missing texvc executable; please see math/README to configure.):

• Failed to parse (Missing texvc executable; please see math/README to configure.):

• Failed to parse (Missing texvc executable; please see math/README to configure.):

For many purposes it suffices to indicate the dyadic projections of a triadic relation  by means of the briefer equivalents listed next:

• Failed to parse (Missing texvc executable; please see math/README to configure.):

• Failed to parse (Missing texvc executable; please see math/README to configure.):

• Failed to parse (Missing texvc executable; please see math/README to configure.):

In light of these definitions, Failed to parse (Missing texvc executable; please see math/README to configure.):

is a mapping from the set Failed to parse (Missing texvc executable; please see math/README to configure.):
of triadic relations over the domains Failed to parse (Missing texvc executable; please see math/README to configure.):
to the set Failed to parse (Missing texvc executable; please see math/README to configure.):
of dyadic relations over the domains Failed to parse (Missing texvc executable; please see math/README to configure.):
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 Failed to parse (Missing texvc executable; please see math/README to configure.):

whose members are just the triadic relations over Failed to parse (Missing texvc executable; please see math/README to configure.):
can be recognized as the set of all subsets of the cartesian product Failed to parse (Missing texvc executable; please see math/README to configure.):
also known as the power set of Failed to parse (Missing texvc executable; please see math/README to configure.):
and notated here as Failed to parse (Missing texvc executable; please see math/README to configure.):

• Failed to parse (Missing texvc executable; please see math/README to configure.):

Likewise, the power sets of the pairwise cartesian products encompass all the dyadic relations on pairs of distinct domains that can be chosen from Failed to parse (Missing texvc executable; please see math/README to configure.):

• Failed to parse (Missing texvc executable; please see math/README to configure.):

• Failed to parse (Missing texvc executable; please see math/README to configure.):

• Failed to parse (Missing texvc executable; please see math/README to configure.):

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, Failed to parse (Missing texvc executable; please see math/README to configure.):

• Failed to parse (Missing texvc executable; please see math/README to configure.):

• Failed to parse (Missing texvc executable; please see math/README to configure.):

• Failed to parse (Missing texvc executable; please see math/README to configure.):

the tacit extensions, Failed to parse (Missing texvc executable; please see math/README to configure.):

of Failed to parse (Missing texvc executable; please see math/README to configure.):
respectively, are defined as follows:
• Failed to parse (Missing texvc executable; please see math/README to configure.):

• Failed to parse (Missing texvc executable; please see math/README to configure.):

• Failed to parse (Missing texvc executable; please see math/README to configure.):

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, Failed to parse (Missing texvc executable; please see math/README to configure.):

The definition and illustration of relational composition presently under way makes use of the tacit extension of Failed to parse (Missing texvc executable; please see math/README to configure.):

to Failed to parse (Missing texvc executable; please see math/README to configure.):
and the tacit extension of Failed to parse (Missing texvc executable; please see math/README to configure.):
to Failed to parse (Missing texvc executable; please see math/README to configure.):
only.

Geometric illustrations of Failed to parse (Missing texvc executable; please see math/README to configure.):

and Failed to parse (Missing texvc executable; please see math/README to configure.):
are afforded by Figures 4 and 5, respectively.
 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
 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

A geometric interpretation can now be given that fleshes out in graphic form the meaning of a formula like the following:

• Failed to parse (Missing texvc executable; please see math/README to configure.):

The conjunction that is indicated by “Failed to parse (Missing texvc executable; please see math/README to configure.): ” corresponds as usual to an intersection of two sets, however, in this case it is the intersection of the tacit extensions Failed to parse (Missing texvc executable; please see math/README to configure.):

and Failed to parse (Missing texvc executable; please see math/README to configure.):

 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)

## 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, dyadic and triadic in the present case. Adding coordinates to the running Example produces the following Figure:

 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)

Thinking of relations in operational terms is facilitated by using variant notations for ordered tuples and sets of ordered tuples, namely, the ordered pair  is written Failed to parse (Missing texvc executable; please see math/README to configure.):

the ordered triple  is written Failed to parse (Missing texvc executable; please see math/README to configure.):
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 Failed to parse (Missing texvc executable; please see math/README to configure.):
and so on.

For example, translating the relations Failed to parse (Missing texvc executable; please see math/README to configure.):

into this notation produces the following summary of the data:

As often happens with abstract notations for functions and relations, the type information, in this case, the fact that Failed to parse (Missing texvc executable; please see math/README to configure.):

and Failed to parse (Missing texvc executable; please see math/README to configure.):
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 dyadic relations in terms of the medial projection of the intersection of their tacit extensions:

Here is the big picture, with all the pieces in place:

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

All that remains is to check the following collection of data and derivations against the situation represented in Figure 8.

## Matrix representation

We have it within our reach to pick up another way of representing dyadic 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.

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 Failed to parse (Missing texvc executable; please see math/README to configure.):

and Failed to parse (Missing texvc executable; please see math/README to configure.):

Here is the setup that we had before:

Let us recall the rule for finding the relational composition of a pair of dyadic relations. Given the dyadic relations Failed to parse (Missing texvc executable; please see math/README to configure.):

and Failed to parse (Missing texvc executable; please see math/README to configure.):
the composition of Failed to parse (Missing texvc executable; please see math/README to configure.):
is written as Failed to parse (Missing texvc executable; please see math/README to configure.):
or more simply as Failed to parse (Missing texvc executable; please see math/README to configure.):
and obtained as follows:

To compute Failed to parse (Missing texvc executable; please see math/README to configure.):

in general, where Failed to parse (Missing texvc executable; please see math/README to configure.):
and Failed to parse (Missing texvc executable; please see math/README to configure.):
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 Failed to parse (Missing texvc executable; please see math/README to configure.):
and Failed to parse (Missing texvc executable; please see math/README to configure.):

To find the relational composition Failed to parse (Missing texvc executable; please see math/README to configure.):

one may begin by writing it as a quasi-algebraic product:

Multiplying this out in accord with the applicable form of distributive law one obtains the following expansion:

Applying the rule that determines the product of elementary relations produces the following array:

Since the plus sign in this context represents an operation of logical disjunction or set-theoretic aggregation, all of the positive multiplicites count as one, and this gives the ultimate result:

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 Failed to parse (Missing texvc executable; please see math/README to configure.):

and Failed to parse (Missing texvc executable; please see math/README to configure.):
together to obtain their relational composite Failed to parse (Missing texvc executable; please see math/README to configure.):

Given the space Failed to parse (Missing texvc executable; please see math/README to configure.):

whose cardinality Failed to parse (Missing texvc executable; please see math/README to configure.):
is Failed to parse (Missing texvc executable; please see math/README to configure.):
there are Failed to parse (Missing texvc executable; please see math/README to configure.):
 Failed to parse (Missing texvc executable; please see math/README to configure.):
elementary relations of the form Failed to parse (Missing texvc executable; please see math/README to configure.):
where  and  range over the space   Although they might be organized in many different ways, it is convenient to regard the collection of elementary relations as arranged in a lexicographic block of the following form:

The relations Failed to parse (Missing texvc executable; please see math/README to configure.):

and Failed to parse (Missing texvc executable; please see math/README to configure.):
may then be regarded as logical sums of the following forms:

The notation Failed to parse (Missing texvc executable; please see math/README to configure.):

indicates a logical sum over the collection of elementary relations Failed to parse (Missing texvc executable; please see math/README to configure.):
while the factors Failed to parse (Missing texvc executable; please see math/README to configure.):
and Failed to parse (Missing texvc executable; please see math/README to configure.):
are values in the boolean domain Failed to parse (Missing texvc executable; please see math/README to configure.):
that are called the coefficients of the relations Failed to parse (Missing texvc executable; please see math/README to configure.):
and Failed to parse (Missing texvc executable; please see math/README to configure.):
respectively, with regard to the corresponding elementary relations Failed to parse (Missing texvc executable; please see math/README to configure.):

In general, for a dyadic relation  the coefficient Failed to parse (Missing texvc executable; please see math/README to configure.):

of the elementary relation Failed to parse (Missing texvc executable; please see math/README to configure.):
in the relation  will be  or  respectively, as Failed to parse (Missing texvc executable; please see math/README to configure.):
is excluded from or included in 

With these conventions in place, the expansions of Failed to parse (Missing texvc executable; please see math/README to configure.):

and Failed to parse (Missing texvc executable; please see math/README to configure.):
may be written out as follows:

Stripping down to the bare essentials, one obtains the following matrices of coefficients for the relations Failed to parse (Missing texvc executable; please see math/README to configure.):

and Failed to parse (Missing texvc executable; please see math/README to configure.):

These are the logical matrix representations of the dyadic relations Failed to parse (Missing texvc executable; please see math/README to configure.):

and Failed to parse (Missing texvc executable; please see math/README to configure.):

and Failed to parse (Missing texvc executable; please see math/README to configure.):
are viewed as logical sums then their relational composition Failed to parse (Missing texvc executable; please see math/README to configure.):
can be regarded as a product of sums, a fact that can be indicated as follows:

The composite relation Failed to parse (Missing texvc executable; please see math/README to configure.):

is itself a dyadic relation over the same space  in other words, Failed to parse (Missing texvc executable; please see math/README to configure.):
and this means that Failed to parse (Missing texvc executable; please see math/README to configure.):
must be amenable to being written as a logical sum of the following form:

In this formula, Failed to parse (Missing texvc executable; please see math/README to configure.):

is the coefficient of Failed to parse (Missing texvc executable; please see math/README to configure.):
with respect to the elementary relation Failed to parse (Missing texvc executable; please see math/README to configure.):

One of the best ways to reason out what Failed to parse (Missing texvc executable; please see math/README to configure.):

should be is to ask oneself what its coefficient Failed to parse (Missing texvc executable; please see math/README to configure.):
should be for each of the elementary relations Failed to parse (Missing texvc executable; please see math/README to configure.):
in turn.

So let us pose the question:

In order to answer this question, it helps to realize that the indicated product given above can be written in the following equivalent form:

A moment's thought will tell us that Failed to parse (Missing texvc executable; please see math/README to configure.):

if and only if there is an element  in  such that Failed to parse (Missing texvc executable; please see math/README to configure.):
and Failed to parse (Missing texvc executable; please see math/README to configure.):

Consequently, we have the result:

This follows from the properties of boolean arithmetic, specifically, from the fact that the product Failed to parse (Missing texvc executable; please see math/README to configure.):

is  if and only if both Failed to parse (Missing texvc executable; please see math/README to configure.):
and Failed to parse (Missing texvc executable; please see math/README to configure.):
are  and from the fact that Failed to parse (Missing texvc executable; please see math/README to configure.):
is equal to  just in case some Failed to parse (Missing texvc executable; please see math/README to configure.):
is 

All that remains in order to obtain a computational formula for the relational composite Failed to parse (Missing texvc executable; please see math/README to configure.):

and Failed to parse (Missing texvc executable; please see math/README to configure.):
is to collect the coefficients Failed to parse (Missing texvc executable; please see math/README to configure.):
as  and  range over 

This is the logical analogue of matrix multiplication in linear algebra, the difference in the logical setting being that all of the operations performed on coefficients take place in a system of boolean arithmetic where summation corresponds to logical disjunction and multiplication corresponds to logical conjunction.

By way of disentangling this formula, one may notice that the form Failed to parse (Missing texvc executable; please see math/README to configure.):

is what is usually called a scalar product.  In this case it is the scalar product of the Failed to parse (Missing texvc executable; please see math/README to configure.):
row of Failed to parse (Missing texvc executable; please see math/README to configure.):
with the  column of Failed to parse (Missing texvc executable; please see math/README to configure.):

To make this statement more concrete, let us go back to the examples of Failed to parse (Missing texvc executable; please see math/README to configure.):

and Failed to parse (Missing texvc executable; please see math/README to configure.):
we came in with:

The formula for computing Failed to parse (Missing texvc executable; please see math/README to configure.):

says the following:

As it happens, it is possible to make exceedingly light work of this example, since there is only one row of Failed to parse (Missing texvc executable; please see math/README to configure.):

and one column of Failed to parse (Missing texvc executable; please see math/README to configure.):
that are not all zeroes.  Taking the scalar product, in a logical way, of the fourth row of Failed to parse (Missing texvc executable; please see math/README to configure.):
with the fourth column of Failed to parse (Missing texvc executable; please see math/README to configure.):
produces the sole non-zero entry for the matrix of Failed to parse (Missing texvc executable; please see math/README to configure.):

## 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 graphs, or bigraphs for short.

Here is what Failed to parse (Missing texvc executable; please see math/README to configure.):

and Failed to parse (Missing texvc executable; please see math/README to configure.):
look like in the bigraph picture:
 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 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

These graphs may be read to say:

To form the composite relation Failed to parse (Missing texvc executable; please see math/README to configure.):

one simply follows the bigraph for Failed to parse (Missing texvc executable; please see math/README to configure.):
by the bigraph for Failed to parse (Missing texvc executable; please see math/README to configure.):
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 Failed to parse (Missing texvc executable; please see math/README to configure.):

Here's how it looks in pictures:

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

Once again we find that Failed to parse (Missing texvc executable; please see math/README to configure.):

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 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 Failed to parse (Missing texvc executable; please see math/README to configure.):

as follows:

Here are the bigraph pictures:

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

To form the composite relation Failed to parse (Missing texvc executable; please see math/README to configure.):

one simply follows the bigraph for  by the bigraph for Failed to parse (Missing texvc executable; please see math/README to configure.):
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 Failed to parse (Missing texvc executable; please see math/README to configure.):

Here's how it looks in pictures:

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

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 Failed to parse (Missing texvc executable; please see math/README to configure.):

between  and  in  is given as follows:

Graphically interpreted, this is a sum over paths. Starting at the node Failed to parse (Missing texvc executable; please see math/README to configure.):

being  indicates that there is an edge in the bigraph of  from node  to node  and Failed to parse (Missing texvc executable; please see math/README to configure.):
being  indicates that there is an edge in the bigraph of Failed to parse (Missing texvc executable; please see math/README to configure.):
from node  to node Failed to parse (Missing texvc executable; please see math/README to configure.):
So the Failed to parse (Missing texvc executable; please see math/README to configure.):
ranges over all possible intermediaries  ascending from  to  just as soon as there happens to be a path of length two between nodes  and Failed to parse (Missing texvc executable; please see math/README to configure.):

It is instructive at this point to compute the other possible composition that can be formed from  and Failed to parse (Missing texvc executable; please see math/README to configure.):

namely, the composition Failed to parse (Missing texvc executable; please see math/README to configure.):
that takes  and Failed to parse (Missing texvc executable; please see math/README to configure.):
in the opposite order.  Here is the graphic computation:
 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 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

In sum, Failed to parse (Missing texvc executable; please see math/README to configure.):

This example affords sufficient evidence that relational composition, just like its kindred, matrix multiplication, is a non-commutative algebraic operation.

## References

• Ulam, S.M., and 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.

## Bibliography

• Mathematical Society of Japan, Encyclopedic Dictionary of Mathematics, 2nd edition, 2 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.
• 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.

## Syllabus

### Relational concepts

 Relation Relation composition Relation construction Relation reduction

## Document history

Portions of the above article were adapted from the following sources under the GNU Free Documentation License, under other applicable licenses, or by permission of the copyright holders.