I have found the following problem and try to solve it by myself, but I have some doubts about it. The problem is the following:
A binary relation P is defined on Z as follows: For all $m,n\in \mathbb{Z},mPn\Leftrightarrow \exists$ a prime number p such that p|m and p|n.
Reflexive:
$mPm\Longleftrightarrow \exists p$ such that p|m and p|m, so clearly it holds the reflexive property.
(However, in the solution book it states that this property does not hold, because the author considers m=1, but 1 is not a prime number).
Symmetric:
$mPn\Longleftrightarrow \exists p$ such that $p|m\wedge p|n$
$nPm\Longleftrightarrow \exists p$ such that $p|n\wedge p|m$
Because of the commutative law this symmetric property also holds.
For the transitive property I have seen that it could be fairly straightforward also:
If I have $mPn,nPq$, then I would like to prove that $mPq$
so I take a prime p and I make that $p|m$ and $p|n$ because mPn. Also, I have that $p|n$ and $p|q$ because $nPq$ and I can say that $p|m$ and $p|q$ proving that is transitive.
However, the solution book states that the transitive property does not hold, because considering a counterexample with the following values: m=2,n=6 and p=9. We have that $mPn$ because the prime number 2 divides 2 and 6, then $nPq$ it holds when I choose 3 as a prime number that divides 6 and 9. However, the transitivity does not hold because 2 cannot divide 9.
The proof by counterexample seems right, but I would like to know if there is some way to prove this transitivity property without using the counterexample. The proof that I found and stated before seemed right, but the counterexample prove it wrong.
Thanks for your help.
Best Answer
It is NOT transitive. If mPn, it means that $\exists$ a prime p such that p|m and p|n. Also if nPq, it means that $\exists$ a prime b such that b|n and b|q. This need not imply that p=b, the fallacy in your argument.
Also note that the symmetric argument should prove “if mPn, then nPm” and not “mPn and nPm”.
It satisfies the reflexive property for all elements of $\mathbb Z$ EXCEPT 1. So overall not reflexive.