1
$\begingroup$

Let $A = \{1, 2, 3,...,9\}$ and let $\sim$ be the relation on $A\times A$ defined by $(a,b) \sim(c,d)$ if $a+d = b+c$.

Prove that $\sim$ is an equivalence relation.

Really stuck on this question, maybe its the use of ~ that is throwing me off. Any suggestions on how to do this? Maybe I could swith ~ out for something else while solving then put it back in.

Thanks

$\endgroup$
  • 1
    $\begingroup$ You have to show ~ is reflexive, symmetric, and transitive. Note $a+d=b+c \iff a-b=c-d$ $\endgroup$ – J. W. Tanner Apr 10 '19 at 21:20
  • $\begingroup$ (1) If the symbol ~ annoys you, simply replace it by the more ordinary symbol R. (2) If you are stuck, it may come from the fact that, in this problem, the "elements" you are deling with are, in fact, ordered pairs. So for example, proving reflexivity amounts to proving that any ordred pair (a,b) has the relation R ( or ~ ) with itself , that is (a,b) R (a,b). Using the defining formula, you could see what you have to prove, and then prove if using basic arithmetic. $\endgroup$ – Saint James Apr 10 '19 at 21:25
  • $\begingroup$ The symbol "~" is often used to denote a relation in case this relation is an equivalence relation. But, before having proved that it is actually an equivalence relation in this case, you are not allowed to read it as " is equivalent to". So, accordind to me, the best thing do do is to replace it by the ordinary symbol R, while you are doing your proof. $\endgroup$ – Saint James Apr 10 '19 at 21:35
1
$\begingroup$

Clearly, the statement $a+d=b+c$ is just saying that $a-b=c-d$, i.e. two ordered pairs are similar if the difference of their terms is equal. To show it's an equivalence relation, we need reflexivity, transitivity and symmetry. The first and last are obvious.

For transitivity, we need to show $x\sim y$ and $y\sim z$ implies $x\sim z$. Let $x=(x_1,x_2),y=(y_1,y_2),z=(z_1,z_2)$. The conditions tell you that $x_1-x_2=y_1-y_2$, but also that $y_1-y_2=z_1-z_2$. Clearly then, $x_1-x_2=z_1-z_2$. But this is exactly what it means for $x\sim z$!

$\endgroup$
1
$\begingroup$

I don't normally do this but I think it may clear some conceptions up. If you want to get to how to effectively solve this skip to the end.

...

Maybe an example first:

If we let $A = (3,6)$ then $A\sim (m,n)$ if $3+ n = 6+m$ so the list of $(m,n)$ where $A \sim (m,n)$ are the ones where $n = 3+m$ so $\{(1,4),(2,5),(3,6),(4,7),(5,8),(6,9)\}$ are all the $(m,n)$ where $A \sim (m,n)$.

We can go a little further.

If $(a,b) \equiv (c,d)$ then $a+d = b+c$ and $a-b = c-d$.

So the "classes" are all the ones related to $(x_1, x_2)$ where $x_1 - x_2 =$:

$-8$: $\{(1,9)\}$

$-7$: $\{(1,8),(2,9)\}$

$-6$: $\{(1,7),(2,8),(3,9)\}$

$-5$: $\{(1,6),(2,7),(3,8),(4,9)\}$

$-4$: $\{(1,5),(2,6),(3,7),(4,8),(5,9)\}$

$-3$: $\{(1,4),(2,5),(3,6),(4,7),(5,8),(6,9)\}$

$-2$: $\{(1,3),(2,4),(3,5),(4,6),(5,7),(6,8),(7,9)\}$

$-1$: $\{(1,2),(2,3),(3,4),(4,5),(5,6),(6,7),(7,8),(8,9)\}$

$0$: $\{(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(7,7),(8,8),(9,9)\}$

$1$: $\{(2,1),(3,2),(4,3),(5,4),(6,5),(7,6),(8,7),(9,8)\}$

$2$: $\{(3,1),(4,2),(5,3),(6,4),(7,5),(8,6),(9,7)\}$

$3$: $\{(4,1),(5,2),(6,3),(7,4),(8,5),(9,6)\}$

$4$: $\{(5,1),(6,2),(7,3),(8,4),(9,5)\}$

$5$: $\{(6,1),(7,2),(8,3),(9,4)\}$

$6$: $\{(7,1),(8,2),(9,3)\}$

$7$: $\{(8,1),(9,2)\}$

$8$: $\{(9,1)\}$

All the pairs in each set are related to each other this is an "equivalence" because every pair is is exactly one class and can be interchanged with others in the class with no ambiguity.

A relationship could not be equivalent if some elemtns are in more than one list. Of some elements aren't in any list. Or if such bunch of lists wouldn't make any sense to make.

==== okay... the real answer====

A relationship is an equivalence if

1) it is reflexive. that is for every pair $(a,b)$ then $(a,b)\sim (a,b)$ or for every $(a,b)$ then $a-b = a-b$. That's always true.

If we view it as $(a,b)\sim (c,d)$ if $a-b = c-d$ then we'd have $a-b = a-b$ which is of course true.

2) it is symmetric. For any pair $(a,b) \sim (c,d)$ then $(c,d)\sim (a,b)$. That is is $a+d = b+c$ then $c+b = d+ a$. That's ... clear.

If we view is as $(a,b)\sim (c,d)$ if $a-b= c-d$ then if $a-b = c-d$ then $c-d = a-b$ so $(a,b)\sim(c,d)\iff (c,d)\sim (a,b)$.

3) it is transitive. That is if $(a,b)\sim (c,d)$ and $(c,d)\sim (e,f)$ then $(a,b) \sim (e,f)$.

So if $a+ d=b+c$ and $c+f = d+ e$ then we have to prove that means $a+f = b+e$.

We can do that via arithmetic $a+d +c+f =b+c + d + e$ so $a+f = b+e$.

$\endgroup$
0
$\begingroup$

Just use the definitions:

For reflexivity, you have to show that for any $(a,b)$, it is true that $(a,b)\sim (a,b)$, i.e. that $a+b=b+a$. Well, $a$ and $b$ are natural numbers, and those are commutative, so yes, this is true.

Symmetry: here you have to show that if $(a,b) \sim (c,d)$, then $(c,d) \sim (a,b)$, which is to say: show that if $a+d=b+c$, then $c+b=d+a$ ... can you show this?

Finally, now that I have shown what you need to prove to demonstrate reflexivity and symmetry, can you figure out what you need to show to demonstrate transitivity?

$\endgroup$

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.