Prove that $R$ is reflexive, symmetric, and transitive.

Question

Define a relation $R$ on $\Bbb Z$ by declaring that $xRy$ if and only if $x^2\equiv y^2\pmod{4}$. Prove that $R$ is reflexive, symmetric, and transitive.

Suppose $x\in\Bbb Z$. Then $x^2\equiv x^2\pmod {4}$ means that $4\mid (x^2-x^2)$, so $x^2-x^2=4a$ where $a=0\in\Bbb Z$. Therefore $R$ is reflexive.

Now suppose $x^2\equiv y^2\pmod {4}$. This means $4\mid (x^2-y^2)$ and so $x^2-y^2=4a$, for some $a\in\Bbb Z$. Multiplying by $-1$ we have $-1(x^2-y^2=4a)\\\rightarrow -x^2+y^2=-4a\\\rightarrow y^2-x^2=4(-a)$

so $4\mid(y^2-x^2)$ and $y^2\equiv x^2\pmod{4}$. This shows that $R$ is symmetric.

Now we assume that $x^2\equiv y^2\pmod{4}$ and $y^2\equiv z^2\pmod{4}$. This means $4\mid(x^2-y^2)$ and $4\mid(y^2-z^2)$. Then we have $x^2-y^2=4a$ and $y^2-z^2=4b$ for some $a,b\in\Bbb Z$. Rearranging we get $x^2=4a+y^2$ and $z^2=y^2-4b$.

Then

$\begin{align*}x^2-z^2&=(4a+y^2)-(y^2-4b)\\&=4a+4b\\&=4(a+b)\end{align*}$

This shows that $4\mid(x^2-z^2)$ and $x^2\equiv z^2\pmod{4}$, therefore $R$ is transitive. $\blacksquare$

Please forgive my rushed formatting, just wondering if my arguments here work and if this is a valid proof. Any feedback is appreciated, thanks!

Answer 1

I agree with J. W. Tanner's question comment that what you've done looks all right.

I have just one small suggestion. With your $x^2−y^2=4a$ and $y^2−z^2=4b$ equations, you don't need to do any rearranging. Instead, you can just add these $2$ equations, as the $y^2$ terms cancel, to more directly get your result of $x^2−z^2=4a+4b=4(a+b)$. This will make your proof a bit shorter & more succinct.

Answer 2

This is straight forward and I think you did ok. The transitivity follows immediately from transitivity of congruence. In fact all three follow from the fact that congruence mod $n$ is indeed an equivalence relation.

Answer 3

Your solution is ok. I’d just like to point out that your problem is in fact just a specific case of a much more general phenomenon:

Let $A$, $B$ be sets, $f:A\to B$ a function, and $R\subseteq B\times B$ an equivalence relation. Define a relation $S\subseteq A\times A$ such that $$(x,y)\in S\Leftrightarrow (f(x),f(y))\in R.$$ Then, $S$ is also an equivalence relation.

This is straightforward to prove:

• $S$ is reflexive since $f(x)Rf(x)$ implies $xSx$.
• $S$ is symmetric since, if $xSy$, then $f(x)Rf(y)$, $f(y)Rf(x)$, and $ySx$.
• $S$ is transitive since, if $xSy$ and $ySz$, then $f(x)Rf(y)$ and $f(y)Rf(z)$, so that $f(x)Rf(z)$ and $xSz$.

Your result is now immediate: take $A=B=\mathbb Z$, $R$ to be equivalence $\text{mod }4$, and $f(x)=x^2$ to be the squaring function.