Mathematics 243 – Algebraic Structures Discussion 2 – Equivalence Relations September 27, 2006

Background

Recall that last time we defined a relation on a set A to be a subset R ⊂ A × A, and we write aRb to mean (a, b) ∈ R. A relation on A is said to be an equivalence relation if it satisfies all three of the following properties:

• R is reflexive: aRa is true for all a ∈ A.

• R is symmetric: For all a, b ∈ R, if aRb is true, then bRa is also true.

• R is transitive: For all a, b, c ∈ A, if aRb and bRc are true, then aRc is also true.

If R is an equivalence relation, then the equivalence class of an element a ∈ A is the set:

[a] = {x ∈ A | aRx}

(in words: [a] is the set of all elements of A that are related to a). Today we want to practice using these ideas on some additional examples and think about how the equivalence classes of an equivalence relation partition the set A.

Discussion Questions

A) Let A = Z be the set of integers. For each of the following relations on Z,

1) What is the set {x ∈ Z | xR1}?

2) Determine which of the three properties of an equivalence relation are satisfied. Prove all your assertions.

i) xRy if and only if x = 4y. ii) xRy if and only if x − y is an integer multiple of 6. iii) xRy if and only if x ≥ y. iv) xRy if and only if |x − y| ≤ 2.

B) Of the four relations in part A, only one satisfies all three properties for equivalence relations. For that one, determine all the distinct equivalence classes, and show that they give a partition of Z.

C) In this problem, you will show that the equivalence classes for an equivalence relation R on the set A form a partition of A.

1) What happens if you take the union of all the equivalence classes [a] for all a ∈ A. What set do you get? Hint: Think about what the reflexive property means!

2) Now, assume that [a] and [b] are any two equivalence classes. Prove that if there is any x ∈ [a] ∩ [b], then in fact [a] = [b].

3) Give the contrapositive form of the implication you proved in part 2. (Recall the contrapositive of “if p then q” is “if not q then not p”. There is nothing to prove for this part because the contrapositive is just a logically equivalent restatement.)

Assignment

Group writeups due Monday, October 2.