Consider
$P(x,y)$: $x$ is a citizen of $y$.
$Q(x,y)$: $x$ lives in $y$.
The universe of discourse of x is the set of all people
The universe of discourse of y is the set of US states.
Express the following English statement as logical expression using predicates and quantifiers:
"Every state has a citizen who does not live in that state".
Now I am confused between two answers,
$\forall y \exists x(P(x,y)\implies\neg Q(x,y))$
$\forall y \exists x(P(x,y)\wedge\neg Q(x,y))$
Which of these is correct? Or did I miss entirely? The first expression is true even if there is a state having no citizens. But the second one isn't. Truth table of both match only 50%.
Best Answer
There are indeed multiple ways of translating the same English sentence into the language of FOL. However, only the second formula $\forall y \exists x[ Pxy \wedge \neg Qxy ]$ in your OP is correct.
To see why, you must be acquainted with the concept of ontological commitment, or the assertion that a thing actually exists.
Universal statements make no ontological commitment. In other words, a statement like "all dragons breathe fire" translated as $\forall x [Dx \to Fx]$ makes no claim that dragons actually exist. It merely states that if any thing is a dragon, then that thing breathes fire. There may be no thing that is a dragon and the formula will still hold true, vacuously.
On the other hand, existential statements do make an ontological commitment. In other words, a statement like "there is a dragon that breathes fire" translated as $\exists x [Dx \wedge Fx]$ makes a claim that at least one dragon actually exists and it also breathes fire. In this case, if there are no dragons, then the statement is patently false.
Your English sentence "every state has a citizen who does not live in that state" makes an ontological commitment. I asserts that, in every state, there actually exists at least one person who is a citizen of that state and does not live in that state. Hence, it is not appropriate to translate the sentence in a way that suggests "if such a person existed, then..." within the scope of the existential quantifier, because the English sentence effectively says "there is such a person..."
@Malady offers some great insight into translating keywords, but you definitely want to be aware of whether a particular sentence makes an ontological commitment or not.