0
$\begingroup$

On the set $\mathbb{N} \times \mathbb{N}$ define $(m, n) \sim (k, l)$ if $m + l = n + k$.

Show that $\sim$ is an equivalence relation on $\mathbb{N} \times \mathbb{N}$. Draw a sketch of $\mathbb{N} \times \mathbb{N}$ that shows several equivalence classes.

This is my first time seeing an equivalence relation with 4 different variables. I've normally dealt with two variables, such as $m \sim n$ in case $m - n$ is odd. Could someone please explain how to go about this? Thank you!

Would it be a set of numbers such as {(m,n,k,l), (m,n,k,l)...} or possibly {(m,n),(k,l); (m,n),(k,l);...}?

$\endgroup$
  • $\begingroup$ The equivalence relation partitions $\mathbb{N}^2$, so the elements of the equivalence classes (or blocks of the partition) should indeed be pairs, not 4-tuples. $\endgroup$ – jII Oct 5 '14 at 1:40
  • $\begingroup$ Think of $(a,b)$ as $a-b$. Indeed your equivalence classes are precisely the fibers of $(a,b)\mapsto a-b$. $\endgroup$ – whacka Oct 5 '14 at 1:43
  • $\begingroup$ See also: math.stackexchange.com/questions/884410/… $\endgroup$ – Martin Sleziak Jun 3 '15 at 11:35
  • $\begingroup$ This is the usual way of defining $\mathbb Z$ in terms of $\mathbb N$. ($\mathbb Z$ is the set of equivalence classes under this equivalence relation.) $\endgroup$ – TonyK Jun 3 '15 at 12:02
0
$\begingroup$

The relation is still defined in terms of two objects being equivalent, it's just that this time the two objects are themselves pairs of numbers. For example $(1,1)$ is equivalent to $(2,2)$ because $1+2=1+2$. $(1,2)$ is not equivalent to $(2,1)$ because $1+1\neq2+2$

If you need more help, here's a proof of transitivity to get you started. Suppose $(a,b)\sim(c,d)$, and $(c,d)\sim(e,f)$ then $a+d=b+c$ and $c+f=d+e$, and consequently $$a+d+c+f=b+c+d+e\text{.}$$ Subtracting $c+d$ from both sides we find $a+f=b+e$ which is to say $(a,b)\sim(e,f)$.

$\endgroup$
  • $\begingroup$ Thank you! Does this mean to show reflexivity, I need to show that (m, n) ~ (m, n)? Also, to show symmetry, do i prove that (m, n) ~ (n, m) or do I show that (m, n) ~ (k, l) => (k, l) ~ (m, n)? $\endgroup$ – mylasthope Oct 5 '14 at 19:51
  • $\begingroup$ I did (m, n) ~ (k, l) implies (k, l) ~ (m, n). Hope that is correct. Trying to figure out how to sketch the equivalence classes now. Once again, thank you for your help. $\endgroup$ – mylasthope Oct 5 '14 at 20:01
  • $\begingroup$ You did the right one. For sketching, think about how you'd show the set on which you've defined your equivalence relation. $\endgroup$ – Trold Oct 6 '14 at 0:57
0
$\begingroup$

First, show that $\sim$ is reflexive, ie that $(m, n) \sim (k, l)$ whenever $m = k$ and $n = l$. Then, show that $\sim$ is symmetric, i.e. $(a, b) \sim (b, a)$ for all $a, b \in \mathbb{N}^2$. Lastly, show that $\sim$ is transitive so that $(a, b) \sim (c, d), (c, d) \sim (e, f) \Rightarrow (a, b) \sim (e, f)$. All of the above is relatively easy to work, out and I will leave it to you.

$\endgroup$

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.