1
$\begingroup$

How can I show that $S$ is an equivalence relation:

Given a relation $S$ on $\mathbb N$ such that:

$$ (n,m) \in S \text{ if } m^2 \text{ is divisible by } n $$

I know equivalence relations are symmetric, reflexive and transitive. I'm just not sure how to use this knowledge to prove it.

Reflexive:
I believe I need to show that for any $x \in \mathbb N$, $(x\,,\,x) \in S$.

I'm unsure how I prove this for reflexive, symmetric, and transitive.

$\endgroup$
1
  • 1
    $\begingroup$ Use $\in$ for $\in$. $\endgroup$
    – Shaun
    Jun 3, 2018 at 11:43

1 Answer 1

4
$\begingroup$

Reflexivity: $(n,n) \in S$ for each $n$. Ask yourself: is it true that $n^2$ is a multiple of $n$? If yes, you have reflexivity.

Symmetry: if $(n,m) \in S$ then $(m,n) \in S$. Ask yourself: assume that $m^2$ is a multiple of $n$. Is it true that $n^2$ is a multiple of $m$? If yes, you have symmetry.

Transitivity: if $(n,m) \in S$ and $(m,l) \in S$, then $(n,l) \in S$. Ask yourself: if $m^2$ is a multiple of $n$ and $l^2$ is a multiple of $m$, is it true that $l^2$ is a multiple of $n$? If yes, you have transitivity.

$\endgroup$
2
  • $\begingroup$ (+1) Great answer! $\endgroup$ Jun 3, 2018 at 11:48
  • $\begingroup$ Thank you @JoséCarlosSantos $\endgroup$
    – Gibbs
    Jun 3, 2018 at 11:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy