1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – gowrath Dec 7 '16 at 23:38
  • $\begingroup$ Using LaTeX markup will get you more views, more upvotes, and most importantly, make it more likely for people to answer. Friendly FYI. $\endgroup$ – The Count Dec 7 '16 at 23:39
  • $\begingroup$ If the entailment is true, How can I prove it ? Because trying every interpretation that satisfies is impossible. $\endgroup$ – Cem Aytekin Dec 7 '16 at 23:40
  • $\begingroup$ 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. $\endgroup$ – Bram28 Dec 7 '16 at 23:48
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.