Prove or disprove this is an equivalence relation

Question

Let $R$ be a relation defined on the set $\Bbb N$ by $a R b$ if either $a|2b$ or $b|2a$. Prove or disprove: $R$ is an equivalence relation.

I able to prove reflexive and symmetric. I understand that this is not an equivalence relation I was just unsure how to prove that it is not transitive.

What have you done so far on this problem? Where are you stuck? — Théophile, Nov 15 '15 at 22:12

score 1 · Answer 1 · answered Nov 17 '15 at 00:11

If the definition of $\mathbb{N}$ includes the number $0$ then the relation may not even be reflexive - whether $0 \mid 0$ depends on the definition of $x|y$, i.e. $\exists k\in\mathbb{Z} \text{ such that }y=kx$, with or without the additional proviso that $k\ne0$.

In any case, the relation is not transitive so is not an equivalence relation. A counterexample shows this: $\lnot (a\sim b \land b\sim c \implies a\sim c)$ for $a=3,b=1,c=5$, i.e. $3\sim1$ and $1\sim5$ but it is not the case that $3\sim5$.

score 0 · Answer 2 · answered Nov 15 '15 at 22:12

0

To prove a equivalence relation we must prove 3 things. A) a~a B) if a~b then b~a C) if a~b and b~c then a~c.

C) Assume for a contradiction that a~c. Let a=1, b=2, and c=4. We can see by our definition that a~b and b~c. However we can see our contradiction that neither 2a=c nor a=2c so a~c is false drawing our contradiction.

Because R has failed one piece of the definition of a equivalence relation it is not a equivalence relation.

answered Nov 15 '15 at 22:12

Chris

472

The definition of $R$ does not require that $2a=c$ or $a=2c$. – Théophile Nov 15 '15 at 22:16
It does if a~c. – Chris Nov 15 '15 at 22:17
Could you explain how? – Théophile Nov 16 '15 at 01:20
a=1 and c=4 implies that a=1|8=2c hence aRc. – Did Nov 16 '15 at 21:08
To be clear, the notation $a|2b$ means "$a$ is a factor of $2b$", not "$a$ is equal to $2b$". – Théophile Nov 17 '15 at 01:15

Prove or disprove this is an equivalence relation

2 Answers2