Comparing Statements and predicates using Truth Tables

Question

Consider the four statements:

• $∃x$ $∀y$ $p(x, y)$
• $∃y$ $∀x$ $p(x, y)$
• $∀x$ $∃y$ $p(x, y)$
• $∀y$ $∃x$ $p(x, y)$

which we call S1, S2, S3 and S4 respectively.

1. Does there exist a predicate p such that S1 and s4 are true, but S2 and s3 are false?
2. Does there exist a predicate p such that S2 and s3 are true, but S1 and s4 are false?
3. Does there exist a predicate p such that S3 and s4 are true, but S1 and s2 are false?
4. Does there exist a predicate p such that S4 is true, but s1, S2 and s3 are false?

Solution:

Consider the four predicates:

One can verify that:

1. if we take p to be p1, then S1 and S4 are true, but S2 and S3 are false
2. if we take p to be p2, then S2 and S3 are true, but S1 and S4 are false
3. if we take p to be p3, then S3 and S4 are true, but S1 and S2 are false
4. if we take p to be p4, then S4 is true, but S1, S2 and S3 are false

Here are my questions:

1. Is my diagram correct (I highlighted the different sections)?

2. What is the structure of p1? How do you READ this table? Where is the INPUT? Where is the OUTPUT?
3. How does p1 get fed into $∃x$ $∀y$ $p(x, y)$?
4. How can I come up with p1?
5. What is the significance of the row with #2 (highlighted in blue)?

Answer 1

You have to read the "matrix" : $p_1, p_2, p_3, p_4$ as interpretations for the predicate letter $p$ that is $T/F$ according to the values assigned to the variables $x$ and $y$ respectively, where the values of $x$ must be read on the left and the values of $y$ on top.

Consider e.g. $S_1 : ∃x ∀y p(x,y)$, and consider the matrix $p_1$.

Is it true that there is a value for $x$ such that $p(x,y)$ is $T$ for all values for $y$ ?

YES. Consider $p_1(0,y)$: it is $T$ for both values : $0,1$ for $y$.

Thus the predicate $p_1$ satisfy the formula $S_1$.

The same for $S_4$, and these results are consistent with the solution 1: "if we take $p$ to be $p_1$, then $S_1$ and $S_4$ are true, but $S_2$ and $S_3$ are false".

---

Note

In principle, the approach is the same IF we have to read the "matrix" in the other "direction" (as suggested by you : with the values for $x$ on top and the values for $y$ on the left) : but in that case, you can see that now the predicate $p_1$ does not satisfy the formula $S_1$.

But in the same way, you can verify that $p_2$ satisfy $S_1$.