Solution

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

An equivalence relation on a set is a binary relation that is reflexive, symmetric and transitive: every element is related to itself, related pairs may be reversed, and two consecutive related pairs imply the pair of endpoints is related.
Write , using the printed left-to-right composition of relations convention. Reflexivity implies and , and hence is reflexive. Reversing a two-step chain gives
since are symmetric. Also and : one inclusion is transitivity, and the reverse follows by inserting a reflexive step. These elementary identities supply the equivalences below, without presuming that a composite of equivalence relations is automatically an equivalence relation.

New to topics? Read the docs here!