A model in which the formula holds

Question

I'm supposed to find a model in which the formula
$$\exists x(\forall y(P(x) \land Q(x,y)))$$ holds.

Does the model below work?:

$M$:

• $U = \{a,b\}$,
• $P=\{a,b\}$,
• $Q=\{(a,b), (b,a)\}$.

Answer 1

No, the interpretation you proposed does not make the formula $$\tag{$*$} \exists x(\forall y(P(x) \land Q(x,y))) $$ true. Indeed, according your interpretation, there are two possibilities for $x$:

1. either $x = a$, and then for $y = a$ we have (according your interpretation) that $P(a)$ holds, but $Q(a,a)$ does not hold;
2. or $x = b$, and then for $y = b$ we have (according your interpretation) that $P(b)$ holds, but $Q(b,b)$ does not hold.

To solve the problem, and have an interpretation $I$ that makes the formula $(*)$ true, you can keep a domain $|I|$ with exactly two elements $a$ and $b$, and slightly change the interpretations of $P$ and $Q$ in $I$ as follows:

!\begin{align} P^I &= \{a\} \\ Q^I &= \{(a,a), (a,b)\} \end{align}

If you look for a more "minimalist" solution, you can take an interpretation $J$ whose domain is $|J| = \{a\}$ (only one element) and the interpretations of $P$ and $Q$ are as follows:

!\begin{align} P^I &= \{a\} \\ Q^I &= \{(a,a)\} \end{align}

Answer 2

You can use the Tree Proof Generator. It says that the expression $$\tag{1} \exists x(\forall y(P(x) \land Q(x,y)))$$ is invalid and displays:

Countermodel:
Domain: { 0 }
P:  { }
Q:  { }

If you input

$$\tag{2} \exists x(\forall y(P(x) \land Q(x,y)))$$

instead, it also says that the expression is invalid and displays

Countermodel:
Domain: { 0 }
x:  0
P:  { }
Q:  { }

So for the $x$ that should exist you can choose $x=0$. For $y=0$ we have

$$P(0) \land Q(0,0)$$ is false.