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
    $\begingroup$ Use $\in$ for $\in$. $\endgroup$ – Shaun Jun 3 '18 at 11:43
5
$\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$
  • $\begingroup$ (+1) Great answer! $\endgroup$ – José Carlos Santos Jun 3 '18 at 11:48
  • $\begingroup$ Thank you @JoséCarlosSantos $\endgroup$ – Gibbs Jun 3 '18 at 11:49

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.