Solutions to Chapter 36 Basic rules for FOL ‣ Solutions to selected exercices ‣ forall x: Calgary

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

Line number	Formula	Justification
$1$	$\forall x\,R(x,x)$
$2$	$R(a,a)$	$\forall$ E $1$
$3$	$\forall y\,R(a,y)$	$\forall$ I $2$
$4$	$\forall x\forall y\,R(x,y)$	$\forall$ I $3$

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

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

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.

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 x\,R(x,m)$	$\exists$ I $6$
$8$	close subproof, 0	$\exists x\,R(x,m)$	$\exists$ E $3$ , $4$ – $7$

2.

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

3.

Line number	Subproof level	Formula	Justification
$1$	0	$\forall x(J(x)\rightarrow K(x))$
$2$	0	$\exists x\forall y\,L(x,y)$
$3$	0	$\forall x\,J(x)$
$4$	open subproof, 1	$\forall y\,L(a,y)$
$5$	1	$L(a,a)$	$\forall$ E $4$
$6$	1	$J(a)$	$\forall$ E $3$
$7$	1	$J(a)\rightarrow K(a)$	$\forall$ E $1$
$8$	1	$K(a)$	$\rightarrow$ 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)\rightarrow\neg G(x))$ ’.
We prove the four Figure I syllogisms; the rest are extremely similar.

1.

Barbara

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

2.

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

3.

Ferio

Line number	Subproof level	Formula	Justification
$1$	0	$\forall x(G(x)\rightarrow\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)\rightarrow\neg F(a)$	$\forall$ E $1$
$7$	1	$\neg F(a)$	$\rightarrow$ 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.

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.

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

Line number	Subproof level	Formula	Justification
$1$	0	$\exists x\,H(x)$
$2$	0	$\forall x(G(x)\rightarrow F(x))$
$3$	0	$\forall x(H(x)\rightarrow G(x))$
$4$	open subproof, 1	$H(a)$
$5$	1	$H(a)\rightarrow G(a)$	$\forall$ E $3$
$6$	1	$G(a)$	$\rightarrow$ E $5$ , $4$
$7$	1	$G(a)\rightarrow F(a)$	$\forall$ E $2$
$8$	1	$F(a)$	$\rightarrow$ 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.

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

3.

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

Line number	Subproof level	Formula	Justification
$1$	0	$\exists x\,H(x)$
$2$	0	$\forall x(F(x)\rightarrow\neg G(x))$
$3$	0	$\forall x(H(x)\rightarrow G(x))$
$4$	open subproof, 1	$H(a)$
$5$	1	$H(a)\rightarrow G(a)$	$\forall$ E $3$
$6$	1	$G(a)$	$\rightarrow$ E $5$ , $4$
$7$	1	$F(a)\rightarrow\neg G(a)$	$\forall$ E $2$
$8$	open subproof, 2	$F(a)$
$9$	2	$\neg G(a)$	$\rightarrow$ E $7$ , $8$
$10$	2	$\bot$	$\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.

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

Line number	Subproof level	Formula	Justification
$1$	0	$\exists x\,H(x)$
$2$	0	$\forall x(F(x)\rightarrow G(x))$
$3$	0	$\forall x(H(x)\rightarrow\neg G(x))$
$4$	open subproof, 1	$H(a)$
$5$	1	$H(a)\rightarrow\neg G(a)$	$\forall$ E $3$
$6$	1	$\neg G(a)$	$\rightarrow$ E $5$ , $4$
$7$	1	$F(a)\rightarrow 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.

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

Line number	Subproof level	Formula	Justification
$1$	0	$\exists x\,G(x)$
$2$	0	$\forall x(G(x)\rightarrow\neg F(x))$
$3$	0	$\forall x(G(x)\rightarrow H(x))$
$4$	open subproof, 1	$G(a)$
$5$	1	$G(a)\rightarrow H(a)$	$\forall$ E $3$
$6$	1	$H(a)$	$\rightarrow$ E $5$ , $4$
$7$	1	$G(a)\rightarrow\neg F(a)$	$\forall$ E $2$
$8$	1	$\neg F(a)$	$\rightarrow$ 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.

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

7.

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

Line number	Subproof level	Formula	Justification
$1$	0	$\exists x\,H(x)$
$2$	0	$\forall x(F(x)\rightarrow G(x))$
$3$	0	$\forall x(G(x)\rightarrow\neg H(x))$
$4$	open subproof, 1	$H(a)$
$5$	1	$G(a)\rightarrow\neg H(a)$	$\forall$ E $3$
$6$	open subproof, 2	$G(a)$
$7$	2	$\neg H(a)$	$\rightarrow$ E $5$ , $6$
$8$	2	$\bot$	$\neg$ E $4$ , $7$
$9$	close subproof, 1	$\neg G(a)$	$\neg$ I $6$ – $8$
$10$	1	$F(a)\rightarrow 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.

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

