I have to prove this equivalence relation. I think I have down reflexivity and symmetry. But I am stuck on transitivity. Any kind of help would be helpful.
Define a relation ~ on $ \Bbb{N}$ x $\Bbb{N}$ as follows. For any $(a,b)$ and $(c,d)$ in $\Bbb{N}$, $(a,b)$ ~ $(c,d)$ if and only if $a + d = b + c.$
Prove that ~ is an equivalence relation on $\Bbb{N}$ x $\Bbb{N}$
- You may not refer to, or use subtraction in any manner. You may on the other hand, assume that you have already proved the following. For any natural numbers $m$, $n$, and $k$, if $m+k=n+k$, then $m=n$
Reflexivity
We have to show that $(a,b)$ ~ $(a,b)$
Let $(a,b)$ be arbitrary elements of $\Bbb{N}$ x $\Bbb{N}$
We have $a+b=b+a$
Since $a$ and $b$ are natural numbers, addition is commutative over natural numbers.
So, $a+b=b+a$ is true as desired.
Therefore, the relation is reflexive
Symmetry
We have to show that IF $(a,b)$ ~ $(c, d)$ THEN $(c,d)$ ~ $(a,b)$.
Let $(a,b)$ and $(c,d)$ be arbitrary elements of $\Bbb{N}$ x $\Bbb{N}$
Assume that $(a,b)$ ~ $(c, d)$.
We have $a+d=b+c.$
Since addition is commutative over natural numbers. We can write the expression as $c+b=d+a$.
Which is equivalent to $(c,d)$ ~ $(a,b)$.
Therefore, the relation is symmetric.
Transitivity
We will have to show that IF $(a,b)$ ~ $(c,d)$ and $(c,d)$ ~ $(e,f)$ THEN $(a,b)$ ~ $(e,f)$.
Let $(a,b)$, $(c,d)$ and $(e,f)$ be arbitrary elements of $\Bbb{N}$ x $\Bbb{N}$
Asume that $(a,b)$ ~ $(c,d)$ and $(c,d)$ ~ $(e,f)$.
We have $(a+d)+(c+f)=(b+c)+(d+e)$
STUCK HERE
This comment from the problem statement is key:
Take what you have so far: $(a+d)+(c+f)=(b+c)+(d+e)$.
By associativity and commutativity of addition, you can write this as: $a+f+c+d=b+e+c+d$. Then, the comment from the problem essentially says, "You are allowed to cancel the "$+d$" from both sides, leaving: $a+f+c=b+e+c$.
Then, that comment again allows you to cancel the "$+c$" from both sides, leaving: $a+f=b+e$.
This is what you wanted to show, allowing you to conclude $(a,b)\sim(e,f)$.