1

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

Cure
  • 4,051
  • Why is the title saying "Models", then? Models are semantics, not syntactic. I expected a whole other question inside. – Asaf Karagila 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. – Asaf Karagila Jul 28 '14 at 21:00

2 Answers2

2

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

Peter Smith
  • 54,743
  • 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
1

Ps this is just an addition to Peter smiths answer, If you want to upvote this answer then please upvotes peter smiths answr as well.

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
Willemien
  • 6,582