# Proof that this relation about divisiblity is reflexive, transitive, …

I can't handle this relation-evidence.

$$xRy \iff (\forall t\in\mathbb{N} \ \text{with t a prime-number}: \ t\mid x \Rightarrow t\mid y)$$

($$t\mid x$$ means $$t$$ divides $$x$$; $$t\mid y$$ means $$t$$ divides $$y$$)

Now i have to prove

• reflexivity: xRx t|x => t|x

• transitivity:∃z∈N: xRy ∧ yRz => xRz (t|x => t|y)∧(t|y => t|z) => (t|x => t|z)

• symmetry: xRy <=> yRx (t|x => t|y) <=> (t|y => t|x)

• asymmetry: xRy => not(yRx) (t|x => t|y) => not(t|y => t|x)

• antisymmetry: xRy ∧ yRx => x=y (t|x => t|y)∧(t|y => t|x) => (x=y)

I have already shown that it's reflexive.

I also tried to show the other ones, but my proof was either wrong oder not concrete enough.

I also don't know, when $$(t\mid x \Rightarrow t\mid y)$$ from $$t\mid x$$ follows $$t\mid y$$, how can $$(t\mid y \Rightarrow t\mid x)$$ from $$t\mid y$$ follows $$t\mid x$$, and what the implication => means here. And because I don't understand it, i also can't show any example that proofs falseness.

So I am thankful for any help I can get.

• Welcome to Mathematics Stack Exchange. $2\mid4$ but $4\nmid2$ — it’s not symmetric – J. W. Tanner Oct 29 '19 at 10:27
• Welcome to MSE. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to. – José Carlos Santos Oct 29 '19 at 10:27
• BTW you could abbreviate "$\forall t\in\Bbb N$ with $t$ a prime-number" to "$\forall t\in\Bbb P$". – J.G. Oct 29 '19 at 10:53
• @J.W.Tanner your counterexample is incorrect. Reread the problem statement again. That being said, the relation won't be symmetric, but then again it won't be antisymmetric either. Every prime divisor of $4$ divides $6$, but $6$ has a prime divisor that does not divide $4$. As such $4\mathcal{R} 6$ but it is not true that $6\mathcal{R}4$. On the other hand we have $4\mathcal{R} 8$ as well as $8\mathcal{R} 4$ as every prime divisor of each is the same despite $4\neq 8$. – JMoravitz Oct 29 '19 at 12:21
• Again, the relation rephrased is that $x$ is related to $y$ iff every prime divisor of $x$ is also a prime divisor of $y$. It is possible for $y$ to have more prime divisors than $x$ has. – JMoravitz Oct 29 '19 at 12:22

Hint $$\, x R y \!\iff\! \cal P_x \subseteq \cal P_y\,$$ for $$\,\cal P_n =$$ set of prime factors of $$\,n,\,$$ reduces it to easy properties of  '$$\subseteq$$'

Remark  Similarly many equivalence relations can be obtained via function pullback - see equivalence kernels (e.g. fibers, preimages, level sets / curves, etc).

I assume the relation is given over $$\mathbb{N}$$

In order to show reflexivity, that is, $$x\mathrel{R}x$$ (for every $$x\in\mathbb{N}$$), you need to show that, given any prime number $$t$$, if $$t\mid x$$, then $$t\mid x$$. This is obviously true.

Is the relation antisymmetric? No: you can see that $$2\mathrel{R}4$$ and $$4\mathrel{R}2$$, but $$2\ne 4$$.

Transitivity. Suppose $$x\mathrel{R}y$$ and $$y\mathrel{R}z$$; you want to prove that $$x\mathrel{R}z$$. So, suppose $$t$$ is a prime with $$t\mid x$$; then $$t\mid y$$, because of $$x\mathrel{R}y$$, and therefore $$t\mid z$$, because of $$y\mathrel{R}z$$. The condition that $$x\mathrel{R}z$$ has been verified.

Try the others.

HINT:

The $$\Rightarrow$$ means "implies" so $$t\mid x\Rightarrow t\mid y$$ means that whenever $$x$$ has $$t$$ as a factor so does $$y$$

For transitivity assume $$xRy$$ and $$yRz$$ and think as follows

$$xRy\iff( t\mid x\Rightarrow \underline{t\mid y})$$ also $$yRz\iff( \underline{t\mid y}\Rightarrow t\mid z).$$ Now the underlined parts are the same so you have $$t\mid x\Rightarrow t\mid z$$ which is $$xRz$$ which we wanted to prove for transitivity.

You could try now the other ones

Hope this helped