# Proving relation $R$ is a equivalence relation on the given set $S$

There are two examples of this question I'm working on

a) $$S = \mathbb{N} - \{1\}:(x,y) \in R$$ if and only if $$gcd(x,y)>1$$

b)$$S=\mathbb{R};(x,y) \in R$$ if and only if there exists $$n\in \mathbb{Z}$$ such that $$x=2^n y$$

I know to prove an equivalence relation you prove the three properties of a relation hold for $$R$$

1)$$a=a$$ (reflexive property)

2)$$a=b$$ and $$b=a$$ (symmetric property)

3)$$a=b$$ and $$b=c$$ then $$a=c$$ (transitive property)

a)

lets say that $$a=(x,y)$$, then not every $$a \in R$$ for any $$x,y \in S$$, if $$x=2,y=3$$ then $$a=(2,3)$$ but $$gcd(2,3) = 1$$ so $$(2,3) \notin R$$ since $$\gcd(x,y)>1$$ does not hold.

So the relation in (a) is not a equivalence relation

b) I don't know how to go about doing this one at all.

Addressing the relation given in $(a)$:

For every $x \in \mathbb N-\{1\}$, $\gcd(x, x) = x \neq 1 \in \mathbb N - \{1\}$ (because $x\neq 1$).

• Hence reflexivity holds.

Furthermore for any $x, y \in \mathbb N-\{1\},$ if $\gcd (x, y) \neq 1$, then $\gcd (y, x) \neq 1$.

• So the relation is symmetric.

Now, for any $x, y, z \in \mathbb N-\{1\}$, if $\gcd(x, y) \neq 1$, and $\gcd (y, z) \neq 1$, can we guarantee that $\gcd(x, z) \neq 1$? If we can, then $R$ from $(a)$ is also transitive, and is therefore an equivalence relation.

But consider $x = 3, y = 6,$ and $z = 8,\; \in \mathbb N-\{1\}.$ $\gcd(x, y) = \gcd(3, 6) = 3 \neq 1.$ And $\gcd(y, z) = \gcd(6, 8) = 2 \neq 1.$ However, $\gcd (x, z) = \gcd(3, 8) = 1$, hence despite $(x, y) \in R, (y, z)\in R,$ it does not follow that $(x, z) \in R.$

• Hence, transitivity alone fails.

Hence the relation is not an equivalence relation.

The relation given in $(b)$ is reflexive (take $n = 0$, then for any $x\in \mathbb R, \;\;x = 2^0 x$ (here $n = 0\in \mathbb Z$).

It is also symmetric. For any $x$ such that $x = 2^n y$ and such that $n \in \mathbb Z$, we have that $y = 2^{-n} x$, and since $n$ is an integer, so is $-n$.

Your sole task then is to determine whether the relation in (b) is transitive. If it is, the relation is an equivalence relation. If it is not, then the relation is not an equivalence relation.