# 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.

• Entailment holds only over a certain model with a specific domain. You can't say statements that quantify over the bird universe entail statements about the horse universe; they are different models. – gowrath Dec 7 '16 at 23:38
• Using LaTeX markup will get you more views, more upvotes, and most importantly, make it more likely for people to answer. Friendly FYI. – The Count Dec 7 '16 at 23:39
• If the entailment is true, How can I prove it ? Because trying every interpretation that satisfies is impossible. – Cem Aytekin Dec 7 '16 at 23:40
• You say that you want to show that every interpretation $I$ that sets $S_1$ to true also sets $S_2$ to true. But part of any interpretation is spelling out a domain or world or universe of discourse. So, for every interpretation you are looking at the same domain for both sets. – Bram28 Dec 7 '16 at 23:48

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.
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)$.