0

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.

Lila
  • 479
  • 4
    You want to prove something is right, when you already have a proof that it is wrong. If you could do that, you would single-handedly destroy all of mathematics. A better use of your time would be to understand why your argument for transitivity is a fallacious argument. Also, the book is right about reflexivity, and you should try to understand why, again, your reasoning is fallacious. – Gerry Myerson Jun 02 '22 at 13:26
  • thank you for your comment @Gerry Myerson, I was just curious if it was possible to disprove it in some formal way and not using counterexample. I will review it. – Lila Jun 02 '22 at 18:28
  • @Lila I think the main reason everyone(including me) was getting confused was your repeated use of “proof” when you clearly meant “disproof”. I hope my answer helped. Thanks! – insipidintegrator Jun 02 '22 at 18:44
  • thank you @insipidintegrator it served a lot, now I know that I should use the correct terminology. – Lila Jun 02 '22 at 19:52
  • 2
    Since a lot of people learning discrete math find disproofs by counterexample unsatisfying, I think it's worth emphasizing: if you want to prove the negation of a universally quantified statement (something like $\neg \forall x P(x)$), producing a counterexample is not informal or nonrigorous at all---it's exactly what you need to do. Reason: by De Morgan's laws, $\neg \forall x P(x)$ is equivalent to $\exists x (\neg P(x))$. How does one prove an existential statement? By constructing an example--in this case, a value of $c$ such that $\neg P(c)$. – Ravi Fernando Jun 03 '22 at 04:57

1 Answers1

3

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.

insipidintegrator
  • 6,642
  • thank you for your answer, it was really helpful, but could you expand a little bit the proof of the transitive part, is there any formal way to express it? – Lila Jun 02 '22 at 13:58
  • YOU CANNOT PROVE IT. IT IS FALSE. YOU COULD PROVE IT ONLY IF IT WERE TRUE. Do you want me to elaborate on the disproof? – insipidintegrator Jun 02 '22 at 14:13
  • Please do not write in uppercase because it is somewhat rude in online postings. The issue is that I saw that the author proof it (that it was false), but I was wondering if there was another way to prove it more formally (just for the sake of curiosity). – Lila Jun 02 '22 at 18:00
  • 2
    So you want a more rigorous _dis_proof? Well, a single counter example (as you mention that the author talks about 2, 6 and 9) is enough to completely disprove the statement. I believe that you are in pursuit of a rigorous, well-written set of statements arguing that the transitivity property is false when applied to the given relation, and are not content with the counter example. We prove a statement because we want to show that the statement holds for all possible elements of a specified set. But here we say that it does not hold for all, which is evident from the counter example. – insipidintegrator Jun 02 '22 at 18:28
  • thanks for your comment and your time, yes you are right. with the counter example it might seem enough. – Lila Jun 02 '22 at 18:29
  • After you were told, several times, Lila, that you can't prove something that has already been proved to be false, you still insisted on asking for a proof of the false statement. In view of that, insipid was more than justified in shouting at you, since mere repetition didn't seem to be getting through. But, insipid, the last word in your answer should be "reflexive", rather than "symmetric". – Gerry Myerson Jun 02 '22 at 23:44
  • @GerryMyerson I think the OP just used instead of disproof. Nothing malicious. – insipidintegrator Jun 03 '22 at 04:35
  • I'm sure no malice was intended. I'm saying that after being told, repeatedly, that you couldn't prove something you had already disproved, Lila might have taken a moment to wonder why users kept telling her that, and might have figured out why we were doing that, or might have asked us why we were doing that, instead of just continuing as if nothing had happened. Hey, you were the one who shouted at Lila, not me! – Gerry Myerson Jun 03 '22 at 05:07
  • 1
    @GerryMyerson – insipidintegrator Jun 03 '22 at 05:51