Definition:Composition of Relations

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

New contributors: Refactoring is a task which is expected to be undertaken by experienced editors only.

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

  • Results about composite relations can be found here.


Illustration

The following is an Euler diagram illustrating the relations between the various entities.

CompositionOfRelations.png

In the above:

$\Img \RR$ denotes the image of a relation $\RR$
$\Preimg \RR$ denotes the preimage of a relation $\RR$.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Composition_of_Relations&oldid=659324"