Let A = {1,2,3,4,5,6,7,8,9,10,11,12} and let R be the relation on set A defined by for any elements m and n in A, m R n iff m is congruent to n (mod 5).

1/ Why is R an equivalence relation?

2/ Find the equivalence classes determined by R.

My Attempt: 1/ Find prove that R is equivalence relation. R has to satisfy 3 condition: reflexive, symmetric, and transitive.

a. Reflexive: Suppose m is in the set A. It is true to say that m is congruent to itself modulo 5. Thus by definition of R, mRm

b. Symmetric: Suppose m,n are in set A. Since mRn, m is congruent to n(mod5) But this implied that n is congruent to m(mod5). Thus, nRm.

c. Transitive: Suppose m,n and r in set A. we have mRn and nRr. Since mRn, m is congruent to n(mod5). Also, nRr which mean that n is congruent to r(mod5) as well. Thus, we have m is congruent to r(mod5)>>>by def of R, mRr >>> R is equivalence relation.

2/ We have [a]={x in A | xRa}

So [{1}]={{1},{1,6}, {1,11}}


and [{3}], [{4}]... so on

Regarding number 2, this look like an order pairs to me so Im not sure if this is right. Can anybody please take a look and let me know any error.

Thank You.

  • 1
    $\begingroup$ The equivalence class $[1]$ is written $\{1, 6, 11\}$ (and so on). But otherwise this seems correct. $\endgroup$ – Arthur May 21 '14 at 7:38
  • $\begingroup$ Thank You. What do you think of the first one ? The proof. $\endgroup$ – user3651672 May 21 '14 at 7:39
  • $\begingroup$ It's correct, but depending on how strict it's supposed to be, it could've been fleshed out a bit more. You correctly interpret $xRy$ as $x\equiv y \pmod 5$ all the time, but once you've done that, the rest of your argument is handwaving. Like transitivity, where you say that $x\equiv y \pmod 5$ and $y \equiv z \pmod 5$ implies $x \equiv z \pmod 5$. Well, why is that? Why is congruence $\pmod 5$ a transitive relation? In the end it's up to you and your professors how much details a proof should have. $\endgroup$ – Arthur May 21 '14 at 8:39

Your Answer

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

Browse other questions tagged or ask your own question.