Numbers and Sets | Part IA, 2006

Explain what is meant by an equivalence relation on a set AA.

If RR and SS are two equivalence relations on the same set AA, we define

RS={(x,z)A×A:R \circ S=\{(x, z) \in A \times A: there exists yAy \in A such that (x,y)R(x, y) \in R and (y,z)S}.(y, z) \in S\} .

Show that the following conditions are equivalent:

(i) RSR \circ S is a symmetric relation on AA;

(ii) RSR \circ S is a transitive relation on AA;

(iii) SRRSS \circ R \subseteq R \circ S;

(iv) RSR \circ S is the unique smallest equivalence relation on AA containing both RR and SS.

Show also that these conditions hold if A=ZA=\mathbb{Z} and RR and SS are the relations of congruence modulo mm and modulo nn, for some positive integers mm and nn.

Typos? Please submit corrections to this page on GitHub.