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)

but I'm simply really bad at going about this. My attempt so far is the following.


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.


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.