0
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Kevin
    Apr 1 at 23:43

2 Answers 2

4
$\begingroup$

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.


In general, for this kind of question, I always prefer to turn the sentence to the positive, that is, if I have to prove that a formula is false (in a certain structure) I show that its negation is true (in the same structure), and I internalize the negation as much as I can. This way, I avoid dealing with nested negations, which are very error-prone.

$\endgroup$
1
$\begingroup$

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.

Hence, your model does make the statement false.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .