# Quantified Propositions to English

• November 30th 2009, 05:03 PM
kturf
Quantified Propositions to English
I need help with this problem.

Let P(x, y) be x has been to y, where the domain of discourse for x is all students in this class, and the domain of discourse for y is all towns in Illinois. Express the following propositions in English.
a) ∃x ∀y P(x, y)
b) ∀y ∃x P(x, y)

I know a is There is a student in this class who has been to all towns in Illinois.

What is b?

Also - the next problem is for me to negate the above statements, can anyone help with that?

Thanks!
• December 1st 2009, 02:19 AM
emakarov
Quote:

b) ∀y ∃x P(x, y)
So, what's the problem? ∀ stands for "for all", ∃ for "there exists", so the sentence is, "For every town y there exists a student x such that x has been to y". (Here y is a town, not a student, because it is the second argument of P.) In fact, it is easy to write a computer program that translates formulas into English. Of course, it is possible to improve the style of this sentence and in particular remove variables x and y, which should be done.

The thing to note here is that the meaning changes dramatically if we swap the universal and existential quantifier. (The meaning does not change if one swaps two consecutive universal or two consecutive existential quantifiers.) In a), there is a single student who has been everywhere, whereas in b), every town may have a different student who visited it.

For negation, it is not clear if you need negations as formulas or as English sentences. In any case, there are (at least) two options. The easy one is to add "It is not the case that" or $\neg$ to the beginning of a sentence or formula. This should always work. The second option is to move the negation inside the formula. To do this, one has to change each quantifier into the other kind and add the negation before the quantifier-free inner part of the formula. E.g., the negation of $\exists x\,\forall y\,P(x,y)$ is $\forall x\,\exists y\,\neg P(x,y)$. The translation of English sentences is done similarly.