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