Composition of relations
In mathematics, particularly in set theory and discrete mathematics, the composition of binary relations is a fundamental operation that combines two relations defined on sets to produce a new relation. Specifically, if R is a binary relation from a set A to a set B (i.e., R \subseteq A \times B) and S is a binary relation from B to a set C (i.e., S \subseteq B \times C), then the composition S \circ R (or sometimes denoted R ; S) is the binary relation from A to C defined by (a, c) \in S \circ R if and only if there exists some b \in B such that (a, b) \in R and (b, c) \in S.[1][2] This operation generalizes the composition of functions, as any function can be viewed as a special type of relation, and it extends the concept by allowing intermediate elements without requiring uniqueness or totality.[3] The composition of relations exhibits several key properties that mirror those of function composition but apply more broadly. Notably, it is associative: for relations R: A \to B, S: B \to C, and T: C \to D, the equality T \circ (S \circ R) = (T \circ S) \circ R holds, meaning parentheses can be omitted in chains of compositions without ambiguity.[4] Unlike function composition, relation composition does not require invertibility, but it interacts meaningfully with other relation operations like union, intersection, and converse; for example, the converse of a composition satisfies (S \circ R)^{-1} = R^{-1} \circ S^{-1}.[5] These properties make composition a cornerstone in relational algebra and category theory, where relations can be seen as morphisms between sets. Beyond pure mathematics, the composition of relations finds practical applications in computer science and database theory. In relational databases, composing relations corresponds to the natural join operation, enabling queries that chain conditions across multiple tables.[6] It also underpins graph theory, where relations represent edges, and composition models paths of length two or more. The formal study of the calculus of binary relations originated in the 19th century, introduced by Augustus De Morgan in 1860 and further developed by Charles Sanders Peirce and Ernst Schröder.[7]Fundamentals
Definition
In set theory, given binary relations R \subseteq X \times Y and S \subseteq Y \times Z, their composition, often denoted S \circ R, is the binary relation S \circ R \subseteq X \times Z defined as the set of all ordered pairs (x, z) such that there exists some y \in Y satisfying (x, y) \in R and (y, z) \in S.[8] This construction captures the transitive linkage between elements of X and Z through intermediate elements in Y, formalized via existential quantification over Y.[8] When R and S are functional relations—meaning each element in the domain maps to exactly one element in the codomain—the composition S \circ R reduces precisely to the standard composition of functions, where (S \circ R)(x) = S(R(x)) for x \in X.[9] The concept of relation composition, introduced by Augustus de Morgan in 1860 and developed by Charles Sanders Peirce, was systematized by Ernst Schröder in the 1890s, particularly in his work on the calculus of relations within the algebra of logic.[7][10]Notation and Variations
The composition of two binary relations R \subseteq X \times Y and S \subseteq Y \times Z is commonly denoted in modern mathematical literature as S \circ R, where the circle symbol \circ indicates the relational product, with R applied first followed by S.[11] This notation aligns with the standard convention for function composition, emphasizing the sequential application from right to left. An alternative infix notation uses juxtaposition, writing RS for the same operation, particularly in contexts where the relations are treated as elements of a monoid under composition; however, this form requires care to distinguish it from other binary operations on relations.[11] Historically, the semicolon notation R ; S—again with R first—was introduced by Ernst Schröder in his 1895 treatise on the algebra and logic of relative theory, where it served as the infix operator for the relative product of relatives (binary relations). Alfred Tarski adopted and formalized this semicolon notation in his 1941 axiomatic treatment of the calculus of relations, defining x \, R ; S \, y to hold if there exists z such that x \, R \, z and z \, S \, y, and using it throughout his development of relation algebras.[12] In domain-specific formalisms, variations reflect syntactic or applicative needs. The Z notation, a formal specification language for software, employs the semicolon ; for forward relational composition (with right-to-left application, as in R ; S), but also supports the dedicated Unicode symbol \twoheadrightarrow (U+2A3E) to explicitly denote relational composition in typeset documents. In relational algebra, foundational to database query languages, direct composition of relations is not a primitive but is realized through the natural join operator \bowtie, which combines tuples from two relations on matching attributes, effectively computing the relational product under equality conditions.[13] A key concern with juxtaposition RS is its potential ambiguity, as it may be misinterpreted as the union R \cup S or, less commonly, the Cartesian product R \times S in texts where these operations lack explicit symbols; authors often mitigate this by reserving juxtaposition strictly for composition or qualifying it contextually.[11]Properties and Generalizations
Algebraic Properties
Relation composition exhibits several fundamental algebraic properties that mirror those of binary operations in abstract algebra. Foremost among these is associativity: for binary relations R \subseteq X \times Y, S \subseteq Y \times Z, and T \subseteq Z \times W, the composition satisfies (R \circ S) \circ T = R \circ (S \circ T). This property allows for unambiguous iteration of compositions without parentheses, facilitating the definition of powers of relations, such as transitive closures.[14] The operation also possesses an identity element. For a set X, the identity relation I_X = \{(x, x) \mid x \in X\} \subseteq X \times X acts as a two-sided unit under composition: if R \subseteq X \times Y, then R \circ I_X = R and I_Y \circ R = R. This neutral behavior ensures that adjoining the identity does not alter the relation, analogous to the role of the identity function in function composition.[15][14] In addition, the empty relation \emptyset functions as an absorbing zero element. For any relation R compatible with \emptyset, the compositions R \circ \emptyset = \emptyset and \emptyset \circ R = \emptyset. This absorption property highlights how the absence of connecting elements in one relation renders the overall composition void, underscoring the set-theoretic foundations of the operation.[14] These properties collectively endow the collection of all binary relations on a fixed set X, denoted \mathrm{Rel}(X), with a monoid structure under composition. Specifically, (\mathrm{Rel}(X), \circ, I_X) forms a monoid, where associativity ensures well-defined multiple compositions and I_X provides the required unit. This algebraic framework is central to relation algebra and enables the study of relations as elements in a semigroup with identity.[15][14] Composition further interacts compatibly with the converse operation on relations. The converse of a relation R \subseteq X \times Y is R^T = \{(y, x) \mid (x, y) \in R\} \subseteq Y \times X, which reverses the direction of the relation. For compatible relations R and S, the key identity holds: (R \circ S)^T = S^T \circ R^T. This reversal property preserves the chaining structure while flipping the order, proving useful in analyzing symmetries and inverses in relational systems.[14]Mathematical Generalizations
In category theory, the composition of relations generalizes to the category Rel, where objects are sets and morphisms are binary relations between them, with composition defined by the standard relational product: for relations R \subseteq A \times B and S \subseteq B \times C, the composite S \circ R = \{(a, c) \mid \exists b \in B : (a, b) \in R \land (b, c) \in S\}.73066-8) This category is dagger-compact and serves as the primary example of an allegory, a bicategory where every morphism has a converse, enabling a calculus of relations that captures properties like associativity and converse preservation under composition.73066-8) The structure of Rel highlights how relation composition extends beyond mere set-theoretic operations to a framework supporting enriched categorical constructions, such as monoidal structures induced by Cartesian products. In more abstract settings, such as regular categories—those with finite limits, coequalizers of kernel pairs, and pullback-stable regular epimorphisms—internal relations are defined using spans or jointly monic pairs. A relation from object r to s is a jointly monic span r \leftarrow x \twoheadrightarrow s, where the pair (f: x \to r, g: x \to s) induces a monomorphism \langle f, g \rangle: x \to r \times s, representing subobjects of the product.[16] Composition of two such relations, say r \leftarrow x \twoheadrightarrow s and s \leftarrow y \twoheadrightarrow t, proceeds via the pullback x \times_s y along the codomain and domain maps, followed by taking the regular image of the induced map to r \times t to ensure the result is again a jointly monic span.[16] This construction yields a bicategory of relations internal to the regular category, equivalent to the 2-category of relational po-categories, where composition is associative and independent of the choice of span representatives.[16] Linear relations provide a further generalization over vector spaces or modules, where a relation between vector spaces V and W over a field k (such as \mathbb{F}_2) is a linear subspace L \subseteq V \times W, closed under addition and scalar multiplication.[17] Composition mirrors the relational case but leverages linearity: for L \subseteq V \times W and M \subseteq W \times U, the composite is L \circ M = \{(v, u) \mid \exists w \in W.\ (v, w) \in L \land (w, u) \in M \}, which is again a linear subspace of V \times U. In finite-dimensional settings over \mathbb{F}_2, the category of linear relations is isomorphic to the phase-free fragment of the qubit ZX-calculus, where linear maps and relations are depicted as Z- and X-spiders connected by wires, allowing diagrammatic simplification of composites through rewrite rules like the bialgebra laws.[18] This framework is particularly useful in quantum information, where ZX-diagrams encode compositions of linear relations on Hilbert spaces. Profunctors, also known as distributors, extend relation composition to arbitrary categories, generalizing binary relations as bifunctors P: C^{op} \times D \to \mathbf{Set} that assign to objects c \in C and d \in D a set of "relations" between them. Composition of profunctors P: C \nrightarrow D and Q: D \nrightarrow E is given by the coend formula (Q \circ P)(c, e) = \int^{d \in D} Q(d, e) \times P(c, d), which quotients by the actions of morphisms in D to ensure functoriality, forming the bicategory \mathbf{Prof} of categories, profunctors, and natural transformations. When restricted to the category of sets, profunctors recover ordinary relations, with composition reducing to the relational product, but in general, this construction applies to arrow categories (where objects are arrows in a base category and morphisms are commuting squares) by viewing arrows as fibrations and profunctors as generalized relations between them, preserving associativity up to isomorphism in the bicategorical sense. This abstraction underpins applications in database theory and open systems modeling, where profunctor composition models relational queries across structured categories.Representation and Computation
Matrix Composition
A binary relation R \subseteq X \times Y on finite sets X = \{x_1, \dots, x_m\} and Y = \{y_1, \dots, y_n\} can be represented by an m \times n logical matrix M_R, where the entry (M_R)_{i,j} = 1 if (x_i, y_j) \in R and $0 otherwise.[19] This representation uses Boolean entries to encode membership directly, facilitating algebraic manipulation. The composition S \circ R, where R \subseteq X \times Y and S \subseteq Y \times Z for finite Z = \{z_1, \dots, z_p\}, corresponds to the Boolean matrix product M_{S \circ R} = M_R * M_S. In this product, addition is the logical OR (+, with $1 + 1 = 1) and multiplication is the logical AND (\cdot).[20] Thus, the entry in row i and column k of M_{S \circ R} is computed as \bigvee_{j=1}^n \left( (M_R)_{i,j} \wedge (M_S)_{j,k} \right), indicating existence of an intermediate element y_j connecting x_i to z_k.[19] For illustration, consider sets X = \{1,2\}, Y = \{a,b\}, Z = \{A,B\}, with R = \{(1,a), (2,a), (2,b)\} so M_R = \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}, and S = \{(a,A), (b,B)\} so M_S = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}. The composition yields S \circ R = \{(1,A), (2,A), (2,B)\}, with M_{S \circ R} = \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}. [21] This matrix approach enables efficient computation of relation compositions for finite sets, as the Boolean product can be evaluated in O(m n p) time using standard algorithms adapted for logical operations.[20] Moreover, when X = Y = Z, the logical matrix aligns with the adjacency matrix of the directed graph representing the relation, allowing composition to model path existence in graph theory.[19]Heterogeneous Relations
Heterogeneous relations arise in the composition of binary relations where the underlying sets differ in type or cardinality, allowing for more general structures beyond homogeneous cases. A relation R \subseteq X \times Y is heterogeneous if X and Y are distinct sets, possibly with |X| \neq |Y|. The composition with another relation S \subseteq Y \times Z follows the standard definition: (x, z) \in S \circ R if and only if there exists y \in Y such that (x, y) \in R and (y, z) \in S. This is valid whenever the codomain of R aligns with the domain of S, even if X \neq Z or |X| \neq |Z|, enabling compositions across mismatched domains and codomains. Key constructions in heterogeneous relation algebra involve the converse relation R^T \subseteq Y \times X, defined by (y, x) \in R^T if and only if (x, y) \in R. The self-composition R R^T \subseteq X \times X captures connectivity within X; in particular, R is total on X (every x \in X relates to some y \in Y) if and only if the identity relation I_X \subseteq X \times X satisfies I_X \subseteq R R^T, since (x, x) \in R R^T holds precisely when there exists y with (x, y) \in R. Dually, R^T R \subseteq Y \times Y assesses coverage on Y; R is surjective on Y (every y \in Y is related to by some x \in X) if and only if I_Y \subseteq R^T R. These tests are fundamental for verifying completeness and exhaustiveness in relational mappings between disparate sets.[19] Heterogeneous relations are computationally represented by rectangular Boolean matrices, with rows indexed by elements of X and columns by Y, where entry (i, j) = 1 if (x_i, y_j) \in R and 0 otherwise. For composition S \circ R with R an |X| \times |Y| matrix and S a |Y| \times |Z| matrix, the result is the |X| \times |Z| Boolean matrix product: (S \circ R)_{i k} = \bigvee_{j=1}^{|Y|} \left( R_{i j} \wedge S_{j k} \right), using disjunction (\vee) as addition and conjunction (\wedge) as multiplication in the Boolean semiring. This accommodates dimensional heterogeneity, unlike square matrices in homogeneous cases. Consider sets A = \{\text{[France](/page/France)}, \text{[Germany](/page/Germany)}, \text{[Italy](/page/Italy)}, \text{[Switzerland](/page/Switzerland)}\} of countries and B = \{\text{[French](/page/French)}, \text{[German](/page/German)}, \text{[Italian](/page/Italian)}\} of languages. The border relation R \subseteq A \times A (symmetric) includes: France–Germany, France–Switzerland, Germany–Switzerland, Switzerland–Italy. Its matrix (rows/columns: F, G, I, S) is: R = \begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{pmatrix}. The speaking relation S \subseteq A \times B is given by:- France relates to French,
- Germany to German,
- Italy to Italian,
- Switzerland to French, German, and Italian.