1. What Composition of Relations Means
The composition of relations links two relations together through a middle set. If one relation connects a → b and another connects b → c, then their composition connects a → c. This creates a new relation by joining the chains through the shared element b.
2. Formal Setup
To define composition, two relations are involved:
- R from A to B
- S from B to C
The composition S ∘ R is a relation from A to C.
2.1. Definition
S \circ R = \{ (a,c) \mid \exists\ b \in B \text{ such that } (a,b) \in R \text{ and } (b,c) \in S \}
3. Understanding the Idea
The relation R takes you from A to B. The relation S takes you further from B to C. Composition simply joins these two steps into one longer step from A to C.
3.1. Chain Picture
a \to b \to c \; \Rightarrow \; a \to c
4. Example to See How Composition Works
Let A = {1,2}, B = {3,4}, C = {5,6}.
Define:
R = \{(1,3),(2,4)\}
S = \{(3,5),(4,6)\}
To form S ∘ R, link each pair in R to the matching pair in S.
4.1. Step-by-Step Linking
- 1 → 3 (from R) and 3 → 5 (from S) give 1 → 5
- 2 → 4 (from R) and 4 → 6 (from S) give 2 → 6
4.2. Final Composition
S \circ R = \{(1,5),(2,6)\}
5. Example with Extra Pairs
If the relations have more than one possible link, composition collects all such connections.
5.1. Illustration
R = \{(1,3),(1,4)\},\quad S = \{(3,5),(4,5),(4,6)\}
Possible chains:
- 1 → 3 → 5 → gives (1,5)
- 1 → 4 → 5 → gives (1,5)
- 1 → 4 → 6 → gives (1,6)
So:
S \circ R = \{(1,5),(1,6)\}
6. Composition Is Not Always Commutative
Composition depends on the direction of the links. In general:
S \circ R \neq R \circ S
The order matters because the middle set and the steps may not match when reversed.
7. Where Composition of Relations Appears
Composition is used whenever steps connect through an intermediate element. Typical examples include:
- Paths in graphs
- Successive mappings
- Linking transformations
- Combining relations to form new ones