3. On problems 3 and 4, we explore the relationship between equivalence relations and partitions. We have already seen this before the congruence classes modulo n partition the integers into n classes, which are all disjoint. We had previously proved this specifically about congruences, but it turns out we can prove this using properties of equivalence relations. For integers x and y, let x ~2 y iff x = y (mod 4). (a) Describe the equivalence classes. (b) Suppose [a] n [b] + 0. That is, suppose there is c such that a = c (mod 4) and b = c (mod 4). Show that a = b (mod 4) using the definition of congruences. That is: suppose there is k such that a - c = 4k, and k2 such that b-c= 4k2. Show that there is k3 such that a - b = 4ks. (C) Now show the previous result using just the symmetric and transitive properties of congruences. That is given a = c(mod 4) and b = c (mod 4), show that a = b (mod 4) using the fact that congruence mod 4 is symmetric and transitive. (d) Continuing above, show that if a = b (mod 4), then [a] = [b]. Hint: you must show that every element of (a) is an element of [b) and vice versa. Let c (a). Then a = c(mod 4). Show that b = c (mod 4) (again: use symmetry and transitivity), which shows ce [b]. Then let ce [b] and show that (c) (a) using a similar argument. 3. On problems 3 and 4, we explore the relationship between equivalence relations and partitions. We have already seen this before the congruence classes modulo n partition the integers into n classes, which are all disjoint. We had previously proved this specifically about congruences, but it turns out we can prove this using properties of equivalence relations. For integers x and y, let x ~2 y iff x = y (mod 4). (a) Describe the equivalence classes. (b) Suppose [a] n [b] + 0. That is, suppose there is c such that a = c (mod 4) and b = c (mod 4). Show that a = b (mod 4) using the definition of congruences. That is: suppose there is k such that a - c = 4k, and k2 such that b-c= 4k2. Show that there is k3 such that a - b = 4ks. (C) Now show the previous result using just the symmetric and transitive properties of congruences. That is given a = c(mod 4) and b = c (mod 4), show that a = b (mod 4) using the fact that congruence mod 4 is symmetric and transitive. (d) Continuing above, show that if a = b (mod 4), then [a] = [b]. Hint: you must show that every element of (a) is an element of [b) and vice versa. Let c (a). Then a = c(mod 4). Show that b = c (mod 4) (again: use symmetry and transitivity), which shows ce [b]. Then let ce [b] and show that (c) (a) using a similar argument