Solutions to Chapter 36 Basic rules for FOL

A. Explain why these two ‘proofs’ are incorrect. Also, provide interpretations which would invalidate the fallacious argument forms the ‘proofs’ enshrine:

When using $\forall$I, you must replace all names with the new variable. So line 3 is bogus. As a counterinterpretation, consider the following:

The instantiating constant, ‘$a$’, occurs in the line (line 2) to which $\exists$E is to be applied on line 5. So the use of $\exists$E on line 5 is bogus. As a counterinterpretation, consider the following:

B. The following three proofs are missing their citations (rule and line numbers). Add them, to turn them into bona fide proofs.

1. 1.

   Line number	Subproof level	Formula	Justification
   1	0	$\forall x\exists y(R(x,y)\vee R(y,x))$
   2	0	$\forall x\neg R(m,x)$
   3	0	$\exists y(R(m,y)\vee R(y,m))$	$\forall$E 1
   4	open subproof, 1	$R(m,a)\vee R(a,m)$
   5	1	$\neg R(m,a)$	$\forall$E 2
   6	1	$R(a,m)$	DS 4, 5
   7	1	$\exists xR(x,m)$	$\exists$I 6
   8	close subproof, 0	$\exists xR(x,m)$	$\exists$E 3, 4–7

2. 2.

   Line number	Subproof level	Formula	Justification
   1	0	$\forall x(\exists yL(x,y)\to \forall zL(z,x))$
   2	0	$L(a,b)$
   3	0	$\exists yL(a,y)\to \forall zL(z,a)$	$\forall$E 1
   4	0	$\exists yL(a,y)$	$\exists$I 2
   5	0	$\forall zL(z,a)$	$\to$E 3, 4
   6	0	$L(c,a)$	$\forall$E 5
   7	0	$\exists yL(c,y)\to \forall zL(z,c)$	$\forall$E 1
   8	0	$\exists yL(c,y)$	$\exists$I 6
   9	0	$\forall zL(z,c)$	$\to$E 7, 8
   10	0	$L(c,c)$	$\forall$E 9
   11	0	$\forall xL(x,x)$	$\forall$I 10

3. 3.

   Line number	Subproof level	Formula	Justification
   1	0	$\forall x(J(x)\to K(x))$
   2	0	$\exists x\forall yL(x,y)$
   3	0	$\forall xJ(x)$
   4	open subproof, 1	$\forall yL(a,y)$
   5	1	$L(a,a)$	$\forall$E 4
   6	1	$J(a)$	$\forall$E 3
   7	1	$J(a)\to K(a)$	$\forall$E 1
   8	1	$K(a)$	$\to$E 7, 6
   9	1	$K(a)\wedge L(a,a)$	$\wedge$I 8, 5
   10	1	$\exists x(K(x)\wedge L(x,x))$	$\exists$I 9
   11	close subproof, 0	$\exists x(K(x)\wedge L(x,x))$	$\exists$E 2, 4–10

C. In exercise 24A, we considered fifteen syllogistic figures of Aristotelian logic. Provide proofs for each of the argument forms. NB: You will find it much easier if you symbolize (for example) ‘No F is G’ as ‘$\forall x(F(x)\to \neg G(x))$’.
We prove the four Figure I syllogisms; the rest are extremely similar.

1. 1.
   ​

   Barbara

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

2. 2.
   ​

   Celerant is exactly as Barbara, replacing ‘$F$’ with ‘$\neg F$’ throughout.

3. 3.
   ​

   Ferio

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

4. 4.
   ​

   Darii is exactly as Ferio, replacing ‘$\neg F$’ with ‘$F$’ throughout.

D. Aristotle and his successors identified other syllogistic forms which depended upon ‘existential import’. Symbolize each of the following argument forms in FOL and offer proofs.

1. 1.
   ​

   Barbari. Something is H. All G are F. All H are G. So: Some H is F
   $\exists xH(x),\forall x(G(x)\to F(x)),\forall x(H(x)\to G(x))\therefore \exists x(H(x)\wedge F(x))$

   Line number	Subproof level	Formula	Justification
   1	0	$\exists xH(x)$
   2	0	$\forall x(G(x)\to F(x))$
   3	0	$\forall x(H(x)\to G(x))$
   4	open subproof, 1	$H(a)$
   5	1	$H(a)\to G(a)$	$\forall$E 3
   6	1	$G(a)$	$\to$E 5, 4
   7	1	$G(a)\to F(a)$	$\forall$E 2
   8	1	$F(a)$	$\to$E 7, 6
   9	1	$H(a)\wedge F(a)$	$\wedge$I 4, 8
   10	1	$\exists x(H(x)\wedge F(x))$	$\exists$I 9
   11	close subproof, 0	$\exists x(H(x)\wedge F(x))$	$\exists$E 1, 4–10

