0
$\begingroup$

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

  • 0
    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$?2012-11-07

1 Answers 1

1

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.

  • 1
    @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?2012-11-07