Sets and logic

I'm having a hard time with these 2 problems.

http://i53.tinypic.com/doneb4.gif






http://i51.tinypic.com/2u6eoh2.gif


I could tip 3$US for your help. If it's against the rules let me know and I'll edit my post.

You could consider the domain to be a group of people and P(x,y) to mean "x knows y". Try to figure out, provided the first proposition is true, whether the second proposition is always true, is always false, or can be either.

Also, if is false, it means that is true. You can move the negation inside, i.e., put it in front of . Then it is easier to compare the two formulas. Moving negation inside is also useful in problem #2. (Edit: Disregard the following. Basically, it reduces to question whether implies . To answer it, it is important to know if the domain is empty.)

Is it correct to say (for #1): AxEy P(x,y) can be false. If we let the domain of discourse be the persons: Roger, John, Tony and let P(x,y) be the statement "x knows y". Then ExAy P(x,y) is true, but AxEy P(x,y) is false ?

Quote:

---

If we let the domain of discourse be the persons: Roger, John, Tony and let P(x,y) be the statement "x knows y". Then ExAy P(x,y) is true, but AxEy P(x,y) is false

---

First, why are you saying that ExAy P(x,y) is true since by assumption in problem 1 it is false? Second, what you said depends on who among Roger, John and Tony knows whom. You have not provided this information. Third, the fact that AxEy P(x,y) can be false is not the whole answer: it is not clear if it is always false under the given assumption or if it can be true as well. However, the idea is right: by varying who knows whom, you can construct situations where ExAy P(x,y) is false (hence, the assumption is true), and AxEy P(x,y) is true in some situations and false in others.

First, before addressing the problem as stated, I think the crucial point is that as long as , you may use the following theorems (which are really the same theorem in disguise):

1. 
2. 

So for example in your first problem, you use theorem 2 followed by theorem 1 (written with judicious use of parentheses).

.

Unfortunately, what you assume ( ) does not imply anything about the statement you are given to evaluate ( ). This most likely means that your question is mis-worded. This can be seen further by specifying two examples for P which exhibit opposite behavior.

Let . Let . Then it is clear that your assumption holds: the statement “there exists an x such that for all y, x is less than y” is false. Again, this is the same thing as asserting . Now, one may evaluate the statement “for all x, there exists a y such that x < y” as being true. Thus, is true.

Now, with the same D, let . Then it is clear that your assumption holds: the statement “there exists an x such that for all y, y-squared is -1” is false. Again, this is the same thing as asserting . Now, one may evaluate the statement “for all x, there exists a y such y-squared is -1” as being false. Thus, is false.

So question 1 as given has no correct answer (your assumption tells you nothing about the truth or falsehood of the statement you wish to evaluate).

You can do similar analysis to show that question 2 is also mis-worded. You may, however, be able to show the converse using the following theorem (assuming a non-empty domain):

Well, let's see. The fact holds without the assumption that the domain is nonempty. I agree that in problem 1, the second formula can be true in some interpretations and false in others. However, in problem 2, the second formula is false (provided the first one is false). Here the fact that the domain is nonempty is essential because otherwise the second formula is vacuously true.