Line number	Subproof level	Formula	Justification
$1$	0	$\exists x\,G(x)$
$2$	0	$\forall x(F(x)\rightarrow\neg G(x))$
$3$	0	$\forall x(G(x)\rightarrow H(x))$
$4$	open subproof, 1	$G(a)$
$5$	1	$G(a)\rightarrow H(a)$	$\forall$ E $3$
$6$	1	$H(a)$	$\rightarrow$ E $5$ , $4$
$7$	1	$F(a)\rightarrow\neg G(a)$	$\forall$ E $2$
$8$	open subproof, 2	$F(a)$
$9$	2	$\neg G(a)$	$\rightarrow$ E $7$ , $8$
$10$	2	$\bot$	$\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.

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

Line number	Subproof level	Formula	Justification
$1$	0	$\exists x\,F(x)$
$2$	0	$\forall x(F(x)\rightarrow G(x))$
$3$	0	$\forall x(G(x)\rightarrow H(x))$
$4$	open subproof, 1	$F(a)$
$5$	1	$F(a)\rightarrow G(a)$	$\forall$ E $2$
$6$	1	$G(a)$	$\rightarrow$ E $5$ , $4$
$7$	1	$G(a)\rightarrow H(a)$	$\forall$ E $3$
$8$	1	$H(a)$	$\rightarrow$ 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.

$\vdash\forall x\,F(x)\rightarrow\forall y(F(y)\wedge F(y))$

Line number	Subproof level	Formula	Justification
$1$	open subproof, 1	$\forall x\,F(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 x\,F(x)\rightarrow\forall y(F(x)\wedge F(x))$	$\rightarrow$ I $1$ – $4$

2.

$\forall x(Ax\rightarrow B(x)),\exists x\,A(x)\vdash\exists x\,B(x)$

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

3.

$\forall x(M(x)\leftrightarrow N(x)),M(a)\wedge\exists x\,R(x,a)\vdash\exists x% \,N(x)$

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

4.

$\forall x\forall y\,G(x,y)\vdash\exists x\,G(x,x)$

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

5.

$\vdash\forall x\,R(x,x)\rightarrow\exists x\exists y\,R(x,y)$

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

6.

$\vdash\forall y\exists x(Q(y)\rightarrow 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)\rightarrow Q(a)$	$\rightarrow$ I $1$ – $2$
$4$	0	$\exists x(Q(a)\rightarrow Q(x))$	$\exists$ I $3$
$5$	0	$\forall y\exists x(Q(y)\rightarrow Q(x))$	$\forall$ I $4$

7.

$N(a)\rightarrow\forall x(M(x)\leftrightarrow M(a)),M(a),\neg M(b)\vdash\neg N(a)$

Line number	Subproof level	Formula	Justification
$1$	0	$N(a)\rightarrow\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))$	$\rightarrow$ E $1$ , $4$
$6$	1	$M(b)\leftrightarrow M(a)$	$\forall$ E $5$
$7$	1	$M(b)$	$\leftrightarrow$ E $6$ , $2$
$8$	1	$\bot$	$\neg$ E $7$ , $3$
$9$	close subproof, 0	$\neg N(a)$	$\neg$ I $4$ – $8$

8.

$\forall x\forall y(G(x,y)\rightarrow G(y,x))\vdash\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)\rightarrow G(y,x))$
$2$	open subproof, 1	$G(a,b)$
$3$	1	$\forall y(G(a,y)\rightarrow G(y,a))$	$\forall$ E $1$
$4$	1	$G(a,b)\rightarrow G(b,a)$	$\forall$ E $3$
$5$	1	$G(b,a)$	$\rightarrow$ E $4$ , $2$
$6$	close subproof, open subproof, 1	$G(b,a)$
$7$	1	$\forall y(G(b,y)\rightarrow G(y,b))$	$\forall$ E $1$
$8$	1	$G(b,a)\rightarrow G(a,b)$	$\forall$ E $7$
$9$	1	$G(a,b)$	$\rightarrow$ 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.

$\forall x(\neg M(x)\vee L(j,x)),\forall x(B(x)\rightarrow L(j,x)),\forall x(M(% x)\vee B(x))\vdash\forall x\,L(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)\rightarrow 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)\rightarrow 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)$	$\rightarrow$ 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 x\,L(j,x)$	$\forall$ I $12$

F. Write a symbolization key for the following argument, symbolize it, and prove it:

