Solutions to Chapter 38 Conversion of quantifiers

A. Show in each case that the sentences are inconsistent:

1. 1.
   ​

   $Sa\to T(m),T(m)\to S(a),T(m)\wedge \neg S(a)$

   Line number	Subproof level	Formula	Justification
   $1$	0	$S(a)\to T(m)$
   $2$	0	$T(m)\to S(a)$
   $3$	0	$T(m)\wedge \neg S(a)$
   $4$	0	$T(m)$	$\wedge$E $3$
   $5$	0	$\neg S(a)$	$\wedge$E $3$
   $6$	0	$S(a)$	$\to$E $2$, $4$
   $7$	0	$\perp$	$\neg$E $5$, $6$

2. 2.
   ​

   $\neg \exists xR(x,a),\forall x\forall yR(y,x)$

   Line number	Subproof level	Formula	Justification
   $1$	0	$\neg \exists xR(x,a)$
   $2$	0	$\forall x\forall yR(y,x)$
   $3$	0	$\forall x\neg R(x,a)$	CQ $1$
   $4$	0	$\neg R(b,a)$	$\forall$E $3$
   $5$	0	$\forall yR(y,a)$	$\forall$E $2$
   $6$	0	$R(b,a)$	$\forall$E $5$
   $7$	0	$\perp$	$\neg$E $6$, $4$

3. 3.
   ​

   $\neg \exists x\exists yL(x,y),L(a,a)$

   Line number	Subproof level	Formula	Justification
   $1$	0	$\neg \exists x\exists yL(x,y)$
   $2$	0	$L(a,a)$
   $3$	0	$\forall x\neg \exists yL(x,y)$	CQ $1$
   $4$	0	$\neg \exists yL(a,y)$	$\forall$E $3$
   $5$	0	$\forall y\neg L(a,y)$	CQ $4$
   $6$	0	$\neg L(a,a)$	$\forall$E $5$
   $7$	0	$\perp$	$\neg$E $2$, $6$

4. 4.
   ​

   $\forall x(P(x)\to Q(x)),\forall z(P(z)\to R(z)),\forall yP(y),\neg Q(a)\wedge \neg R(b)$

   Line number	Subproof level	Formula	Justification
   $1$	0	$\forall x(P(x)\to Q(x))$
   $2$	0	$\forall z(P(z)\to R(z))$
   $3$	0	$\forall yP(y)$
   $4$	0	$\neg Q(a)\wedge \neg R(b)$
   $5$	0	$\neg Q(a)$	$\wedge$E $4$
   $6$	0	$P(a)\to Q(a)$	$\forall$E $1$
   $7$	0	$\neg P(a)$	MT $6$, $5$
   $8$	0	$P(a)$	$\forall$E $3$
   $9$	0	$\perp$	$\neg$E $8$, $7$

B. Show that each pair of sentences is interderivable:

C. In appendix 24, we considered what happens when we move quantifiers ‘across’ various logical operators. Show that each pair of sentences is interderivable:

1. 1.
   ​

   $\forall x(F(x)\wedge G(a)),\forall xF(x)\wedge G(a)$

   Line number	Subproof level	Formula	Justification
   $1$	0	$\forall x(F(x)\wedge G(a))$
   $2$	0	$F(b)\wedge G(a)$	$\forall$E $1$
   $3$	0	$F(b)$	$\wedge$E $2$
   $4$	0	$G(a)$	$\wedge$E $6$
   $5$	0	$\forall xF(x)$	$\forall$I $3$
   $6$	0	$\forall xF(x)\wedge G(a)$	$\wedge$I $5$, $4$

   Line number	Subproof level	Formula	Justification
   $1$	0	$\forall xF(x)\wedge G(a)$
   $2$	0	$\forall xF(x)$	$\wedge$E $1$
   $3$	0	$G(a)$	$\wedge$E $1$
   $4$	0	$F(b)$	$\forall$E $2$
   $5$	0	$F(b)\wedge G(a)$	$\wedge$I $4$, $3$
   $6$	0	$\forall x(F(x)\wedge G(a))$	$\forall$I $5$

