# Proof that an equivalence class contains an element

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

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

-
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