**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)*.

- Show that
*R*is an equivalence relation on*A*. - 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, 2, 3}, {3, 4}, {4, 5, 6}
- {1, 2, 6}, {3, 5}, {4}
- {2, 4, 6}, {1, 5}
- {1, 4, 5}, {2, 3, 6}

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

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