I will display the exact problem, then my questions. I have searched to the extremes to figure this out and can't:
Show that the given relation $R$ is an equivalence relation on set $S$.
$S$ is the set of ordered pairs of positive integers.
Define $R$ so that $(x_1,x_2)R(y_1, y_2)$ means that $x_1 + y_2 = y_1 + x_2$.
Edit:
- Reflexive: If $(x_1, x_2)R(y_1, y_2)$ means $x_1 + y_2 = y_1 + x_2$ then $(x_1, x_2)R(x_1, x_2)$. Such that $x_1 + x_2 = x_1 + x_2$. This is true $\forall$ $\in$ $S$, therefore it is reflexive.
- Symmetric: If $(x_1, x_2)R(y_1, y_2)$ means $x_1 + y_2 = y_1 + x_2$ then $(y_1, y_2)R(x_1, x_2)$ means $y_1 +x_2 = x_1 + y_2$. $y_1 +x_2 = x_1 + y_2$ is the equivalent as $x_1 + y_2 = y_1 + x_2$ when $\forall$ $\in$ $S$. Therefore it is symmetric.
- Transitive: *If $(x_1, x_2)R(y_1, y_2)$ means $x_1 + y_2 = y_1 + x_2$, suppose $α=(x_1,x_2)$ and $β=(y_1,y_2)$. Since it is reflexive and symmetric, $α R β$ $β R α$ and $α R α$ are all true. Since transitive is $x R y$, $y R z$, and $z R x$ we can say that it is transitive because $α R β$ $β R α$ and $α R α$ are all true.
$\infty$ number of equivalence classes of $R$
Are all my reasons here valid and correct?
Thank you!
Best Answer
You have correctly wrote a proof of the first two properties, reflexivity and symmetry. For transitivity, you did not quite write things as you should. Don't be afraid to explicitly write the elements of $S$! I wrote a short proof below so you can see what I mean:
Denote $\mathbb{N}$ the set of positive integers. Like @Anurag A mentioned here, for ordered pairs $(x_1,x_2), (y_1,y_2) \in \mathbb{N} \times \mathbb{N} $, the definition of $(x_1,x_2)R(y_1,y_2)$ can be restated as
$$x_1 - x_2 = y_1 - y_2.$$
With this in mind, let's prove:
Reflexivity: for all $(x_1,x_2) \in \mathbb{N} \times \mathbb{N} $, of course we have that $x_1 - x_2 = x_1 - x_2$;
Symmetry: for all $(x_1,x_2), (y_1,y_2) \in \mathbb{N} \times \mathbb{N} $, if $x_1 - x_2 = y_1 - y_2$, then exchanging the left side with the right one (this is just the symmetry of the "$=$" relation), we check that $y_1 - y_2 = x_1 - x_2$;
Transitivity: for all $(x_1,x_2), (y_1,y_2),(z_1,z_2) \in \mathbb{N} \times \mathbb{N} $, if $x_1 - x_2 = y_1 - y_2$ and $y_1 - y_2 = z_1 - z_2$, then just equal both equations and we get
$$x_1 - x_2 = z_1 - z_2,$$ so $(x_1, x_2) R (z_1,z_2)$.
For the number of equivalence classes, as Anurag A said, two pairs in $\mathbb{N} \times \mathbb{N}$ are equivalent if the difference of their first and second coordinates is the same. So you have an equivalence class for each possible difference: $\ldots, -2,-1,0,1,2, \ldots$, that is, for every integer. The cardinality of the set of equivalence classes is the same as $\mathbb{Z}$.
Finally, as a piece of advice, I understand that it is helpful for you to write the definitions of things you want to prove and then proceed to prove them (often, ending up writing the exact same thing twice). I recommend you do this on your notes of course, but when showing your work to other people (like here or to your teacher), you can be more clear if you just write directly what you are going to prove. The reader should know what the defintions involved are, anyway.