# Is this relation an equivalence?

I'm completely lost in discrete mathematics. I have to find out whether $$xRy \iff \exists z\in \mathbb N \;\;[z\mid y \iff z\mid x]$$ where $x,y \in \mathbb N$ is an equivalence.

I know that relation must be reflexive, symmetric and transitive in order to be an equivalence.

If relation is reflexive, then $z\mid x \iff z\mid x$ must be the same, which is true. But I have no idea how to prove symmetry and transitivity of relation. Thanks for your advice

• Should it be:$$xRy\iff\{ \forall z\in \mathbb{N}, z|x\iff z|y\}\quad ?$$ – b00n heT Oct 11 '16 at 18:53
• What exactly is meant by $z\in N:z|y$ & $z|x$? Here $z$ is free and this is not a well defined relation in $x$ and $y$. – drhab Oct 11 '16 at 18:53
• Edited, I'm sorry for bad representation. – Speedding Oct 11 '16 at 18:54
• An equivalence relation on a set $A$ is a subset of $A\times A$ that has certain properties. What set $A$ are you dealing with? Also what is $N$ in your question? – drhab Oct 11 '16 at 19:05
• Instead of saying "$z|x$ & $z|x$ must be the same", it's better to say "$z|x \iff z|x$" which is easier to understand. – Kevin Long Oct 11 '16 at 19:07

## 2 Answers

Let $x,y\in\mathbb Z$ and observe that $z:=\max(x,y)+1$ will not divide $x$ and will not divide $y$.

That means that the statement: $$z\mid x\iff z\mid y$$ is actually a true statement.

Proved is now that for every pair $\langle x,y\rangle\in\mathbb N^2$ we have $xRy$ (or equivalently $R=\mathbb N^2$).

Reflexivity, symmetry and transitivity are evident for this relation.

• Thanks. If I'm talking about equivalence classes, then for z = 1 there will be only 1 equivalence class (because 1 will divide $\allin z \in Z$) and for z > 1 there will be 2 equivalence classes (the number is dividable by z / is not dividable by z), am I right? – Speedding Oct 12 '16 at 17:33
• I meant $\forall z \in Z$ – Speedding Oct 12 '16 at 17:35
• My answer deals with relation $\exists z\in\mathbb N[z|x\iff z|y]$ (the one stated in your question). In your comment you seem to ask questions about other relation(s): $z|x\iff z|y$ where $z$ is a fixed element of $\mathbb N$. Denoting such a relation by $R_z$ it can be observed that $R_z$ is an equivalence relation for every $z\in\mathbb N$. Secondly that $R_1$ has one equivalence class, and for $z\neq1$ the relation $R_z$ has indeed $2$ equivalence classes as you remark. Note that there is an essential difference between $R$ in your question and the relations $R_z$ mentioned here. – drhab Oct 13 '16 at 7:25

In plain english. "Two natural numbers are related if they have a factor in common" (which ... as $z$ could be $1$ means all numbers are related but ... I get ahead of myself.)

Reflexive: Is is true that for all $x$ there is an $z$ so that $z|x \iff z|x$? well.... yeah. $poo \iff poo$ is always true so... this is kind of trivial.

Symmetric: Is it true that if $z|x \iff z|y$ then $z|y \iff z|x$? Well, yes... if $A \iff B$ then it's true $B \iff A$.

Transitive: Suppose there is a $z$ so that $z|x \iff z|y$ and that there is a $w$ so the $w|y \iff w|u$. Well.... foey. I'm going to point out if $z = w =1$ we have $1|x$, $1|y$, and $1|u$ so all are always true so transitivity holds.

• Transitivity even works on $\mathbb N\setminus\{1\}$. – drhab Oct 12 '16 at 8:39
• Yeah, I know but ... I didn't want to. – fleablood Oct 12 '16 at 18:14