Unit 21 Exercises

1. Which of the following relations on {1, 2, 3, 4} are equivalence relations?  Determine the properties of an equivalence relation that the others lack.

a) {(1, 1), (2, 2), (3, 3), (4, 4)}

b) {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4)}

c) {(1, 1), (1, 2), (1, 4), (2, 2), (2, 4), (3, 3), (4, 1), (4, 2), (4, 4)}

2. Suppose that A is a nonempty set, and f is a function that has A as its domain.  Let R be the relation on A consisting of all ordered pairs (x, y) where f(x) = f(y).

1. Show that R is an equivalence relation on A.
2. What are the equivalence classes of R ?

3. Show that propositional equivalence is an equivalence relation on the set of all compound propositions.

4. Give a description of each of the congruence classes modulo 6.

5. Which of the following collections of subsets are partitions of {1, 2, 3, 4, 5, 6}  ?

1. {1, 2, 3}, {3, 4}, {4, 5, 6}
2. {1, 2, 6}, {3, 5}, {4}
3. {2, 4, 6}, {1, 5}
4. {1, 4, 5}, {2, 3, 6}

6. Consider the equivalence relation on the set of integers R = { (x, y) | x - y is an integer }.

1. What is the equivalence class of 1 for this equivalence relation?
2. What is the equivalence class of 0.3 for this equivalence relation?