Counterexample $\neg \forall x~(P(x) \to \exists y~Q(x,y)), \forall x~\forall y~(R(x,y) \to (P(y) \vee Q(y,x))) \vdash \cdots$

Question

$$\dfrac{\quad{\neg \forall x~\big(P(x) \to \exists y~Q(x,y)\big) ~,\\ \forall x~\forall y~\Big(R(x,y) \to \big(P(y) \vee Q(y,x)\big)\Big)}\hspace{2ex}}{\therefore\quad\exists z~\Big(\neg P(z)\vee\forall y~\big(Q(z,y)\wedge\neg R(y,z)\big)\Big)} $$

$\uparrow$ I need to find a counter example of the logically invalid statement above

I have tried setting up a thruth table for determining the cases in which all premesis are true but the conclusion is false (these scenarios can be used as counter examples if I am correct). From the thruth table I found two combinations of (Q,P,R) (where Q indicates Q(x,y)=true etc.), however I am quite sure this approach is not the best one if it is even correct.

I am not sure how to work with the first premise since it uses the $\exists$ quantifier.

I have tried rewriting the statements into simpler form (rewriting the implication A $\rightarrow B$ as $\neg A \vee B$ etc. but am I not sure what form of the arguments should be in for finding the counter example.

I hope my writing is somewhat understandable. If any clarification is needed please ask me.

Any help is greatly appreciated , Thank you very much!

Here is some of my work: The first image shows my attempt at simplification of the premises/conclusion.

The second image shows my attempt at finding a counter example:

Answer 1

Tip: Use alpha-replacement to express your statements with the same tokens in the same order in the predicates.   Also rearrange them into PreNex normal form.

$$\dfrac{\because\quad{\neg \forall x~\big(P(x) \to \exists y~Q(x,y)\big) ~,\\ \forall x~\forall y~\Big(R(x,y) \to \big(P(y) \vee Q(y,x)\big)\Big)}\hspace{2ex}}{\therefore\quad\exists z~\Big(\neg P(z)\vee\forall y~\big(Q(z,y)\wedge\neg R(y,z)\big)\Big)}\qquad\dfrac{\because\quad{\neg \forall z~\exists y~\big(P(z) \to Q(z,y)\big) ~,\\ \forall y~\forall z~\Big(R(y,z) \to \big(P(z) \vee Q(z,y)\big)\Big)}\hspace{2ex}}{\therefore\quad\exists z~\forall y~\Big(\neg P(z)\vee\big(Q(z,y)\wedge\neg R(y,z)\big)\Big)} $$

Answer 2

For your counterexample you should consider a number of different objects that do or do not have certain properties and that do or do not stand in certain relationships ... However, if the domain contain infinitely many objects, then you get infinitely many possible properties and relationships, and the truth-table method cannot be used. And even if the domain is of finite size, the number of possible properties and relationships grows exponentially, so the truth-table method may not be very practical.

Here are some further thoughts/observations:

1. Since the conclusion needs to be false, all objects in the domain need to have property $P$. It also needs to be the case that for any object $z$, there needs to be some object $y$ such that either $\neg Q(z,y)$ or $R(y,z)$

2. Notice that if all objects have property $P$, then automatically premise $2$ is satisfied, no matter what relations $Q$ or $R$ hold.

3. Given that all objects have property $P$, in order for the first premise to be true, you need at least one object $x$ such that for any $y$ we have $\neg Q(x,y)$

All this means that we can easily generate a counterexample simply by having all objects have property $P$, by having no pair of objects stand in relation $Q$, and by having all pairs of objects stand in relation $R$

In fact, the simplest counterexample would be to have just one object that has property $P$, that does not stand in relation $Q$ to itself, and that does stand in relation $R$ to itself (though the latter is not necessary).

Now, as it so happens, with $1$ object in the domain (let's denote it with $a$), then what you did with the truth-table does, in a way, work out ... though please understand that your $P$ is really $P(a)$, your $Q$ is really $Q(a,a)$, and your $R$ is really $R(a,a)$. As such, you found the same two ways to do so as I indicated above.

However, please know that you got very lucky here! Typically you will need multiple objects for a counterexample, and things will get much more complicated than what you did. In particular, you can no longer just work with the predicate symbols and treat them as if they are atomic statements, since with two different objects $a$ and $b$, $P(a)$ is a different claim from $P(b)$.