Answer to Question #245939 in Discrete Mathematics for Mico

Question

Let R₁ and R₂ be equivalence relation on X. Show that R₁ R₂ is an equivalence relation on X.

Answer 1

We suppose thar $R_1R_2\equiv R_1\cap R_2$ because for $R_1\circ R_2$ statement is not valid.

1) reflexivity

Let x be any element in X, then $<x,x>\in R_1,<x,x>\in R_2$

because R₁,R₂ both are reflexive therefore by definition we have that $<x,x>\in R_1\cap R_2=R_1R_2$ . So reflexivity is proved.

2) symmetry

Let $<x,y>\in R_1\cap R_2$ . Then $<x,y>\in R_1$ and $<x,y>\in R_2$

Therefore $<y,x>\in R_1$ and $<y,x>\in R_2$ because both of R₁,R₂ are symmetrc as equivalences. By definition of intersection we have $<y,x>\in R_1\cap R_2$ therefore R₁R₂ is symmetrical

3) transitivity

Let $<x,y>,<y,z>\in R_1\cap R_2$ . Therefore $<x,y>,<y,z>\in R_1$ and $<x,y>,<y,z>\in R_2$ . This this entails $<x,z>\in R_1$ and $<x,z>\in R_2$ because R₁,R₂ are transitive. So $<x,z>\in R_1R_2$ , therefore R₁R₂ is transitive.

In this way three basical properties of equivalence are proved and so R₁R₂ is equivalence.