0

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);...}?

Martin Sleziak
  • 53,687
mylasthope
  • 241
  • 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. – jII Oct 05 '14 at 01:40
  • Think of $(a,b)$ as $a-b$. Indeed your equivalence classes are precisely the fibers of $(a,b)\mapsto a-b$. – anon Oct 05 '14 at 01:43
  • See also: http://math.stackexchange.com/questions/884410/if-r-is-a-brc-d-iff-ad-bc-show-that-r-is-an-equivalence-relation – Martin Sleziak Jun 03 '15 at 11:35
  • 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.) – TonyK Jun 03 '15 at 12:02

2 Answers2

0

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

Trold
  • 1,133
  • 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)? – mylasthope Oct 05 '14 at 19:51
  • 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. – mylasthope Oct 05 '14 at 20:01
  • You did the right one. For sketching, think about how you'd show the set on which you've defined your equivalence relation. – Trold Oct 06 '14 at 00:57
0

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.

MathMajor
  • 6,478