# Is this formula valid? $\forall x \forall y ( P(x,y) \rightarrow P(y,x))$

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.

• 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$. – Ian Dec 7 '17 at 20:34
• Sorry, but is the context of P play any role, if the formula is valid? – shcolf Dec 7 '17 at 20:44
• 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. – Ian Dec 7 '17 at 20:49
• 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. – shcolf Dec 7 '17 at 21:03

## 2 Answers

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

• 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? – shcolf Dec 7 '17 at 20:50
• 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. – Tiwa Aina Dec 7 '17 at 21:18
• 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? – shcolf Dec 7 '17 at 21:30
• 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). – Tiwa Aina Dec 7 '17 at 21:34

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: • 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? – shcolf Dec 8 '17 at 10:56
• @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! :) – Bram28 Dec 8 '17 at 13:24