M

1. (Equivalence Relationa). Recall that given a relation U on a set A, the transitive closure of the symmetric closure of the reflexive closure of U is the least equivalence E relation on A which contains U; the relation E is called the cquivalence closure of the relation U. Use this result to find the equivalence closure of the relation U={(1,2),(2,1)+(2,3),(3,2)} on the set A={1,2,3,4} by working as follows. (i) Find the reflexive closure R of U, R=reflexive(U)=UA=U{(1,1),(2,2),(3,3),(4,4)}. (ii) Find the symmetric closure S of R, S=symmetric(R)=RR1. (iii) Find the transitive closure T of the relation S, T=transitive(S)=SS2S3S4 (to find the relation T work as you did in HW \#4). (iv) By (i) and (iii), the relation T must be reflexive and transitive. Verify directly that T is symmetric (as it must be since any power of a symmetric relation is also symmetric, why?), thereby proving that T is an equivalence relation, and then find the equivalence classes by T