# How to prove the relation is transitive?

Problem:
Consider the relation R on $N$ defined by
$x$R$y$ iff $2$ divides $x + y$.
Prove that R is an equivalent relation

My work:
I know that to prove that a relation is an equivalent relation, I have to show that it's reflexive, symmetric and transitive.
So first reflexive. Suppose there is an integer $a$ in $N$. Then $a + a = 2a$.
$2$ divides $2a$ because $2a = (2)(a)$. Therefore this relation is reflexive because $(a,a)$ will be in the relation.
For symmetric - Suppose there is an ordered pair $(a, b)$ for which $a$ and $b$ are both in $N$. If
$2 \mid (a + b)$ then $2$ will also divide $b + a$ because of the commutative law of addition
Commutative Law. Therefore the ordered pair $(b, a)$ will also be in the relation and the relation will therefore be symmetric
For transitive, Suppose $(a, b)$ and $(b, c)$ are in the relation. Now I have to show that $(a, c)$ will also be in the relation.
$a + b = 2k$ for some integer $k$, solving for $b$, we have
$b = 2k - a$.
$b + c = 2m$ for some integer $m$. Substituting for $b$, we have
$2k - a + c = 2m$
$c - a = 2(k + m)$
Algebraically I have shown the $2$ divides $c - a$. Is there some algebra step or trick I can use to show that $2$ will also divide $c + a$?

• Note that $c+a=(c-a)+2a$. Mar 7, 2015 at 0:41
• @AMPerrine Damn that's clever. So you add 2a to both sides and you have 2(k + m + a) on the other? Mar 7, 2015 at 0:54

Start with the relationships, where $$a,b,c,k,j \in \mathbb{Z}$$: $$a R b, bRc \rightarrow 2|(a+b), 2|(b+c)$$ $$(a+b) = 2k, (b+c) = 2j$$ $$a+2b+c = 2(k+j)$$ $$a+c = 2(k+j)-2b$$ $$a+c = 2(k+j-b)$$

And thus $$2$$ divides $$(a+c)$$. Therefore, if $$aRb,bRc$$, then $$aRc$$, satisfying the definition of transitivity.

• is it possible to do it with the substitution strategy I was using? Mar 7, 2015 at 0:41
• Sort of. Go from$2k-a+c = 2m$ to $2k+c = 2m +a$. Then take both sides mod 2; $2k+c\textrm{ mod }2 = 2m + a\textrm{ mod }2$. Cancel the even numbers: $a\textrm{ mod }2=c\textrm{ mod }2$. If they have the same parity, then their sum has an even parity.
– user208649
Mar 7, 2015 at 0:43

The sum of two numbers is even iff the numbers are the same parity, so $xRy$ is equivalent to "$x$ and $y$ have the same parity". Now transitivity is obvious.

• You wouldn't have to do any proofs then would you? Mar 7, 2015 at 0:59
• @committedandroider You would probably want to prove that the sum of two numbers is even iff the numbers are the same parity (which would end up being as long as proving transitivity directly), but it has the advantage of making it clearer why the relation is transitive. Mar 7, 2015 at 1:02