ABSTRACT
For more definitions relating to this section, see Section 2.6. Let A and B be sets. A binary relation from A to B is a subset of the ordered pairs A × B = {(x, y) : x ∈ A, y ∈ B}.
If R is a binary relation from A to B, and S is a binary relation from B to C, the composition of R with S is a binary relation from A to C defined by
R ◦ S = {(x, z) ∈ A× C : ∃y ∈ B[(x, y) ∈ R, (y, z) ∈ S]}. (Caution: this notation can differ with the common notation for composition of functions-see comments following that definition.) Note that if R ⊆ A × B, S ⊆ B × C, and T ⊆ C ×D are binary relations, then
(R ◦ S) ◦ T = R ◦ (S ◦ T ); so in a sense, composition of relations is associative.
