Ex. 4. Suppose that R1 and R2 are equivalence relations on the set S. Determine whether each of these combinations of R1 and R2 must be an equivalence relation. a) R1∪R2 b) R1∩R2 c) R1⊕R2

a) R1∪R2 may not be an equivalence relation.

b) R1∩R2 is an equivalence relation.

c) R1⊕R2 is not an equivalence relation.

Step-by-step explanation:

a)

R1∪R2 may not be an equivalence relation.

Counter-example

S={1,2,3}

R1={ (1,1), (2,2), (3,3), (1,2), (2,1) }

R2={ (1,1), (2,2), (3,3), (1,3), (3,1) }

R1 and R2 are equivalence relations in S. Let us see R1∪R2 is not.

(2,1) ∈ R1∪R2 and (1,3) ∈ R1∪R2. If R1∪R2 were an equivalence relation in S it should be transitive, so (2,3) should belong to R1∪R2. But (2,3) ∉ R1∪R2 and R1∪R2 is not an equivalence relation

b)

R1∩R2 is an equivalence relation.

Let us prove is reflexive:

(a, a) ∈R1 for every a in S, (a, a) ∈R2 for every a in S, so

(a, a) ∈R1∩R2

is symmetric:

If (a, b) ∈R1∩R2 then (a, b) ∈R1 and (a, b) ∈R2. Since R1 and R2 are equivalence relations, (b, a) ∈R1 and (b, a) ∈R2, hence (b, a) ∈R1∩R2

is transitive:

If (a, b) ∈R1∩R2 and (b, c) ∈R1∩R2 then (a, b) ∈R1 and (b, c) ∈R1 and (a, b) ∈R2 and (b, c) ∈R2, so (a, c) ∈R1 and (a, c) ∈R2, hence (a, c) ∈R1∩R2.

c)

R1⊕R2 is not an equivalence relation.

Since R1⊕R2 = (R1∪R2) - (R1∩R2) the intersection of R1 and R2 is not in R1⊕R2, so the diagonal (the elements of the form (a, a) with a∈S) are not in R1⊕R2 hence it is not reflexive.