Definition:Composition of Relations
Jump to navigation
Jump to search
Definition
Let $\RR_1 \subseteq S_1 \times T_1$ and $\RR_2 \subseteq S_2 \times T_2$ be relations.
Then the composite of $\RR_1$ and $\RR_2$ is defined and denoted as:
- $\RR_2 \circ \RR_1 := \set {\tuple {x, z} \in S_1 \times T_2: \exists y \in S_2 \cap T_1: \tuple {x, y} \in \RR_1 \land \tuple {y, z} \in \RR_2}$
Some authors write $\RR_2 \circ \RR_1$ as $\RR_2 \RR_1$.
It is clear that the composite relation $\RR_2 \circ \RR_1$ can also be defined as:
- $\map {\RR_2 \circ \RR_1} {S_1} = \map {\RR_2} {\map {\RR_1} {S_1} }$
Note that:
- $(1): \quad \RR_2 \circ \RR_1 \subseteq S_1 \times T_2$
- $(2): \quad$ The domain of $R_2 \circ \RR_1$ equals the domain of $\RR_1$, that is, $S_1$
- $(3): \quad$ The codomain of $R_2 \circ \RR_1$ equals the codomain of $\RR_2$, that is, $T_2$.
Also see
- Image of Composite Relation
- Preimage of Composite Relation
- Composition of Mappings is Composition of Relations
Illustration
The following is an Euler diagram illustrating the relations between the various entities.
In the above:
- $\Img \RR$ denotes the image of a relation $\RR$
- $\Preimg \RR$ denotes the preimage of a relation $\RR$.
Sources
- 1955: John L. Kelley: General Topology ... (previous) ... (next): Chapter $0$: Relations
- 1960: Paul R. Halmos: Naive Set Theory ... (previous) ... (next): $\S 10$: Inverses and Composites
- 1965: Seth Warner: Modern Algebra ... (previous) ... (next): Exercise $5.8$
- 1967: George McCarty: Topology: An Introduction with Application to Topological Groups ... (previous) ... (next): Chapter $\text{I}$: Sets and Functions: Problem $\text{AA}$: Relations
- 1971: Gaisi Takeuti and Wilson M. Zaring: Introduction to Axiomatic Set Theory: $\S 6.6$
- 2010: Steve Awodey: Category Theory (2nd ed.) ... (previous) ... (next): $\S 1.4.4$