There is someone who likes everyone who likes everyone that she likes.
∴

There is someone who likes herself.

Symbolization key:

domain:: all people
$L(x,y)$ :: blank _x likes blank _y

$\exists x\forall y(\forall z(L(x,z)\rightarrow L(y,z))\rightarrow L(x,y))% \therefore\exists x\,L(x,x)$

Line number	Subproof level	Formula	Justification
$1$	0	$\exists x\forall y(\forall z(L(x,z)\rightarrow L(y,z))\rightarrow L(x,y))$
$2$	open subproof, 1	$\forall y(\forall z(L(a,z)\rightarrow L(y,z))\rightarrow L(a,y))$
$3$	1	$\forall z(L(a,z)\rightarrow L(a,z))\rightarrow L(a,a)$	$\forall$ E $2$
$4$	open subproof, 2	$L(a,c)$
$5$	2	$L(a,c)$	R $4$
$6$	close subproof, 1	$L(a,c)\rightarrow L(a,c)$	$\rightarrow$ I $4$ – $5$
$7$	1	$\forall z(L(a,z)\rightarrow L(a,z))$	$\forall$ I $6$
$8$	1	$L(a,a)$	$\rightarrow$ E $3$ , $7$
$9$	1	$\exists x\,L(x,x)$	$\exists$ I $8$
$10$	close subproof, 0	$\exists x\,L(x,x)$	$\exists$ E $1$ , $2$ –– $9$

G. Show that each pair of sentences is interderivable.

1.

$\forall x(A(x)\rightarrow\neg B(x))$ , $\neg\exists x(A(x)\wedge B(x))$
2.

$\forall x(\neg A(x)\rightarrow B(d))$ , $\forall x\,A(x)\vee B(d)$
3.

$\exists x\,P(x)\rightarrow Q(c)$ , $\forall x(P(x)\rightarrow Q(c))$

H. For each of the following pairs of sentences: If they are interderivable, give proofs to show this. If they are not, construct an interpretation to show that they are not logically equivalent.

1.

$\forall x\,P(x)\rightarrow Q(c),\forall x(P(x)\rightarrow Q(c))$ Not logically equivalent
Counter-interpretation: let the domain be the numbers $1$ and $2$ . Let ‘ $c$ ’ name $1$ . Let ‘ $P(x)$ ’ be true of and only of $1$ . Let ‘ $Q(x)$ ’ be true of, and only of, $2$ .
2.

$\forall x\forall y\forall zB(x,y,z),\forall x\,B(x,x,x)$ Not logically equivalent
Counter-interpretation: let the domain be the numbers $1$ and $2$ . Let ‘ $B(x,y,z)$ ’ be true of, and only of, $\mathopen{\langle}$ 1,1,1 $\mathclose{\rangle}$ and $\mathopen{\langle}$ 2,2,2 $\mathclose{\rangle}$ .

3.

$\forall x\forall y\,D(x,y),\forall y\forall x\,D(x,y)$ interderivable

Line number	Formula	Justification
$1$	$\forall x\forall y\,D(x,y)$
$2$	$\forall y\,D(a,y)$	$\forall$ E $1$
$3$	$D(a,b)$	$\forall$ E $2$
$4$	$\forall x\,D(x,b)$	$\forall$ I $3$
$5$	$\forall y\forall x\,D(x,y)$	$\forall$ I $4$

Line number	Formula	Justification
$1$	$\forall y\forall x\,D(x,y)$
$2$	$\forall x\,D(x,a)$	$\forall$ E $1$
$3$	$D(b,a)$	$\forall$ E $2$
$4$	$\forall y\,D(b,y)$	$\forall$ I $3$
$5$	$\forall x\forall y\,D(x,y)$	$\forall$ I $4$

4.

$\exists x\forall y\,D(x,y),\forall y\exists x\,D(x,y)$ Not logically equivalent
Counter-interpretation: let the domain be the numbers $1$ and $2$ . Let ‘ $D x y$ ’ hold of and only of $\mathopen{\langle}$ 1,2 $\mathclose{\rangle}$ and $\mathopen{\langle}$ 2,1 $\mathclose{\rangle}$ . This is depicted thus:
5.

$\forall x(R(c,a)\leftrightarrow R(x,a)),R(c,a)\leftrightarrow\forall x\,R(x,a)$ Not logically equivalent
Counter-interpretation: consider the following diagram, allowing ‘ $a$ ’ to name 1 and ‘ $c$ ’ to name 2:

I. For each of the following arguments: If it is valid in FOL, give a proof. If it is invalid, construct an interpretation to show that it is invalid.

1.