2. 2.
   ​

   $\exists x(F(x)\vee G(a)),\exists xF(x)\vee G(a)$

   Line number	Subproof level	Formula	Justification
   $1$	0	$\exists x(F(x)\vee G(a))$
   $2$	open subproof, 1	$F(b)\vee G(a)$
   $3$	open subproof, 2	$F(b)$
   $4$	2	$\exists xF(x)$	$\exists$I $3$
   $5$	2	$\exists xF(x)\vee G(a)$	$\vee$I $4$
   $6$	close subproof, open subproof, 2	$G(a)$
   $7$	2	$\exists xF(x)\vee G(a)$	$\vee$I $6$
   $8$	close subproof, 1	$\exists xF(x)\vee G(a)$	$\vee$E $2$, $3$–$5$, $6$–$7$
   $9$	close subproof, 0	$\exists xF(x)\vee G(a)$	$\exists$E $1$, $2$–$8$

   Line number	Subproof level	Formula	Justification
   $1$	0	$\exists xF(x)\vee G(a)$
   $2$	open subproof, 1	$\exists xF(x)$
   $3$	open subproof, 2	$F(b)$
   $4$	2	$F(b)\vee G(a)$	$\vee$I $3$
   $5$	2	$\exists x(F(x)\vee G(a))$	$\exists$I $4$
   $6$	close subproof, 1	$\exists x(F(x)\vee G(a))$	$\exists$E $2$, $3$–$5$
   $7$	close subproof, open subproof, 1	$G(a)$
   $8$	1	$F(b)\vee G(a)$	$\vee$I $7$
   $9$	1	$\exists x(F(x)\vee G(a))$	$\exists$I $8$
   $10$	close subproof, 0	$\exists x(F(x)\vee G(a))$	$\vee$E $1$, $2$–$6$, $7$–$9$

3. 3.
   ​

   $\forall x(G(a)\to F(x)),G(a)\to \forall xF(x)$

   Line number	Subproof level	Formula	Justification
   $1$	0	$\forall x(G(a)\to F(x))$
   $2$	0	$G(a)\to F(b)$	$\forall$E $1$
   $3$	open subproof, 1	$G(a)$
   $4$	1	$F(b)$	$\to$E $2$, $3$
   $5$	1	$\forall xF(x)$	$\forall$I $4$
   $6$	close subproof, 0	$G(a)\to \forall xF(x)$	$\to$I $3$–$5$

   Line number	Subproof level	Formula	Justification
   $1$	0	$G(a)\to \forall xF(x)$
   $2$	open subproof, 1	$G(a)$
   $3$	1	$\forall xF(x)$	$\to$E $1$, $2$
   $4$	1	$F(b)$	$\forall$E $3$
   $5$	close subproof, 0	$G(a)\to F(b)$	$\to$I $2$–$4$
   $6$	0	$\forall x(G(a)\to F(x))$	$\forall$I $5$

4. 4.
   ​

   $\forall x(F(x)\to G(a)),\exists xF(x)\to G(a)$

   Line number	Subproof level	Formula	Justification
   $1$	0	$\forall x(F(x)\to G(a))$
   $2$	open subproof, 1	$\exists xF(x)$
   $3$	open subproof, 2	$F(b)$
   $4$	2	$F(b)\to G(a)$	$\forall$E $1$
   $5$	2	$G(a)$	$\to$E $4$, $3$
   $6$	close subproof, 1	$G(a)$	$\exists$E $2$, $3$–$5$
   $7$	close subproof, 0	$\exists xF(x)\to G(a)$	$\to$I $2$–$6$

   Line number	Subproof level	Formula	Justification
   $1$	0	$\exists xF(x)\to G(a)$
   $2$	open subproof, 1	$F(b)$
   $3$	1	$\exists xF(x)$	$\exists$I $2$
   $4$	1	$G(a)$	$\to$E $1$, $3$
   $5$	close subproof, 0	$F(b)\to G(a)$	$\to$I $2$–$4$
   $6$	0	$\forall x(F(x)\to G(a))$	$\forall$I $5$

