Course contentsShow
← Mathematics
Lesson 2548 of 3,12151. Discrete Math — Sets, Relations, FunctionsFree lesson

Composition of Relations

Define the composition of two relations and compute the resulting relation by following paths through intermediate elements.

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.