Proof that this relation about divisiblity is reflexive, transitive, ...

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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