2. 2.
   ​

   Celaront. Something is H. No G are F. All H are G. So: Some H is not F
   $\exists xH(x),\forall x(G(x)\to \neg F(x)),\forall x(H(x)\to G(x))\therefore \exists x(H(x)\wedge \neg F(x))$
   Proof is exactly as for Barbari, replacing ‘$F$’ with ‘$\neg F$’ throughout.

3. 3.
   ​

   Cesaro. Something is H. No F are G. All H are G. So: Some H is not F.
   $\exists xH(x),\forall x(F(x)\to \neg G(x)),\forall x(H(x)\to G(x))\therefore \exists x(H(x)\wedge \neg F(x))$

   Line number	Subproof level	Formula	Justification
   1	0	$\exists xH(x)$
   2	0	$\forall x(F(x)\to \neg G(x))$
   3	0	$\forall x(H(x)\to G(x))$
   4	open subproof, 1	$H(a)$
   5	1	$H(a)\to G(a)$	$\forall$E 3
   6	1	$G(a)$	$\to$E 5, 4
   7	1	$F(a)\to \neg G(a)$	$\forall$E 2
   8	open subproof, 2	$F(a)$
   9	2	$\neg G(a)$	$\to$E 7, 8
   10	2	$\perp$	$\neg$E 6, 9
   11	close subproof, 1	$\neg F(a)$	$\neg$I 8–10
   12	1	$H(a)\wedge \neg F(a)$	$\wedge$I 4, 11
   13	1	$\exists x(H(x)\wedge \neg F(x))$	$\exists$I 12
   14	close subproof, 0	$\exists x(H(x)\wedge \neg F(x))$	$\exists$E 1, 4–13
4. 4.
   ​

   Camestros. Something is H. All F are G. No H are G. So: Some H is not F.
   $\exists xH(x),\forall x(F(x)\to G(x)),\forall x(H(x)\to \neg G(x))\therefore \exists x(H(x)\wedge \neg F(x))$

   Line number	Subproof level	Formula	Justification
   1	0	$\exists xH(x)$
   2	0	$\forall x(F(x)\to G(x))$
   3	0	$\forall x(H(x)\to \neg G(x))$
   4	open subproof, 1	$H(a)$
   5	1	$H(a)\to \neg G(a)$	$\forall$E 3
   6	1	$\neg G(a)$	$\to$E 5, 4
   7	1	$F(a)\to G(a)$	$\forall$E 2
   8	1	$\neg F(a)$	MT 7, 6
   9	1	$H(a)\wedge \neg F(a)$	$\wedge$I 4, 8
   10	1	$\exists x(H(x)\wedge \neg F(x))$	$\exists$I 9
   11	close subproof, 0	$\exists x(H(x)\wedge \neg F(x))$	$\exists$E 1, 4–10

5. 5.
   ​

   Felapton. Something is G. No G are F. All G are H. So: Some H is not F.
   $\exists xG(x),\forall x(G(x)\to \neg F(x)),\forall x(G(x)\to H(x))\therefore \exists x(H(x)\wedge \neg F(x))$

   Line number	Subproof level	Formula	Justification
   1	0	$\exists xG(x)$
   2	0	$\forall x(G(x)\to \neg F(x))$
   3	0	$\forall x(G(x)\to H(x))$
   4	open subproof, 1	$G(a)$
   5	1	$G(a)\to H(a)$	$\forall$E 3
   6	1	$H(a)$	$\to$E 5, 4
   7	1	$G(a)\to \neg F(a)$	$\forall$E 2
   8	1	$\neg F(a)$	$\to$E 7, 4
   9	1	$H(a)\wedge \neg F(a)$	$\wedge$I 6, 8
   10	1	$\exists x(H(x)\wedge \neg F(x))$	$\exists$I 9
   11	close subproof, 0	$\exists x(H(x)\wedge F(x))$	$\exists$E 1, 4–10

6. 6.
   ​

   Darapti. Something is G. All G are F. All G are H. So: Some H is F.
   $\exists xG(x),\forall x(G(x)\to F(x)),\forall x(G(x)\to H(x))\therefore \exists x(H(x)\wedge F(x))$
   Proof is exactly as for Felapton, replacing ‘$\neg F$’ with ‘$F$’ throughout.
