Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $A = \mathbb{N} \times \mathbb{N} $, and let $R$ be an equivalence relation on $A$ such that:

$$R = \left\{\big((m,n),(h,k)\big) \in A \times A \mid m + k = n + h\right\}.$$

Prove that each equivalence class of $R$ contains exactly one element $(m,n)$ such that at least one of $m$ or $n$ is $0$.

share|cite|improve this question
This exercise is extremely straightforward. What have you tried? – wj32 Nov 7 '12 at 3:26
I'm afraid it isn't so straightforward for me... I'm very new to these ideas of equivalence classes, and all I've managed to do so far is prove that $R$ is an equivalence relation. Is there some sort of method for determining this? I would like steps rather than an answer, so I can do similar questions on my own. – Stan Harvey Nov 7 '12 at 3:48
Consider an equivalence class that contains $(3, 4)$. What would be another element in this same equivalence class of the form $(m, n)$ where either $m$ or $n$ is $0$? – Benjamin Dickman Nov 7 '12 at 4:39

HINTS: For $d\in\Bbb Z$ let $C_d=\{\langle m,n\rangle\in A:m-n=d\}$.

  • Show that each $C_d$ is an equivalence class of $R$, and each equivalence class of $R$ is one of the sets $C_d$.

To show that each $C_d$ contains exactly one element $\langle m,n\rangle$ such that at least one of $m$ and $n$ is $0$, you must do two things:

  1. prove that each $C_d$ contains at least one such element, and
  2. prove each $C_d$ contains at most one such element.

You can do (1) by simply exhibiting an specific element of $C_d$ that has at least one $0$ component: there is one that has a very simple description in terms of $d$. You can do (2) by assuming that $\langle m,n\rangle$ and $\langle h,k\rangle$ are such elements and using the fact that they are both in $C_d$ to show that they must in fact be equal.

share|cite|improve this answer
Thanks for the hints! This is a late reply, but only because I left this problem for the night and am getting back to it now. One question: I have never seen the terminology $C_d$ before. Is it the same as $[A]$, or am I completely off? I'm not entirely sure how $\{(m,n) \in A : m-n = d\}$ works, either. For instance, using the example in the comment at the top of the page where the equivalence class contains $(3,4)$. This would give $3 - 4 = -1$, but would a negative number be possible if I'm dealing with $\mathbb{N}$? – Stan Harvey Nov 7 '12 at 18:18
@Stan: $C_d$ is simply a convenient name for the set that I’m defining there. It turns out that (for instance) $C_{-1}=[\langle 3,4\rangle]=[\langle 5,6\rangle]=\dots~$, but at that point I’m simply defining a set of ordered pairs; the fact that the set is actually an equivalence class of $R$ remains to be proved. No, there’s no problem with the negative indices: they are simply labels for the sets $C_d$. There is no implication that negative integers can appear in the ordered pairs that are elements of $C_d$. – Brian M. Scott Nov 7 '12 at 18:23
Thanks for the clarification! I think I grasp it now. Just one more thing. What do you mean when you say the one element has a very simple description in terms of $d$? I get that either $m$ or $n$ must be 0, but how can that be expressed in terms of $d$? – Stan Harvey Nov 7 '12 at 18:52
@Stan: Suppose that $d\ge 0$; then $\langle d,0\rangle\in C_d$ and has a $0$ component. Can you use a similar idea to find a specific member of $C_d$ with a zero component when $d$ is negative? – Brian M. Scott Nov 7 '12 at 19:05

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.