 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2006/ia/paper-4/5e/ii/solution

Codex  0 Created 2026-09-24 Updated 2026-10-14

T

is transitive exactly when

T \circ T \subseteq T

. If condition (iii) holds, associativity and monotonicity of composition of relations give

T \circ T = R \circ S \circ R \circ S \subseteq R \circ R \circ S \circ S = R \circ S = T .

Hence (iii) implies (ii). Conversely, the inclusions

R, S \subseteq T

imply

S \circ R \subseteq T \circ T .

T

is a transitive relation, the right side lies in

T

, which is condition (iii). Thus (ii) and (iii) are equivalent.

 New to topics? Read the docs here!