Is this relation an equivalence?

Question

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
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
Start by telling us something about $x$ and $y$. What are they? Integers maybe? — drhab, Oct 11 '16 at 19:12
This is very hard to parse. What if $z=1$? Then (trusting that $x,y\in \mathbb N$) isn't your condition trivially satisfied? — lulu, Oct 11 '16 at 19:13

score 1 · Answer 1 · answered Oct 11 '16 at 19:39

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$.

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

score 1 · Accepted Answer · answered Oct 12 '16 at 08:37

1

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.

answered Oct 12 '16 at 08:37

drhab

151,093

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 07:25

Is this relation an equivalence?

2 Answers2