3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ It might be helpful to think of a person who has no friends. The statement is true but nobody needs to be quarantined. $\endgroup$ – CopyPasteIt Aug 20 '17 at 19:22
  • 1
    $\begingroup$ If it were known that the "friend" relation is symmetric, then your answer and the book's would be equivalent, and both would be correct. Without the assumption that friendship is symmetric, your answer should have $F(y,x)$ instead of $F(x,y)$, since, in the sentence to be translated, the one with measles is a friend of the one to be quarantined, not vice versa. $\endgroup$ – Andreas Blass Aug 21 '17 at 1:03
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks, that helped. I think where I got confused is that I did not understand the $ \implies $ part correctly. If it was only the $ \exists $ part alone that would be a statement that there is a friend who has measles. But because of the $ \implies $, it becomes if there exists ... $\endgroup$ – Avatar33 Aug 20 '17 at 19:31
1
$\begingroup$

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! ☺️

$\endgroup$
1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Almost: If we don't know that friendship is symmetric, then the book's $F(y,x)$ is correct and the OP's $F(x,y)$ isn't. $\endgroup$ – Andreas Blass Aug 21 '17 at 1:04
  • $\begingroup$ @AndreasBlass Oh, you're right, I didn't spot that reversal; I was too focused on the quantifiers. Thanks! $\endgroup$ – Bram28 Aug 21 '17 at 13:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.