I'm studying for my final exam of discrete mathematics, is an exercise in particular concerning equivalence relations do not know how to start:

$$ \text{Let } A = \left\{{3, 5, 6, 8, 9, 11, 13}\right\}\text{ and } R \subseteq A\times A: xRy\Longleftrightarrow{ x \equiv y}$$

How I can prove the symmetry, reflexivity and transitivity?

  • $(1)$ symmetry ($xRx$ for any $x$),

  • $(2)$ reflexivity ($xRy$ implies $yRx$), and

  • $(3)$ transitivity ($xRy$ and $yRz$ implies $xRz$)

I know clearly that the properties must be satisfied by other exercises I've done, but this one in specific, I do not know how to prove mathematically

  • $\begingroup$ what is the $x$ triple-bar $y$? $\endgroup$ – ncmathsadist Jun 7 '12 at 1:07
  • $\begingroup$ @ncmathsadist exactly equal or equivalent $\endgroup$ – franvergara66 Jun 7 '12 at 1:09
  • 1
    $\begingroup$ These then follow because equality is an equivalence relation on any set. $\endgroup$ – ncmathsadist Jun 7 '12 at 1:15
  • $\begingroup$ Use \LaTeX to post, not an image. You have problems here and I can't edit the image. $\endgroup$ – ncmathsadist Jun 7 '12 at 1:16
  • $\begingroup$ What's A2? From your question, I presume it's the cartesian product of A with itself, so what's A? $\endgroup$ – Rick Decker Jun 7 '12 at 1:17

This should follow from the fact that equality is an equivalence relation under any set.

$x=x$, for all $x$

$x=y \to y=x$, for all $x$ and $y$

if $x=y$ and $y=z$, then $x=z$, for any $x$, $y$, and $z$

  • $\begingroup$ Sure, those are the properties of an equivalence relation, but how I prove it? $\endgroup$ – franvergara66 Jun 7 '12 at 1:46
  • 1
    $\begingroup$ If you prove that it satisfies these three properties, then you prove it's an equivalence relation. Proving that these are true for equality will depend on whether you are taking equality as a defined relation or if it is a primitive. $\endgroup$ – A.S Jun 7 '12 at 2:25

Now that we have the clarification from my comment below, your proof should be straightforward. Equality on any set is an equivalence relation.

  • $\begingroup$ Yes, That's Right $\endgroup$ – franvergara66 Jun 7 '12 at 1:36
  • 4
    $\begingroup$ This should be a comment, or CW. $\endgroup$ – Pedro Tamaroff Jun 7 '12 at 1:37
  • 2
    $\begingroup$ So the answer should be (1) Reflexive: any a in A is equal to itself, (2) Symmetric: If a and b are in A and a R b, Then a = b so b = a so b R a. I'll leave it up to you to show transitivity. $\endgroup$ – Rick Decker Jun 7 '12 at 1:42
  • 4
    $\begingroup$ This post has been flagged by a user as "not an answer." Would you care to expand, sadist? $\endgroup$ – anon Jun 7 '12 at 3:27
  • $\begingroup$ I think he is saying $A=\{3,5,6,8,9,11,13\}$ and $R=\{(x,y)\in A^2|x=y\}$. $\endgroup$ – ncmathsadist Jun 7 '12 at 12:20

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.