Predicate Logic and Calculus

Question

Question of the week came up in my schools logic club but there is not much information to it. Here is the question:

Show that

$$ \exists x\,[R(x)\wedge \lnot Q(x)],\ \forall x\,[P(x)\to Q(x)],\, \forall x[R(x)\to(P(x)\vee S(x))] \models \exists x\,[R(x)\wedge S(x)] $$ Describe in details all your work

Now I know that it does not want us to use formal deduction, so what method do they want us to use then? Formal Deduction is the only way I am familiar with at the moment but apparently that has been ruled out as a possible method.

Answer 1

Start with $\exists x(Rx\land\neg Qx)$ and instantiate, i.e. infer $(Ra\land\neg Qa)$.

Since $\forall x(Px\to Qx)$, we have $Pa\to Qa$. But since $\neg Qa$, then necessarily $\neg Pa$.

Finally, $\forall x(Rx\to(Px\lor Sx))$ gives $Ra\to (Pa\lor Sa)$. And since $Ra$ and $\neg Pa$, then necessarily $Sa$.

$$Ra\land\neg Qa\land\neg Pa\land Sa\to\exists x(Rx\land Sx)$$

Answer 2

Note that what the question asks to have proved is not a "$\vdash$" statement, but a "$\vDash$" statement -- thus, you're being asked to prove that any structure that satisfies the three premises will also satisfy $\exists x(R(x)\land S(x))$.

One way to do this would indeed be to present a formal proof of the "$\vdash$" entailment, and then appeal to some known result that the proof system you're using is sound. But apparently that's not what you're supposed to do.

The other option is to reason directly (and informally, that is, in everyday mathematical style) about $\vDash$, and what it means for the various formulas to be satisfied in a structure:

Given a structure $(\mathfrak M,P_{\mathfrak M},Q_{\mathfrak M}, R_{\mathfrak M},S_{\mathfrak M})$ which satisfies such-and-such we need to find an $x\in\mathfrak M$ such that $x\in R_{\mathfrak M}$ and $x\in S_{\mathfrak M}$. Because $\mathfrak M\vDash \exists x(R(x)\land\neg Q(x)$ we know that $\mathfrak M$ contains an $x$ such that $x\in R_{\mathfrak M}$ and $x\notin Q_{\mathfrak M}$. (And so forth ...)