This is a textbook problem, and I'm trying to understand how it can be proved. I feel like I can come up with a counterexample, but assume I must be wrong somewhere in my understanding.

For sake of counterexample, assume A = {1,2}, R={(1,1)}, S={(2,2)}, then R and S are equivalence relations (as they are both reflexive, symmetric and transitive). However, the intersection of R and S is the empty set. Since an equivalence relation cannot be the empty set, then $R\cap S$ is not an equivalence relation.

So... what is my mistake here?

  • 1
    $\begingroup$ List the axioms for equivalence relations. Then verify them one by one. $\endgroup$ – Jacob Wakem Nov 3 '16 at 5:26
  • $\begingroup$ How can I do that when there are no specifics for the set? Also, why is the example I give not an adequate counterexample? (I'm assuming its not) $\endgroup$ – Alex Butterfield Nov 3 '16 at 7:44
  • $\begingroup$ By logical argument on x (R and S) y implies xRy and xSy implies (some propertry of equivalence relations for R) and (some property of equivalence relations for S) implies (some property of equivalence relations for (R and S) ) . $\endgroup$ – Jacob Wakem Nov 3 '16 at 16:50

$R$ and $S$ are not equivalence relations. $(2,2)\not\in R$ and $(1,1)\not\in S$.

  • $\begingroup$ I'm not sure I agree. (yet) The definition of an equivalence relation doesn't say that they have to be the same set, as you are implying. $\endgroup$ – Alex Butterfield Nov 3 '16 at 6:45
  • $\begingroup$ DEFINITION A relation R on a set A is an equivalence relation on A if R is reflexive on A, symmetric, and transitive. $\endgroup$ – Alex Butterfield Nov 3 '16 at 6:45
  • $\begingroup$ @AlexButterfield They don't have to be the same set. But they do have to be reflexive. Your R and S aren't. $\endgroup$ – user223391 Nov 3 '16 at 18:47
  • $\begingroup$ Thanks guys. I didn't realize that to be reflexive on a set A then all elements from set A must be in the relation in the form (x,x). I thought it was just, if some (x,y) is in R then (x,x) and (y,y) must be in R. $\endgroup$ – Alex Butterfield Nov 8 '16 at 9:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.