1
$\begingroup$

This may seem a simple question for many of you guys, but I'm having hard time understanding basic concepts here.

$$\forall x \forall y ( P(x,y) \rightarrow P(y,x)) $$

As I understand, I need to prove whether the above formula is valid, or just provide a counter example. I couldn't come up with one though.

With a similar problem, $$\forall x \exists y ( P(x,y) \rightarrow P(y,x)) $$ I was able to provide a counter example.
If our domain is $\mathbb{N}$ and $P(x,y)$ represents $x < y$, then we get $T \rightarrow F$ which is false.

Some of my thoughts which may be essentially wrong.
On the other hand, I have noticed one thing, which was (I believe) true in propositional calculus. If the formula is not valid, then the negation of it is satisfy-able.

So if we do some manipulations, then we can get $\exists x \exists y \neg ( P(x,y) \rightarrow P(y,x)) $, which is satisfy-able, so that implies that the formula is not valid. But here, due to lack of knowledge and also experience, I don't feel, that this is the right way.

I use Mendelson's book, in case if you're wondering. Pointing out my own mistakes is much appreciated :)
Thank you.

$\endgroup$
  • $\begingroup$ Well, P isn't quantified or specified, so it could be true or false depending on what P is. But yes, a simple counterexample is to make the domain be $\mathbb{N}$ or similar, and $P(x,y)=x<y$, in which case the formula fails for $x=1,y=2$. $\endgroup$ – Ian Dec 7 '17 at 20:34
  • $\begingroup$ Sorry, but is the context of P play any role, if the formula is valid? $\endgroup$ – shcolf Dec 7 '17 at 20:44
  • $\begingroup$ I don't really know what "the formula is valid" means in this context. What I think you intend is to ask whether $\forall P \forall x \forall y P(x,y) \Rightarrow P(y,x)$ for all $x,y,P$ in some appropriate problem domain (e.g. binary relations on the natural numbers). That can be refuted by presenting an example $P$ for which $\forall x \forall y P(x,y) \Rightarrow P(y,x)$ fails. But without quantifying or specifying $P$, it's not entirely clear what your question is. $\endgroup$ – Ian Dec 7 '17 at 20:49
  • $\begingroup$ Yes, I think you got my intention right about $\forall P$ as a prefix. Maybe my book uses different syntax. What I mean by "the formula is valid", is if the formula is a tautology? Sorry for confusion. And yes, we are free to refute the formula, if it's not valid. $\endgroup$ – shcolf Dec 7 '17 at 21:03
1
$\begingroup$

How about $P(x,y) = x \text{ is a multiple of } y$ ?

Finding a counterexample proposition is essentially finding a proposition where having $x\mathrm Ry$ doesn't mean that $y\mathrm Rx$, for some relation $\mathrm R$.

$\endgroup$
  • $\begingroup$ Thank you for your answer. I just don't get one thing. When you say $x$ is a multiple of $y$, does this handle the case when $x=y$? Or this isn't important because we found at least one pair of $(x,y)$ that doesn't satisfy the formula? $\endgroup$ – shcolf Dec 7 '17 at 20:50
  • $\begingroup$ Indeed, it isn't important because we found at least one pair that doesn't satisfy the formula. While it's true for one specific case $(x,y)$ where $x=y$, it's not true $\forall x \forall y$, as stated in the formula. $\endgroup$ – Tiwa Aina Dec 7 '17 at 21:18
  • $\begingroup$ Ok, got you. One more thing is confusing me though. If we have a statement like $\forall x \forall y P(x,y)$ and $P(x,y)$ is just as you defined, this will be false, because it's not true $\forall x \forall y $, no? $\endgroup$ – shcolf Dec 7 '17 at 21:30
  • $\begingroup$ If the statement is just $\forall x \forall y P(x,y)$ on its own? Then yes, since it is false for any coprime $x,y$ and for $x<y$ (in other words, it's not true $\forall x \forall y$, as you said). $\endgroup$ – Tiwa Aina Dec 7 '17 at 21:34
1
$\begingroup$

You can use the exact same counterexample as you used for that other problem! That is, take the natural numbers as the domain, and interpret $P(x,y)$ as $x < y$

Then $\forall x \forall y (P(x,y) \rightarrow P(y,x))$ says that for any two numbers $x$ and $y$: if $x < y$ then $y <x$ ... which is clearly false!

And ironically, this counterexample does actually not work to show that $\forall x \exists y (P(x,y) \rightarrow P(y,x))$ is not valid, since for any number $x$, I can pick a number $y$, namely $x$ itself, such that $x \not < y$, and hence we have $\neg P(x,y)$, and hence $P(x,y) \rightarrow P(y,x)$. In fact, there is no counterexample to $\forall x \exists y (P(x,y) \rightarrow P(y,x))$, because that statement is valid! Here is a proof:

enter image description here

$\endgroup$
  • $\begingroup$ Wow, interesting, thanks a lot! I'll check the proof once I get back home. :) BTW, are you using a tool for generating the proof, or you wrote this by hand? $\endgroup$ – shcolf Dec 8 '17 at 10:56
  • $\begingroup$ @shcolf It's a tool called Fitch that comes with a commercial logic textbook so unfortunately it's not free ... but it does check the validity of the proof! :) $\endgroup$ – Bram28 Dec 8 '17 at 13:24

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.