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$.


  • 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!


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.

  • $\begingroup$ Unfortunately this is what the teacher expects us to write for proving anything in this course. I, personally, agree it is tedious. Thank you for the assistance. I will make adjustments to my post shortly! $\endgroup$ – c r Feb 15 '16 at 1:07

The objects that are being related are ordered pairs. So given an object $\alpha=(x_1,x_2)$ and an object $\beta=(y_1,y_2)$, you have that $\alpha \, R \, \beta$ by the condition $x_1-x_2=y_1-y_2$ (the difference of the coordinates in the two pairs are the same. For example, $(1,3) \, R \, (2,4)$ because in both cases the difference of coordinates is $-2$. Likewise $(1,1) \, R \, (2,2)$ because the difference is $0$.

For reflexivity, you need to check if every object is related to itself, i.e. is $\alpha \, R \, \alpha$ for every $\alpha \in S$? So you are asking if $$(x,y) \, R \, (x,y) \, \quad \forall \, (x,y) \in S?$$

  • $\begingroup$ For reflexive, is that simply stating: if x1 is a positive integer, then ∀ (x1,x2)∈S, (x1,x2)=(x1,x2) because from how I understand it... x1, x2, y1, y2 can be the set of all positive integers all the way to infinity? $\endgroup$ – c r Feb 14 '16 at 22:31

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.