What You'll Learn
You'll learn how to combine two relations by following paths through shared intermediate elements, forming a new relation called their composition.
The Core Idea
Imagine you have two relations: R relates elements from set A to set B, and S relates elements from set B to set C. The composition of these relations, written S ∘ R (read "S composed with R"), creates a direct relation from A to C.
Here's the rule: (a, c) is in S ∘ R if and only if there exists some intermediate element b in B such that (a, b) is in R and (b, c) is in S. You're essentially following a two-step path: first through R, then through S.
Think of it like connecting flights: if there's a flight from city A to city B (relation R) and another from city B to city C (relation S), then there's a composed "travel route" from A to C (relation S ∘ R).
Computing a Composition
Example: Let A = {1, 2}, B = {x, y}, C = {α, β}.
- R = {(1, x), (1, y), (2, x)} (from A to B)
- S = {(x, α), (y, β)} (from B to C)
To find S ∘ R:
- From 1: (1, x) in R and (x, α) in S → (1, α) in S ∘ R
- From 1: (1, y) in R and (y, β) in S → (1, β) in S ∘ R
- From 2: (2, x) in R and (x, α) in S → (2, α) in S ∘ R
Therefore, S ∘ R = {(1, α), (1, β), (2, α)}.
Notice the order matters: we apply R first, then S, even though S is written first in the notation.
Key Takeaway: The composition S ∘ R of two relations connects elements from the first set to the last by finding all valid two-step paths through an intermediate set.