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

  • $\begingroup$ Should it be:$$xRy\iff\{ \forall z\in \mathbb{N}, z|x\iff z|y\}\quad ?$$ $\endgroup$ – b00n heT Oct 11 '16 at 18:53
  • $\begingroup$ 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$. $\endgroup$ – drhab Oct 11 '16 at 18:53
  • $\begingroup$ Edited, I'm sorry for bad representation. $\endgroup$ – Speedding Oct 11 '16 at 18:54
  • $\begingroup$ 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? $\endgroup$ – drhab Oct 11 '16 at 19:05
  • $\begingroup$ 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. $\endgroup$ – Kevin Long Oct 11 '16 at 19:07

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.

  • $\begingroup$ 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? $\endgroup$ – Speedding Oct 12 '16 at 17:33
  • $\begingroup$ I meant $\forall z \in Z$ $\endgroup$ – Speedding Oct 12 '16 at 17:35
  • $\begingroup$ 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. $\endgroup$ – 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.

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

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.