Predicate logic difficulty

Question

If $∀x∃y P(x, y)$ is true, can the following be true?

1. $∀x∀yP(x, y)$ or
2. $∃x∀yP(x, y)$ or
3. $∃x∃yP(x, y) $

I understand the order of $X$ and $Y$ matters when the quantifiers are different but can the quantifier rather than the variable change, and can a 'there exists' be upgraded to a 'for all' or vice versa as in the first and third question?

Answer 1

If $∀x∃y P(x, y)$ is true, can the following be true?

Of course, all three statements can be true given the truth of the given statement. If we consider a domain with a single object that stands in relation $P$ to itself, then all four statement are true.

... this seems too obvious ... are you sure you phrased that question correctly? Shouldn't you be asking which other statements must be true given the truth of the given statement? Indeed, that is a more typical question for logic ...

So, let's change the can into must ... or, what is the same thing,let's ask which, if any, of the three statements logically follows from the given statement.

To that, the answer is only statement 3 ... and that is assuming (as most standard logics do), that the domain cannot be empty. Indeed, if the domain is not empty, then any universal statement implies its existential counterpart, i.e. $\forall x \ \varphi(x)$ implies $\exists x \ \varphi(x)$, and therefore $\forall x \ \exists y \ P(x,y)$ implies $\exists x \ \exists y \ P(x,y)$ as a specific instance of that. However, an existential statement does not imply its universal counterpart (i.e. an existential cannot be 'upgraded' to a universal)

Answer 2

It all depends on what $P(x,y)$ is. I think that perhaps you may be misunderstanding the point of the question, it seems like you are thinking about this too syntactically (i.e. you are focusing on whether 1. 2. and 3. are allowed under the language of predicate logic, which they all are) rather than semantically (i.e. thinking about what each sentence means and deducing whether they can follow from the premise of $\forall x\exists y P(x, y)$).

So to answer your question, what really needs to be done is to analyze the meaning of each of the sentences. Looking at the sentence $\forall x\exists y P(x, y)$, all it is saying is that for every $x$ you pick there will be some $y$ such that $P(x,y)$ is true. I assume that that's all the information you have about $P(x,y)$, and it's the only information you have to deduce whether the other ones can be true. I emphasize can because it is not about determining whether each sentence is actually true, just whether they're consistent with the premise. Make sure you think about $x,y$ and $P(x,y)$ abstractly, we don't actually care what each of them are, only what we can deduce based on the above sentence. Now let's analyze each of the options:

1. $\forall x\forall yP(x, y)$ This just says every $x$ can be combined with any $y$ to make $P(x,y)$ true. This is different from the original statement, which doesn't assert something as strong, but they are still compatible with each other. Although $\forall x\exists y P(x, y)$ only says that every $x$ has some $y$ that makes $P(x,y)$ true, it could moreover be true that any choice of $y$ would make $P(x,y)$ true. So $\forall x\forall yP(x, y)$ can be true.
2. This is just a weaker statement than 1., so if 1. can be true so can 2.!
3. This can be true, but as was pointed out in the comments below is not always true. If the universe from which these variables are quantified over is empty, then while $\forall x\exists y P(x, y)$ is vacuously true, $\exists x\exists y P(x, y)$ must be false. If on the other hand the universe is non-trivial then this must be true. There does exist an $x$ for which there exists a $y$ that makes $P(x,y)$ true. In fact, by our assumption, any choice of $x$ satisfies this. In general you can look at $\exists$ as a downgrade of $\forall$. If something is true for all choices of $x$ then it must be true for some single choice of $x$, as long as choices for $x$ actually exist (i.e. we're not talking about the empty set). The converse is not always true on the other hand, if something is true for some single choice of $x$, you can't necessarily conclude it's true for all $x$.

Answer 3

None of these are implied by the given statement.

1. $\forall x\exists y P(x,y)\not\to\forall x\forall y P(x,y)$: Let $x,y\in\mathbb N$, and let $P(x,y)$ be the equality relation.

2. $\forall x\exists y P(x,y)\not\to\exists x\forall y P(x,y)$: Same example as $1$.

3. $\forall x\exists y P(x,y)\not\to\exists x\exists y P(x,y)$: Let $x,y\in\varnothing$, and $P(x,y)$ be the false relation. $\forall x\exists y P(x,y)$ is true since the statement is true for all $x$ (since there are no $x$). However, there does not exist an $x,y$ such that $P(x,y)$, so that is false.