Prove or disprove the syntactic consequence.

Consider $\forall x(Px\implies Qx)$. Which of the following are syntactic consequence of the former?: (i)$\forall xPx$, (ii) $\exists x Px$, (iii) $\exists x (Px\wedge Qx)$, (iv) $\neg\exists x (Px\wedge \neg Qx)$.

I managed to solve the four parts, it would be great if someone could check them up.

First, $\forall x(Px\implies Qx)$ would be trivially true if there is no $x$ such that $Px.$ This could prove (i)-(iii) false giving a model of the premise that is not of the conclusion.

(i) Consider the model M= $\{\{a,b,P,Q\};a,b;\{a\},\{a\}\}$. Then $M(Pa)=M(Qa)=T$ which means $M(Pa\implies Qa)=T$, and since $M(Pb)=F$ we have $M(Pb\implies Qb)=T$; here I conclude $M(\forall x (Px\implies Qx))=T$ but $M(Pb)=F$ so $M(\forall xPx)=F$.

(ii) Define the relation $P$ as the empty set, then for an interpretation $M$ is $M(Px)=F$ for each $x$ -this is, $M(\exists x Px)=F$-, but $M(Px\implies Qx)=T$ for each $x$ because $Px$ is never true.

(iii) False because of (ii).

(iv) This seems to be true. Checking the syntactical consequence:

$1.\forall x (Px\implies Qx) \;(Pre.) \\ 2. \exists x(Px\wedge \neg Qx)\; (Assumption)\\ 3. Pa \\ 4. \neg Qa \\5. \neg (Pa\implies Qa)\\ 6. \neg \forall x (Px\implies Qx)\;(Contradiction)\\7.\neg\exists x(Px\implies \neg Qx)$

• Why is the title saying "Models", then? Models are semantics, not syntactic. I expected a whole other question inside. Jul 28 '14 at 20:55
• I wrote 'Models' in the title because using the correction theorem we can prove there is no syntatic consequence giving a model of the premise that is not of the conclusion, just as in the semantic case. Should I edit the title?.
– Cure
Jul 28 '14 at 21:00
• Well, I expected this to be a question about the completeness theorem. Jul 28 '14 at 21:00

(i) to (iii) are indeed not syntactic consequences of the given assumption.

(iv) is a syntactic consequence -- but whether your proof is OK will depend on the system you are supposed to be using. In particular, the step from (5) to (6) involves the rule from $\neg\varphi(a)$ infer $\neg\forall x\varphi(x)$ which is certainly sound but it is not usually a basic rule in a natural deduction or other system. So you'll need to tell us what syntactic system you are supposed to be using before we can tell you if your proof is well-formed in it.

• Thanks. Taking a look of the properties I can use I see you were right and the inference from (5) to (6) was not valid.
– Cure
Jul 29 '14 at 16:07

Just to give an correct proof of (iv)

1  |         Vx ( Px -> Qx)     Premisse
.  ------------------------------------
2  | |_____  Ex ( Px & ~Qx)     Assumption for ~ Introduction
3  | | |__a  Pa & ~Qa           Assumption for Existentional elimination
4  | | |     Pa                 3 & Elimination
5  | | |     Pa -> Qa           1 Universal Elimination
6  | | |     Qa                 4,5 -> Elimination
7  | | |     ~Qa                3 & Elimination
8  | | |     _|_                6,7 _|_ Introduction
.  | | <---------------------------- end subproof
9  | |       _|_                2, 3-8 Existentional elimination
.  | <------------------------------ end subproof
10 |         ~Ex ( Px & ~Qx)    2-9 ~ Introduction