1. ## Quantifier question

Hello people,

Finals is coming up, and my teacher gave us a worksheet of problems to work on because they will be similar to the ones on the exam. My problem is I just never grasped quantifiers, and he gave us a problem that uses this.

I have to to express each of these statements using quantifiers, then form the negation of the statement so that no negation is to the left of the quantifier:

1. Someone has visited every state in the US except Oregon and Nebraska.

2. No one has visited every state in the US.

3. Every USC student has visited someone in NYC or visited someone in another town
who visited someone in NYC.

I'm thinking I start with V(x,y) being the statement "x has visited y"? number 1 and 3 is very hard to me, but I tried number 2 and this is what I got.

2. $\displaystyle \neg \forall x V(x,every state in the US)$

can anybody help me with this?

2. Concerning problem 2, there are two ways to formulate "no one has property P" using quantifiers: (1) for every x, it is not the case that P(x) and (2) it is not the case that there exists an x such that P(x). The property P here is that x visited every state. This can be formulated as "for every y, x visited y".

Problem 1 is easy if there were no exceptions (Oregon and Nebraska). Then one would say, "There exists a person x such that for every state y, x visited y". To make sure that the state y is neither Oregon nor Nebraska, we could say, "for every state y, if y is not Oregon and y is not Nebraska, then ...".

For problem 3, I would expect the instructor to give the basic relations that can be used in translation. Without this information, if I wanted to play smart alec, I would call the translation of the whole proposition by one letter P.

In problem 3, it makes sense to say V(x, y) again denotes "x visited y", but y is now a person. Also, it makes sense to consider a set of places with NYC and possibly USC being constants from this set. Finally, one needs another relation L(x, y) for "x is in y" where x is a person and y is a place. Alternatively, one can consider a ternary relation V(x, y, z) to mean "x visited y who is in z".

3. Thanks for your help emarkov,

My instructor did not give a basic relation for problem 3 unfortunately, I will look at the info you gave me and try to do the problems now. If I need any more help I will post again, hope you will answer