Relational Composition

Definition

Given relations $R : A \nrightarrow B$ and $S : B \nrightarrow C$, the composite $S \circ R : A \nrightarrow C$ is:

$S \circ R = \{(a, c) \in A \times C : \exists b \in B. aRb \land bSc\}$

In words: $a$ is related to $c$ by $S \circ R$ iff there is some intermediate $b$ connecting them through $R$ and then $S$.

Notation Warning

Some sources write composition as $R ; S$ or $RS$. The order convention varies. Our convention: $(S \circ R)(a) = S(R(a))$.

Example

Let $R : \{1, 2, 3\} \nrightarrow \{a, b\}$ with $R = \{(1, a), (2, b), (3, a)\}$.

Let $S : \{a, b\} \nrightarrow \{X, Y\}$ with $S = \{(a, X), (b, Y), (b, X)\}$.

Then $S \circ R = \{(1, X), (2, X), (2, Y), (3, X)\}$.

Check: $1Ra$ and $aSX$, so $(1, X) \in S \circ R$. And $2Rb$ with $bSY$ and $bSX$, so $(2, Y), (2, X) \in S \circ R$.

Examinable Proof: Associativity

Theorem: Relational composition is associative: $(T \circ S) \circ R = T \circ (S \circ R)$.

Proof:

By extensionality, we show both sides relate the same pairs.

$a ((T \circ S) \circ R) d \iff \exists c. aRc \land c(T \circ S)d$ $\iff \exists c. aRc \land (\exists b. cSb \land bTd)$ $\iff \exists b, c. aRc \land cSb \land bTd$

$a (T \circ (S \circ R)) d \iff \exists b. a(S \circ R)b \land bTd$ $\iff \exists b. (\exists c. aRc \land cSb) \land bTd$ $\iff \exists b, c. aRc \land cSb \land bTd$

Both sides are equivalent to $\exists b, c. aRc \land cSb \land bTd$.

Therefore $(T \circ S) \circ R = T \circ (S \circ R)$.

Examinable Proof: Identity Laws

Theorem: The identity relation is a neutral element for composition.

$\text{id}_B \circ R = R = R \circ \text{id}_A$

for $R : A \nrightarrow B$.

Proof:

$a(\text{id}_B \circ R)b \iff \exists c \in B. aRc \land c\,\text{id}_B\,b$ $\iff \exists c \in B. aRc \land c = b$ $\iff aRb$

Similarly: $a(R \circ \text{id}_A)b \iff \exists c \in A. a\,\text{id}_A\,c \land cRb$ $\iff \exists c \in A. a = c \land cRb$ $\iff aRb$

Monoid Structure

The endo-relations $\text{Rel}(A, A)$ on a set $A$ form a monoid under composition:

• Associativity: $(R \circ S) \circ T = R \circ (S \circ T)$
• Identity: $R \circ \text{id}_A = R = \text{id}_A \circ R$

This is a foundational structure with many applications.

n-fold Iteration

For a relation $R$ on $A$, define the $n$-fold iteration:

$R^{\circ 0} = \text{id}_A$ $R^{\circ (n+1)} = R \circ R^{\circ n}$

Interpretation

• $R^{\circ 0}$: “be the same element”
• $R^{\circ 1} = R$: “take one $R$-step”
• $R^{\circ n}$: “take exactly $n$ $R$-steps”

The Path Relation

The path relation (or reflexive-transitive closure) is:

$R^{\circ *} = \bigcup_{n \geq 0} R^{\circ n}$

This relates $a$ to $b$ iff there is a path of length $\geq 0$ from $a$ to $b$.

Properties

• Always reflexive: $\text{id}_A \subseteq R^{\circ *}$
• Always transitive: $R^{\circ *} \circ R^{\circ *} = R^{\circ *}$

---

Summary

• $S \circ R = \{(a, c) : \exists b. aRb \land bSc\}$
• Composition is associative with identity $\text{id}$
• Endo-relations form a monoid under composition
• $R^{\circ n}$ is $n$-fold iteration; $R^{\circ *} = \bigcup_n R^{\circ n}$ is the path relation