7. 7.
   ​

   Calemos. Something is H. All F are G. No G are H. So: Some H is not F.
   $\exists xH(x),\forall x(F(x)\to G(x)),\forall x(G(x)\to \neg H(x))\therefore \exists x(H(x)\wedge \neg F(x))$

   Line number	Subproof level	Formula	Justification
   1	0	$\exists xH(x)$
   2	0	$\forall x(F(x)\to G(x))$
   3	0	$\forall x(G(x)\to \neg H(x))$
   4	open subproof, 1	$H(a)$
   5	1	$G(a)\to \neg H(a)$	$\forall$E 3
   6	open subproof, 2	$G(a)$
   7	2	$\neg H(a)$	$\to$E 5, 6
   8	2	$\perp$	$\neg$E 4, 7
   9	close subproof, 1	$\neg G(a)$	$\neg$I 6–8
   10	1	$F(a)\to G(a)$	$\forall$E 2
   11	1	$\neg F(a)$	MT 10, 9
   12	1	$H(a)\wedge \neg F(a)$	$\wedge$I 4, 11
   13	1	$\exists x(H(x)\wedge F(x))$	$\exists$I 12
   14	close subproof, 0	$\exists x(H(x)\wedge F(x))$	$\exists$E 1, 4–13

8. 8.
   ​

   Fesapo. Something is G. No F is G. All G are H. So: Some H is not F.
   $\exists xG(x),\forall x(F(x)\to \neg G(x)),\forall x(G(x)\to H(x))\therefore \exists x(H(x)\wedge \neg F(x))$

   Line number	Subproof level	Formula	Justification
   1	0	$\exists xG(x)$
   2	0	$\forall x(F(x)\to \neg G(x))$
   3	0	$\forall x(G(x)\to H(x))$
   4	open subproof, 1	$G(a)$
   5	1	$G(a)\to H(a)$	$\forall$E 3
   6	1	$H(a)$	$\to$E 5, 4
   7	1	$F(a)\to \neg G(a)$	$\forall$E 2
   8	open subproof, 2	$F(a)$
   9	2	$\neg G(a)$	$\to$E 7, 8
   10	2	$\perp$	$\neg$E 4, 9
   11	close subproof, 1	$\neg F(a)$	$\neg$I 8–10
   12	1	$H(a)\wedge \neg F(a)$	$\wedge$I 6, 11
   13	1	$\exists x(H(x)\wedge \neg F(x))$	$\exists$I 12
   14	close subproof, 0	$\exists x(H(x)\wedge \neg F(x))$	$\exists$E 1, 4–13
9. 9.
   ​

   Bamalip. Something is F. All F are G. All G are H. So: Some H are F.
   $\exists xF(x),\forall x(F(x)\to G(x)),\forall x(G(x)\to H(x))\therefore \exists x(H(x)\wedge F(x))$

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

E. For each of the following claims, provide an FOL proof that shows it is true.

1. 1.
   ​

   $⊢\forall xF(x)\to \forall y(F(y)\wedge F(y))$

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

2. 2.
   ​

   $\forall x(Ax\to B(x)),\exists xA(x)⊢\exists xB(x)$

   Line number	Subproof level	Formula	Justification
   1	0	$\forall x(A(x)\to B(x))$
   2	0	$\exists xA(x)$
   3	open subproof, 1	$A(a)$
   4	1	$A(a)\to B(a)$	$\forall$E 1
   5	1	$B(a)$	$\to$E 4, 3
   6	1	$\exists xB(x)$	$\exists$I 5
   7	close subproof, 0	$\exists xB(x)$	$\exists$E 2, 3–6
3. 3.
   ​

   $\forall x(M(x)\leftrightarrow N(x)),M(a)\wedge \exists xR(x,a)⊢\exists xN(x)$

   Line number	Subproof level	Formula	Justification
   1	0	$\forall x(M(x)\leftrightarrow N(x))$
   2	0	$M(a)\wedge \exists xR(x,a)$
   3	0	$M(a)$	$\wedge$E 2
   4	0	$M(a)\leftrightarrow N(a)$	$\forall$E 1
   5	0	$N(a)$	$\leftrightarrow$E 4, 3
   6	0	$\exists xN(x)$	$\exists$I 5

