Understanding quantifiers

Question

I'm working through "How to prove it" by Daniel Velleman. We're asked to translate the following sentence into it's logical equivalent. Anyone who has a friend who has measles will have to be quarantined.

My answer would be: Let

• $F(y,x)$ mean $y$ is a friend of $x$
• $M(y)$ mean $y$ has measles
• $Q(x)$ mean $x$ must be quarantined.

Then the statement is $ \forall x \forall y [(F(x,y) \land M(y)) \implies Q(x)] $

The book gives the answer: $ \forall x [\exists y(F(y,x) \land M(y)) \implies Q(x)] $

To me the book's answer reads as: There exists someone who has a friend who has measles. This seems different to the original statement. Could someone help me understand the provided answer and how my answer is wrong?

Answer 1

The problem here is that your statement implies '$x$ needs to be quarantined' is independent between each friend - ie, pairing $x$ with some different friend could give different answers for $Q(x)$.

However, $Q(x)$ depends on all of his friends. We need to determine $Q(x)$ from the status of all of his friends, hence the given answer.

Answer 2

From what I see, the reason your answer is incorrect in one aspect is because you've said $\forall y$ instead of $\exists y$. The importance is because you're taking all of the people x, and then saying that if there exists their friend, y, that has measles, then they will be quarantined. Hope that answers your question! ☺️

Answer 3

First, there is a slight difference between your answer and the book's answer, in that you use $F(x,y)$, and the book uses $F(y,x)$. Given that it is the one that has the measles that should be the friend of the other one, it should be $F(y,x)$, to the book is correct here.

But, as far as the difference in sign and location of quantifiers goes, your translation and the book's translation are actually in agreement!

Here is the relevant equivalence principle:

Prenex Laws

Where $\psi$ is any formula that does not contain $x$ as a free variable:

$\exists x \ \varphi(x) \rightarrow \psi \Leftrightarrow \forall x (\varphi(x) \rightarrow \psi)$

$\forall x \ \varphi(x) \rightarrow \psi \Leftrightarrow \exists x (\varphi(x) \rightarrow \psi)$

This applies to your case, since you can 'pull out' the quantifier from the book's sentence because the $Q(x)$ does not contain $y$ as a free variable. And the Prenex Laws say that if the quantifier was in the antecedent of a conditional, then it changes to the other quantifier, and so you end up with exactly your statement.

So, other than the $x$ and $y$ reversal in $F(x,y)$, you didn't do anything wrong. The book is correct, and you were almost correct ... your very small mistake had nothing to do with the quantifiers!