Predicate Logic Determine whether the following set of formulas
{∃xP(x), ∀xQ(x)}  (Set S1)
entails the formula
∃y(P(y) ∧ Q(y)) (Set S2)
I want to prove that every interpretation that satisfies Set S1 also satisfies S2. However I am not sure whether x and y should belong to the same universe or not. For Instance can I say that x belongs to bird universe and P is the property of having wings and y belongs to horse universe and Q is the property of being an animal. In that case S1 would not entail the formula S2.
 A: Take any interpretation $I$ with domain $D$. In order for $I$ to satisfy $S_1$, we need $I \vDash \exists x P(x)$ and $I\vDash \forall Q(x)$. In order for $I \vDash \exists x P(x)$, there needs to be some $d \in D$ such that $d \in I(P)$ where $I(P) \subseteq D$. Also, in order for $I\vDash \forall x Q(x)$, it must be true that $I(Q)=D$. Hence, $d \in I(Q)$. So, $d \in I(P)$ and $d \in I(Q)$, and so there is some $d \in D$ that satisfies the formula $P(y) \land Q(y)$, and therefore $I\vDash \exists y (P(y) \land Q(y))$. And therefore $I$ will satisfy $S_2$ as well.
A: If $\mathfrak{A}\models\exists x P(x)$ holds, you know that there is an element $a\in\vert\mathfrak{A}\vert$ such that $\mathfrak{A}\models P(a)$. (The element $a$ is sometimes called a witness for the existential statement.)
Now ask whether $\mathfrak{A}\models Q(a)$.
If you want to do this purely proof theoretically (i.e., without appealing to models), consider whatever rule you have for existential quantifier elimination and apply this rule to $\exists x P(x)$.
