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

There is believed to be a mistake here, possibly a typo.In particular: I think this should be $\RR_2 \circ \RR_1 \sqbrk {S_1} \equal \RR_2 \sqbrk {\RR_1 \sqbrk {S_1} \cap S_2}$, in which case this doesn't define a relation, otherwise the notation needs to be definedYou can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by reviewing it, and either correcting it or adding some explanatory material as to why you believe it is actually correct after all.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 `{{Mistake}}` from the code.If you would welcome a second opinion as to whether your work is correct, add a call to `{{Proofread}}` the page. |

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$