4. 4.
   ​

   $\forall x\forall yG(x,y)⊢\exists xG(x,x)$

   Line number	Subproof level	Formula	Justification
   1	0	$\forall x\forall yG(x,y)$
   2	0	$\forall yG(a,y)$	$\forall$E 1
   3	0	$G(a,a)$	$\forall$E 2
   4	0	$\exists xG(x,x)$	$\exists$I 3

5. 5.
   ​

   $⊢\forall xR(x,x)\to \exists x\exists yR(x,y)$

   Line number	Subproof level	Formula	Justification
   1	open subproof, 1	$\forall xR(x,x)$
   2	1	$R(a,a)$	$\forall$E 1
   3	1	$\exists yR(a,y)$	$\exists$I 2
   4	1	$\exists x\exists yR(x,y)$	$\exists$I 3
   5	close subproof, 0	$\forall xR(x,x)\to \exists x\exists yR(x,y)$	$\to$I 1–4

6. 6.
   ​

   $⊢\forall y\exists x(Q(y)\to Q(x))$

   Line number	Subproof level	Formula	Justification
   1	open subproof, 1	$Q(a)$
   2	1	$Q(a)$	R 1
   3	close subproof, 0	$Q(a)\to Q(a)$	$\to$I 1–2
   4	0	$\exists x(Q(a)\to Q(x))$	$\exists$I 3
   5	0	$\forall y\exists x(Q(y)\to Q(x))$	$\forall$I 4

7. 7.
   ​

   $N(a)\to \forall x(M(x)\leftrightarrow M(a)),M(a),\neg M(b)⊢\neg N(a)$

   Line number	Subproof level	Formula	Justification
   1	0	$N(a)\to \forall x(M(x)\leftrightarrow M(a))$
   2	0	$M(a)$
   3	0	$\neg M(b)$
   4	open subproof, 1	$N(a)$
   5	1	$\forall x(M(x)\leftrightarrow M(a))$	$\to$E 1, 4
   6	1	$M(b)\leftrightarrow M(a)$	$\forall$E 5
   7	1	$M(b)$	$\leftrightarrow$E 6, 2
   8	1	$\perp$	$\neg$E 7, 3
   9	close subproof, 0	$\neg N(a)$	$\neg$I 4–8
8. 8.
   ​

   $\forall x\forall y(G(x,y)\to G(y,x))⊢\forall x\forall y(G(x,y)\leftrightarrow G(y,x))$

   Line number	Subproof level	Formula	Justification
   1	0	$\forall x\forall y(G(x,y)\to G(y,x))$
   2	open subproof, 1	$G(a,b)$
   3	1	$\forall y(G(a,y)\to G(y,a))$	$\forall$E 1
   4	1	$G(a,b)\to G(b,a)$	$\forall$E 3
   5	1	$G(b,a)$	$\to$E 4, 2
   6	close subproof, open subproof, 1	$G(b,a)$
   7	1	$\forall y(G(b,y)\to G(y,b))$	$\forall$E 1
   8	1	$G(b,a)\to G(a,b)$	$\forall$E 7
   9	1	$G(a,b)$	$\to$E 8, 6
   10	close subproof, 0	$G(a,b)\leftrightarrow G(b,a)$	$\leftrightarrow$I 2–5, 6–9
   11	0	$\forall y(G(a,y)\leftrightarrow G(y,a))$	$\forall$I 10
   12	0	$\forall x\forall y(G(x,y)\leftrightarrow G(y,x))$	$\forall$I 11

9. 9.
   ​

   $\forall x(\neg M(x)\vee L(j,x)),\forall x(B(x)\to L(j,x)),\forall x(M(x)\vee B(x))⊢\forall xL(j,x)$

   Line number	Subproof level	Formula	Justification
   1	0	$\forall x(\neg M(x)\vee L(j,x))$
   2	0	$\forall x(B(x)\to L(j,x))$
   3	0	$\forall x(M(x)\vee B(x))$
   4	0	$\neg M(a)\vee L(j,x)$	$\forall$E 1
   5	0	$B(a)\to L(j,a)$	$\forall$E 2
   6	0	$M(a)\vee B(a)$	$\forall$E 3
   7	open subproof, 1	$\neg M(a)$
   8	1	$B(a)$	DS 6, 7
   9	1	$L(j,a)$	$\to$E 5, 8
   10	close subproof, open subproof, 1	$L(j,a)$
   11	1	$L(j,a)$	R 10
   12	close subproof, 0	$L(j,a)$	$\vee$E 4, 7–9, 10–11
   13	0	$\forall xL(j,x)$	$\forall$I 12