# 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}$

This page has been identified as a candidate for refactoring of medium complexity.In particular: There are two definitions here which need to be proved to be equal.Until this has been finished, please leave
`{{Refactor}}` in the code.
Because of the underlying complexity of the work needed, it is recommended that you do not embark on a refactoring task until you have become familiar with the structural nature of pages of $\mathsf{Pr} \infty \mathsf{fWiki}$.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{Refactor}}` from the code. |

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 $\RR_2 \circ \RR_1$ equals the domain of $\RR_1$, that is, $S_1$
- $(3): \quad$ The codomain of $\RR_2 \circ \RR_1$ equals the codomain of $\RR_2$, that is, $T_2$.

## Also denoted as

Some authors write $\RR_2 \circ \RR_1$ as $\RR_2 \RR_1$.

## Also see

- Image of Composite Relation
- Preimage of Composite Relation
- Composition of Mappings is Composition of Relations

- Results about
**composite relations**can be found**here**.

## 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): Chapter $\text I$: Algebraic Structures: $\S 5$: Composites and Inverses of Functions: 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$