Recipe

Compute the composite of two relations

Use when: you're given R from A to B and S from B to C, and asked for the composite S∘R

Goal: the full list of pairs (a,c) reachable by an R-step into B followed by an S-step out of B

Taught in Combining and composing relations

1. 1

   In S\circ R, R runs first (from A to B), then S runs second (from B to C); read right to left, the same order as function composition.

   Example

   For R from \{1,2,3\} to itself and S from \{2,3\} to \{x,y\}, S\circ R chains R first, then S.

   Why: composition order is not arbitrary -- swapping which relation runs first generally produces a completely different result.

2. 2

   Take each pair (a,b) in R, then search S for a pair starting with that same b; a match gives a new pair (a,c).

   Example

   R=\{(1,2),(2,3)\}, S=\{(2,x),(3,y)\}: from (1,2) in R, find (2,x) in S, giving (1,x).

   • some b in R's second slot has no matching pair starting with b in S — that R-pair contributes nothing to the composite.
   • b does have a matching pair in S — record the resulting (a,c) pair.

   Why: the middle element b is exactly the layover that has to connect an R-pair to an S-pair for a composite pair to exist.

3. 3

   Repeat the previous step for every pair of R, then gather all the resulting (a,c) pairs into one set, without repeats.

   Example

   From (1,2): (1,x). From (2,3): (2,y). So S\circ R = \{(1,x),(2,y)\}.

   Why: the composite relation is defined as the full set of pairs reachable this way, and a set never lists a pair twice.