Can a English statement be expressed as more than one logical expression, both of which mean the same thing?

Question

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%.

Answer 1

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.

Answer 2

I think your misunderstanding comes from a misunderstanding of the logical implication. Have you seen the implication as disjunction? $$(A \implies B) \iff (\neg A \lor B)$$ Now your English statement which you had to express in the language of logic was "Every state has a citizen who does not live in this state." Now think about what this means. For this to be true, for every state there must exist a person who is a citizen of that state but who does not live in the state.

I italicized the important phrases here, which have clear logical analogs in this problem. Let us begin translating this into logic.

"For every state" is the universal quantifier on states, "$\forall \mbox{ states } y$". "There exists a person" is the existential quantifier on people, thus we have "$\forall \mbox{ states } y \; \exists \mbox{ a person } x $". "Is a citizen of" is the predicate $P$, thus we have "$\forall \mbox{ states } y \; \exists \mbox{ a person } x \; P(x,y)$". "But" is the logical conjunction, so we have "$\forall \mbox{ states } y \; \exists \mbox{ a person } x \; P(x,y) \land $". "Does not live in" is the predicate $\neg Q$, so finally we have:

$$\forall \mbox{ states } y \; \exists \mbox{ a person } x \; P(x,y) \land \neg Q(x,y) $$

Thus the second answer is right, the first is wrong. Do you understand why this is conjunction, and not implication?