Showing equivalence relation.

Question

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

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

My book does not even explain how to do this kind of problems. I understand that we need to show that it's symmetric, reflexive, and transitive. However, I usually do it with a matrix. How can I put the above problem into matrix form and then draw diagrams from it?

Answer 1

addendum:

This answer is only useful if $\mathbb Z$ (and subtraction) is allready at your disposal. It seems however that you are busy here with constructing $\mathbb Z$. If that is the case then have a look at the direct proof.

---

Note that $(m,n)\sim(k,l)\iff f(m,n)=f(k,l)$ where $f:\mathbb N\times\mathbb N\rightarrow\mathbb Z$ is defined by $f(m,n)=m-n$. That makes it easy to prove that it is an equivalence relation:

1) $f(m,n)=f(m,n)$ reflexive

2) $f(m,n)=f(m',n')\Rightarrow f(m,n)=f(m',n')$ symmetric

3) $f(m,n)=f(m',n')\wedge f(m',n')=f(m'',n'')\Rightarrow f(m,n)=f(m'',n'')$ transitive

In general if $f:X\rightarrow Y$ is a function then $\sim$ defined by $x\sim x'\iff f(x)=f(x')$ is always an equivalence relation on $X$.

Two (trivial) equivalence relations on any set $X$ are $\{(x,x)\mid x\in X\}$ and $X\times X$.

---

addendum

Here a direct proof

For convenience I start with $(m,n)\sim(k,l)\iff m+l=k+n$ (instead of $n+k$). Then:

$$m+n=m+n$$ for each pair $(m,n)$ is exactly the statement that $\sim$ is reflexive.

$$m+n=k+l\Rightarrow k+l=m+n$$ deals with symmetry.

$$m+n=k+n\wedge k+q=p+l\Rightarrow m+l+k+q=p+l+k+n\Rightarrow m+q=p+n$$ deals with transitivity.

Answer 2

(a)R in N will be reflexive iff (m,n) R (m,n).
Now, m+n=n+m$\implies$(m,n) R (m,n)$\implies$R is reflexive

(b)R in N will be symmetric if (m,n) R (l,k)$\implies$ (l,k) R (m,n). Now, m+k=n+l$\implies$l+n=k+m$\implies$ (m,n) R (l,k)$\implies$ (l,k) R (m,n)$\implies$R is symmetric.

(c)R in N will be transitive if (m,n) R (l,k) and (l,k) R (p,q)$\implies$(m,n) R (p,q). Now,
(m,n) R (l,k) and (l,k) R (p,q) $\implies$ m+k=n+l and l+q=k+p$\implies$k=n+l-m and k=l+q-p
$\implies$n+l-m=l+q-p$\implies$n-m=q-p$\implies$n+p=q+m$\implies$m+q=n+p$\implies$(m,n) R (p,q). Thus, R is transitive.