$\exists y\forall x\,R(x,y)\therefore\forall x\exists y\,R(x,y)$ Valid

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

2.

$\forall x\exists y\,R(x,y)\therefore\exists y\forall x\,R(x,y)$ Not valid
Counter interpretation: let the domain be the numbers $1$ and $2$ . Let ‘ $R x y$ ’ be true of $1$ and $2$ , and of $2$ and $1$ (but not $1$ and itself or $2$ and itself).
3.

$\exists x(P(x)\wedge\neg Q(x))\therefore\forall x(P(x)\rightarrow\neg Q(x))$ Not valid
Counter interpretation: let the domain be the numbers $1$ and $2$ . Let ‘ $P x$ ’ be true of everything in the domain. Let ‘ $Q x$ ’ be true of, and only of, $2$ .

4.

$\forall x(S(x)\rightarrow T(a)),S(d)\therefore T(a)$ Valid

Line number	Formula	Justification
$1$	$\forall x(S(x)\rightarrow T(a))$
$2$	$S(d)$
$3$	$S(d)\rightarrow T(a)$	$\forall$ E $1$
$4$	$T(a)$	$\rightarrow$ E $3$ , $2$

5.

$\forall x(Ax\rightarrow B(x)),\forall x(B(x)\rightarrow C(x))\therefore\forall x% (A(x)\rightarrow C(x))$ Valid

Line number	Subproof level	Formula	Justification
$1$	0	$\forall x(A(x)\rightarrow B(x))$
$2$	0	$\forall x(B(x)\rightarrow C(x))$
$3$	0	$A(a)\rightarrow B(a)$	$\forall$ E $1$
$4$	0	$B(a)\rightarrow C(a)$	$\forall$ E $2$
$5$	open subproof, 1	$A(a)$
$6$	1	$B(a)$	$\rightarrow$ E $3$ , $5$
$7$	1	$C(a)$	$\rightarrow$ E $4$ , $6$
$8$	close subproof, 0	$A(a)\rightarrow C(a)$	$\rightarrow$ I $5$ – $7$
$9$	0	$\forall x(A(x)\rightarrow C(x))$	$\forall$ I $8$

6.

$\exists x(D(x)\vee E(x)),\forall x(D(x)\rightarrow F(x))\therefore\exists x(D(% x)\wedge F(x))$ Invalid
Counter-interpretation: let the domain be the number $1$ . Let ‘ $D x$ ’ hold of nothing. Let both ‘ $E x$ ’ and ‘ $F x$ ’ hold of everything.

7.

$\forall x\forall y(R(x,y)\vee R(y,x))\therefore R(j,j)$ Valid

Line number	Subproof level	Formula	Justification
$1$	0	$\forall x\forall y(R(x,y)\vee R(y,x))$
$2$	0	$\forall y(R(j,y)\vee R(y,j))$	$\forall$ E $1$
$3$	0	$R(j,j)\vee R(j,j)$	$\forall$ E $2$
$4$	open subproof, 1	$R(j,j)$
$5$	1	$R(j,j)$	R $4$
$6$	close subproof, open subproof, 1	$R(j,j)$
$7$	1	$R(j,j)$	R $6$
$8$	close subproof, 0	$R(j,j)$	$\vee$ E $3$ , $4$ – $5$ , $6$ – $7$

8.

$\exists x\exists y(R(x,y)\vee R(y,x))\therefore R(j,j)$ Invalid
Counter-interpretation: consider the following diagram, allowing ‘ $j$ ’ to name $2$ .
9.

$\forall x\,P(x)\rightarrow\forall x\,Q(x),\exists x\neg P(x)\therefore\exists x% \neg Q(x)$ Invalid
Counter-interpretation: let the domain be the number $1$ . Let ‘ $P(x)$ ’ be true of nothing. Let ‘ $Q(x)$ ’ be true of everything.

10.

$\exists x\,M(x)\rightarrow\exists x\,N(x)$ , $\neg\exists x\,N(x)\therefore\forall x\neg M(x)$ Valid

Line number	Subproof level	Formula	Justification
$1$	0	$\exists x\,M(x)\rightarrow\exists x\,N(x)$
$2$	0	$\neg\exists x\,N(x)$
$3$	open subproof, 1	$M(a)$
$4$	1	$\exists x\,M(x)$	$\exists$ I $3$
$5$	1	$\exists x\,N(x)$	$\rightarrow$ E $1$ , $4$
$6$	1	$\bot$	$\neg$ E $5$ , $2$
$7$	close subproof, 0	$\neg M(a)$	$\neg$ I $3$ – $6$
$8$	0	$\forall x\neg M(x)$	$\forall$ I $7$