5. 5.
   ​

   $\exists x(G(a)\to F(x)),G(a)\to \exists xF(x)$

   Line number	Subproof level	Formula	Justification
   $1$	0	$\exists x(G(a)\to F(x))$
   $2$	open subproof, 1	$G(a)$
   $3$	open subproof, 2	$G(a)\to F(b)$
   $4$	2	$F(b)$	$\to$E $3$, $2$
   $5$	2	$\exists xF(x)$	$\exists$I $4$
   $6$	close subproof, 1	$\exists xF(x)$	$\exists$E $1$, $3$–$5$
   $7$	close subproof, 0	$G(a)\to \exists xF(x)$	$\to$I $2$–$6$

   Line number	Subproof level	Formula	Justification
   $1$	0	$G(a)\to \exists xF(x)$
   $2$	open subproof, 1	$G(a)$
   $3$	1	$\exists xF(x)$
   $4$	open subproof, 2	$F(b)$
   $5$	open subproof, 3	$G(a)$
   $6$	3	$F(b)$	R $4$
   $7$	close subproof, 2	$G(a)\to F(b)$	$\to$I $5$–$6$
   $8$	2	$\exists x(G(a)\to F(x))$	$\exists$I $7$
   $9$	close subproof, 1	$\exists x(G(a)\to F(x))$	$\exists$E $3$, $4$–$8$
   $10$	close subproof, open subproof, 1	$\neg G(a)$
   $11$	open subproof, 2	$G(a)$
   $12$	2	$\perp$	$\neg$E $11$, $10$
   $13$	2	$F(b)$	X $12$
   $14$	close subproof, 1	$G(a)\to F(b)$	$\to$E $11$–$13$
   $15$	1	$\exists x(G(a)\to F(x))$	$\exists$I $14$
   $16$	close subproof, 0	$\exists x(G(a)\to F(x))$	LEM $2$–$9$, $10$–$15$

6. 6.
   ​

   $\exists x(F(x)\to G(a)),\forall xF(x)\to G(a)$

   Line number	Subproof level	Formula	Justification
   $1$	0	$\exists x(F(x)\to G(a))$
   $2$	open subproof, 1	$\forall xF(x)$
   $3$	open subproof, 2	$F(b)\to G(a)$
   $4$	2	$F(b)$	$\forall$E $2$
   $5$	2	$G(a)$	$\to$E $3$, $4$
   $6$	close subproof, 1	$G(a)$	$\exists$E $1$, $3$–$5$
   $7$	close subproof, 0	$\forall xF(x)\to G(a)$	$\to$I $2$–$6$

   Line number	Subproof level	Formula	Justification
   $1$	0	$\forall xF(x)\to G(a)$
   $2$	open subproof, 1	$\forall xF(x)$
   $3$	1	$G(a)$	$\to$E $1$, $2$
   $4$	open subproof, 2	$F(b)$
   $5$	2	$G(a)$	R $3$
   $6$	close subproof, 1	$F(b)\to G(a)$	$\to$I $4$–$5$
   $7$	1	$\exists x(F(x)\to G(a))$	$\exists$I $6$
   $8$	close subproof, open subproof, 1	$\neg \forall xF(x)$
   $9$	1	$\exists x\neg F(x)$	CQ $8$
   $10$	open subproof, 2	$\neg F(b)$
   $11$	open subproof, 3	$F(b)$
   $12$	3	$\perp$	$\neg$E $11$, $10$
   $13$	3	$G(a)$	X $12$
   $14$	close subproof, 2	$F(b)\to G(a)$	$\to$I $11$–$13$
   $15$	2	$\exists x(F(x)\to G(a))$	$\exists$I $14$
   $16$	close subproof, 1	$\exists x(F(x)\to G(a))$	$\exists$E $9$, $10$–$15$
   $17$	close subproof, 0	$\exists x(F(x)\to G(a))$	LEM $2$–$7$, $8$–$16$