Question

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

Answer 1

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

b) R1∩R2 is an equivalence relation.

c) R1⊕R2 is not an equivalence relation.

Explanation:

Answer 2

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

b) R1∩R2 is an equivalence relation.

c) R1⊕R2 is not an equivalence relation.

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.