# Predicate logic: Find a model so that the formula is false. [closed]

This question comes from an old exam: Describe a model where the following is false: $$\forall_{x} \forall_{y}(P(x,y) \to \neg Q(x,y))$$.

I take the model $$M$$ as follows: \begin{align} M = ( \!U = \text{the set of even numbers}, & \quad P(x, y) = "\!2 \text{ divides } x \text{ and } y\!", \\ & \quad Q(x, y) = "\!x \times y \text{ is divisible by } 2\!\end{align}

My question: Does this satisfy the requirement? I think so but I am always unsure about these. I have posted a similar question yesterday but I am not sure whether or not this counts as a double post because it is a little bit different and also this time I want to verify. If this is not allowed, notify me and I will delete it.

• That strikes me as a "too easy" question. You can give the structure where U contains a single element x (for whatever value of x you like), and P(x, x) and Q(x, x) are both true. Of course, if it specified "a model of arithmetic" or some such, then it's closer to being a real question, but even then, P and Q have no special meaning within the axioms of arithmetic, and can still be defined e.g. as tautologies. Apr 1 at 23:43

Proving that a formula $$A$$ is false in a certain structure (aka model, according to your terminology) amounts to proving that its negation $$\lnot A$$ is true in such a structure.
In your case, we have $$A = \forall x \forall y \, (P(x,y) \to \lnot Q(x,y))$$. Its negation is $$\lnot A = \lnot \forall x \forall y \, (P(x,y) \to \lnot Q(x,y)) \equiv \exists x \exists y \, (P(x,y) \land Q(x,y))$$, where $$\equiv$$ stands for logical equivalence, obtained by applying de Morgan's laws.
Thus, within the structure you have defined, your question amounts to showing that there exist two even natural numbers $$m$$ and $$n$$ that are both divisible by $$2$$, and such that $$m \times n$$ is divisible by $$2$$. Of course, this is true! Take for instance $$m = n = 2$$. Said differently, your answer is correct.
Since the domain consists only of even numbers, $$(P(x, y))$$ is always true. Similarly, $$(Q(x, y))$$ is always true because the product of any two even numbers is divisible by 2. So, there will be instances where $$(P(x, y))$$ is true and $$(Q(x, y))$$ is also true, thus making $$(P(x, y))\rightarrow\neg Q(x, y)$$ false.