Solutions to Chapter 39 Rules for identity ‣ Solutions to selected exercices ‣ forall x: Calgary

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

1.

$P(a)\vee Q(b),Q(b)\rightarrow b=c,\neg P(a)\vdash Q(c)$

Line number	Formula	Justification
$1$	$P(a)\vee Q(b)$
$2$	$Q(b)\rightarrow b=c$
$3$	$\neg P(a)$
$4$	$Q(b)$	DS $1$ , $3$
$5$	$b=c$	$\rightarrow$ E $2$ , $4$
$6$	$Q(c)$	$=$ E $5$ , $4$

2.

$m=n\vee n=o,A(n)\vdash A(m)\vee A(o)$

Line number	Subproof level	Formula	Justification
$1$	0	$m=n\vee n=o$
$2$	0	$A(n)$
$3$	open subproof, 1	$m=n$
$4$	1	$A(m)$	$=$ E $3$ , $2$
$5$	1	$A(m)\vee A(o)$	$\vee$ I $4$
$6$	close subproof, open subproof, 1	$n=o$
$7$	1	$A(o)$	$=$ E $6$ , $7$
$8$	1	$A(m)\vee A(o)$	$\vee$ I $7$
$9$	close subproof, 0	$A(m)\vee A(o)$	$\vee$ E $1$ , $3$ – $5$ , $6$ – $8$

3.

$\forall x\ x=m,R(m,a)\vdash\exists x\,R(x,x)$

Line number	Formula	Justification
$1$	$\forall x\ x=m$
$2$	$R(m,a)$
$3$	$a=m$	$\forall$ E $1$
$4$	$R(a,a)$	$=$ E $3$ , $2$
$5$	$\exists x\,R(x,x)$	$\exists$ I $4$

4.

$\forall x\forall y(R(x,y)\rightarrow x=y)\vdash R(a,b)\rightarrow R(b,a)$

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

5.

$\neg\exists x\neg x=m\vdash\forall x\forall y(P(x)\rightarrow P(y))$

Line number	Subproof level	Formula	Justification
$1$	0	$\neg\exists x\neg x=m$
$2$	0	$\forall x\neg\neg x=m$	CQ $1$
$3$	0	$\neg\neg a=m$	$\forall$ E $2$
$4$	0	$a=m$	DNE $3$
$5$	0	$\neg\neg b=m$	$\forall$ E $2$
$6$	0	$b=m$	DNE $5$
$7$	open subproof, 1	$P(a)$
$8$	1	$P(m)$	$=$ E $3$ , $7$
$9$	1	$P(b)$	$=$ E $5$ , $8$
$10$	close subproof, 0	$P(a)\rightarrow P(b)$	$\rightarrow$ I $7$ – $9$
$11$	0	$\forall y(P(a)\rightarrow P(y))$	$\forall$ I $10$
$12$	0	$\forall x\forall y(P(x)\rightarrow P(y))$	$\forall$ I $11$

6.

$\exists x\,J(x),\exists x\neg J(x)\vdash\exists x\exists y\ \neg x=y$

Line number	Subproof level	Formula	Justification
$1$	0	$\exists x\,J(x)$
$2$	0	$\exists x\neg J(x)$
$3$	open subproof, 1	$J(a)$
$4$	open subproof, 2	$\neg J(b)$
$5$	open subproof, 3	$a=b$
$6$	3	$J(b)$	$=$ E $5$ , $3$
$7$	3	$\bot$	$\neg$ E $6$ , $4$
$8$	close subproof, 2	$\neg a=b$	$\neg$ I $5$ – $7$
$9$	2	$\exists y\neg a=y$	$\exists$ I $8$
$10$	2	$\exists x\exists y\neg x=y$	$\exists$ I $9$
$11$	close subproof, 1	$\exists x\exists y\neg x=y$	$\exists$ E $2$ , $4$ – $10$
$12$	close subproof, 0	$\exists x\exists y\neg x=y$	$\exists$ E $1$ , $3$ – $11$

7.

$\forall x(x=n\leftrightarrow M(x)),\forall x(O(x)\vee\neg M(x))\vdash O(n)$

Line number	Subproof level	Formula	Justification
$1$	0	$\forall x(x=n\leftrightarrow M(x))$
$2$	0	$\forall x(O(x)\vee\neg M(x))$
$3$	0	$n=n\leftrightarrow M(n)$	$\forall$ E $1$
$4$	0	$n=n$	$=$ I
$5$	0	$M(n)$	$\leftrightarrow$ E $3$ , $4$
$6$	0	$O(n)\vee\neg M(n)$	$\forall$ E $2$
$7$	open subproof, 1	$\neg O(n)$
$8$	1	$\neg M(n)$	DS $6$ , $7$
$9$	1	$\bot$	$\neg$ E $5$ , $8$
$10$	close subproof, 0	$\neg\neg O(n)$	$\neg$ I $7$ – $9$
$11$	0	$O(n)$	DNE $10$

8.

$\exists x\,D(x),\forall x(x=p\leftrightarrow D(x))\vdash D(p)$

Line number	Subproof level	Formula	Justification
$1$	0	$\exists x\,D(x)$
$2$	0	$\forall x(x=p\leftrightarrow D(x))$
$3$	open subproof, 1	$D(c)$
$4$	1	$c=p\leftrightarrow D(c)$	$\forall$ E $2$
$5$	1	$c=p$	$\leftrightarrow$ E $4$ , $3$
$6$	1	$D(p)$	$=$ E $5$ , $3$
$7$	close subproof, 0	$D(p)$	$\exists$ E $1$ , $3$ – $6$

9.

$\exists x\bigl{[}(K(x)\wedge\forall y(K(y)\rightarrow x=y))\wedge B(x)\bigr{]}% ,K(d)\vdash B(d)$

Line number	Subproof level	Formula	Justification
$1$	0	$\exists x\bigl{[}(K(x)\wedge\forall y(K(y)\rightarrow x=y)\wedge B(x)\bigr{]}$
$2$	0	$K(d)$
$3$	open subproof, 1	$(K(a)\wedge\forall y(K(y)\rightarrow a=y))\wedge B(a)$
$4$	1	$K(a)\wedge\forall y(K(y)\rightarrow a=y)$	$\wedge$ E $3$
$5$	1	$K(a)$	$\wedge$ E $4$
$6$	1	$\forall y(K(y)\rightarrow a=y)$	$\wedge$ E $4$
$7$	1	$K(d)\rightarrow a=d$	$\forall$ E $6$
$8$	1	$a=d$	$\rightarrow$ E $7$ , $2$
$9$	1	$B(a)$	$\wedge$ E $3$
$10$	1	$B(d)$	$=$ E $8$ , $9$
$11$	close subproof, 0	$B(d)$	$\exists$ E $1$ , $3$ – $10$

10.

$\vdash P(a)\rightarrow\forall x(P(x)\vee\neg x=a)$

Line number	Subproof level	Formula	Justification
$1$	open subproof, 1	$P(a)$
$2$	open subproof, 2	$b=a$
$3$	2	$P(b)$	$=$ E $2$ , $1$
$4$	2	$P(b)\vee\neg b=a$	$\vee$ I $3$
$5$	close subproof, open subproof, 2	$\neg b=a$
$6$	2	$P(b)\vee\neg b=a$	$\vee$ I $5$
$7$	close subproof, 1	$P(b)\vee\neg b=a$	LEM $2$ – $4$ , $5$ – $6$
$8$	1	$\forall x(P(x)\vee\neg x=a)$	$\forall$ I $7$
$9$	close subproof, 0	$P(a)\rightarrow\forall x(P(x)\vee\neg x=a)$	$\rightarrow$ I $1$ – $8$

B. Show that the following are interderivable:

‣

$\exists x\bigl{(}[F(x)\wedge\forall y(F(y)\rightarrow x=y)]\wedge x=n\bigr{)}$
‣

$F(n)\wedge\forall y(F(y)\rightarrow n=y)$

And hence that both have a decent claim to symbolize the English sentence ‘Nick is the F’.

In one direction:

Line number	Subproof level	Formula	Justification
$1$	0	$\exists x\bigl{(}[F(x)\wedge\forall y(F(y)\rightarrow x=y)]\wedge x=n\bigr{)}$
$2$	open subproof, 1	${}[F(a)\wedge\forall y(F(y)\rightarrow a=y)]\wedge a=n$
$3$	1	$a=n$	$\wedge$ E $2$
$4$	1	$F(a)\wedge\forall y(F(y)\rightarrow a=y)$	$\wedge$ E $2$
$5$	1	$F(a)$	$\wedge$ E $4$
$6$	1	$F(n)$	$=$ E $3$ , $5$
$7$	1	$\forall y(F(y)\rightarrow a=y)$	$\wedge$ E $4$
$8$	1	$\forall y(F(y)\rightarrow n=y)$	$=$ E $3$ , $7$
$9$	1	$F(n)\wedge\forall y(F(y)\rightarrow n=y)$	$\wedge$ I $6$ , $8$
$10$	close subproof, 0	$F(n)\wedge\forall y(F(y)\rightarrow n=y)$	$\exists$ E $1$ , $2$ – $9$

And now in the other:

Line number	Formula	Justification
$1$	$F(n)\wedge\forall y(F(y)\rightarrow n=y)$
$2$	$n=n$	$=$ I
$3$	${}[F(n)\wedge\forall y(F(y)\rightarrow n=y)]\wedge n=n$	$\wedge$ I $1$ , $2$
$4$	$\exists x\bigl{(}[F(x)\wedge\forall y(F(y)\rightarrow x=y)]\wedge x=n\bigr{)}$	$\exists$ I $3$

C. In appendix 26, we claimed that the following are logically equivalent symbolizations of the English sentence ‘there is exactly one F’:

‣

$\exists x\,F(x)\wedge\forall x\forall y\bigl{[}(F(x)\wedge F(y))\rightarrow x=% y\bigr{]}$
‣

$\exists x\bigl{[}F(x)\wedge\forall y(F(y)\rightarrow x=y)\bigr{]}$
‣

$\exists x\forall y(F(y)\leftrightarrow x=y)$

Show that they are all interderivable. (Hint: to show that three claims are interderivable, it suffices to show that the first proves the second, the second proves the third and the third proves the first; think about why.)
It suffices to show that the first proves the second, the second proves the third and the third proves the first, for we can then show that any of them prove any others, just by chaining the proofs together (numbering lines, where necessary. Armed with this, we start on the first proof:

Line number	Subproof level	Formula	Justification
$1$	0	$\exists x\,F(x)\wedge\forall x\forall y\bigl{[}(F(x)\wedge F(y))\rightarrow x=% y\bigr{]}$
$2$	0	$\exists x\,F(x)$	$\wedge$ E $1$
$3$	0	$\forall x\forall y\bigl{[}(F(x)\wedge F(y))\rightarrow x=y\bigr{]}$	$\wedge$ E $1$
$4$	open subproof, 1	$F(a)$
$5$	1	$\forall y\bigl{[}(F(a)\wedge F(y))\rightarrow a=y\bigr{]}$	$\forall$ E $3$
$6$	1	$(F(a)\wedge F(b))\rightarrow a=b$	$\forall$ E $5$
$7$	open subproof, 2	$F(b)$
$8$	2	$F(a)\wedge F(b)$	$\wedge$ I $4$ , $7$
$9$	2	$a=b$	$\rightarrow$ E $6$ , $8$
$10$	close subproof, 1	$F(b)\rightarrow a=b$	$\rightarrow$ I $7$ – $9$
$11$	1	$\forall y(F(y)\rightarrow a=y)$	$\forall$ I $10$
$12$	1	$F(a)\wedge\forall y(F(y)\rightarrow a=y))$	$\wedge$ I $4$ , $11$
$13$	1	$\exists x\bigl{[}F(x)\wedge\forall y(F(y)\rightarrow x=y)\bigr{]}$	$\exists$ I $12$
$14$	close subproof, 0	$\exists x\bigl{[}F(x)\wedge\forall y(F(y)\rightarrow x=y)\bigr{]}$	$\exists$ E $2$ , $4$ – $13$

Now for the second proof:

Line number	Subproof level	Formula	Justification
$1$	0	$\exists x\bigl{[}F(x)\wedge\forall y(F(y)\rightarrow x=y)\bigr{]}$
$2$	open subproof, 1	$F(a)\wedge\forall y(F(y)\rightarrow a=y)$
$3$	1	$F(a)$	$\wedge$ E $2$
$4$	1	$\forall y(F(y)\rightarrow a=y)$	$\wedge$ E $2$
$5$	open subproof, 2	$F(b)$
$6$	2	$F(b)\rightarrow a=b$	$\forall$ E $4$
$7$	2	$a=b$	$\rightarrow$ E $6$ , $5$
$8$	close subproof, open subproof, 2	$a=b$
$9$	2	$F(b)$	$=$ E $8$ , $3$
$10$	close subproof, 1	$F(b)\leftrightarrow a=b$	$\leftrightarrow$ I $5$ – $7$ , $8$ – $9$
$11$	1	$\forall y(F(y)\leftrightarrow a=y)$	$\forall$ I $10$
$12$	1	$\exists x\forall y(F(y)\leftrightarrow x=y)$	$\exists$ I $11$
$13$	close subproof, 0	$\exists x\forall y(F(y)\leftrightarrow x=y)$	$\exists$ E $1$ , $2$ – $12$

And finally, the third proof:

Line number	Subproof level	Formula	Justification
$1$	0	$\exists x\forall y(F(y)\leftrightarrow x=y)$
$2$	open subproof, 1	$\forall y(F(y)\leftrightarrow a=y)$
$3$	1	$F(a)\leftrightarrow a=a$	$\forall$ E $2$
$4$	1	$a=a$	$=$ I
$5$	1	$F(a)$	$\leftrightarrow$ E $3$ , $4$
$6$	1	$\exists x\,F(x)$	$\exists$ I $5$
$7$	open subproof, 2	$F(b)\wedge F(c)$
$8$	2	$F(b)$	$\wedge$ E $7$
$9$	2	$F(b)\leftrightarrow a=b$	$\forall$ E $2$
$10$	2	$a=b$	$\leftrightarrow$ E $9$ , $8$
$11$	2	$F(c)$	$\wedge$ E $7$
$12$	2	$F(c)\leftrightarrow a=c$	$\forall$ E $2$
$13$	2	$a=c$	$\leftrightarrow$ E $12$ , $11$
$14$	2	$b=c$	$=$ E $10$ , $13$
$15$	close subproof, 1	$(F(b)\wedge F(c))\rightarrow b=c$	$\rightarrow$ I $8$ – $14$
$16$	1	$\forall y\bigl{[}(F(b)\wedge F(y))\rightarrow b=y\bigr{]}$	$\forall$ I $15$
$17$	1	$\forall x\forall y\bigl{[}(F(x)\wedge F(y))\rightarrow x=y\bigr{]}$	$\forall$ I $16$
$18$	1	$\exists x\,F(x)\wedge\forall x\forall y\bigl{[}(F(x)\wedge F(y))\rightarrow x=% y\bigr{]}$	$\wedge$ I $6$ , $17$
$19$	close subproof, 0	$\exists x\,F(x)\wedge\forall x\forall y\bigl{[}(F(x)\wedge F(y))\rightarrow x=% y\bigr{]}$	$\exists$ E $1$ , $2$ – $18$

D. Symbolize the following argument

There is exactly one F.
There is exactly one G.
Nothing is both F and G.
∴

There are exactly two things that are either F or G.

And offer a proof of it.

$\exists x\bigl{[}F(x)\wedge\forall y(F(y)\rightarrow x=y)\bigr{]}$
$\exists x\bigl{[}G(x)\wedge\forall y(G(y)\rightarrow x=y)\bigr{]}$
$\forall x(\neg F(x)\vee\neg G(x))\therefore\phantom{.}$
∴

$\exists x\exists y\bigl{[}\neg x=y\wedge\forall z((F(z)\vee G(z))\rightarrow(x% =z\vee y=z))\bigr{]}$

Line number	Subproof level	Formula	Justification
$1$	0	$\exists x\bigl{[}F(x)\wedge\forall y(F(y)\rightarrow x=y)\bigr{]}$
$2$	0	$\exists x\bigl{[}G(x)\wedge\forall y(G(y)\rightarrow x=y)\bigr{]}$
$3$	0	$\forall x(\neg F(x)\vee\neg G(x))$
$4$	open subproof, 1	$F(a)\wedge\forall y(F(y)\rightarrow a=y)$
$5$	1	$F(a)$	$\wedge$ E $4$
$6$	1	$\forall y(F(y)\rightarrow a=y)$	$\wedge$ E $4$
$7$	1	$\neg F(a)\vee\neg G(a)$	$\forall$ E $3$
$8$	1	$\neg G(a)$	DS $7$ , $5$
$9$	open subproof, 2	$G(b)\wedge\forall y(G(y)\rightarrow b=y)$
$10$	2	$G(b)$	$\wedge$ E $9$
$11$	2	$\forall y(G(y)\rightarrow b=y)$	$\wedge$ E $9$
$12$	open subproof, 3	$a=b$
$13$	3	$G(a)$	$=$ E $12$ , $10$
$14$	3	$\bot$	$\neg$ E $13$ , $8$
$15$	close subproof, 2	$\neg a=b$	$\neg$ I $12$ – $14$
$16$	open subproof, 3	$F(c)\vee G(c)$
$17$	open subproof, 4	$F(c)$
$18$	4	$F(c)\rightarrow a=c$	$\forall$ E $6$
$19$	4	$a=c$	$\rightarrow$ E $18$ , $17$
$20$	4	$a=c\vee b=c$	$\vee$ I $19$
$21$	close subproof, open subproof, 4	$G(c)$
$22$	4	$G(c)\rightarrow b=c$	$\forall$ E $11$
$23$	4	$b=c$	$\rightarrow$ E $22$ , $21$
$24$	4	$a=c\vee b=c$	$\vee$ I $23$
$25$	close subproof, 3	$a=c\vee b=c$	$\vee$ E $16$ , $17$ – $20$ , $21$ – $24$
$26$	close subproof, 2	$(F(c)\vee G(c))\rightarrow(a=c\vee b=c)$	$\rightarrow$ I $16$ – $25$
$27$	2	$\forall z((F(z)\vee G(z))\rightarrow(a=z\vee b=z))$	$\forall$ I $26$
$28$	2	$\neg a=b\wedge\forall z((F(z)\vee G(z))\rightarrow(a=z\vee b=z))$	$\wedge$ I $15$ , $27$
$29$	2	$\exists y\bigl{[}\neg a=y\wedge\forall z((F(z)\vee G(z))\rightarrow(a=z\vee y=% z))\bigr{]}$	$\exists$ I $28$
$30$	2	$\exists x\exists y\bigl{[}\neg x=y\wedge\forall z((F(z)\vee G(z))\rightarrow(x% =z\vee y=z))\bigr{]}$	$\exists$ I $29$
$31$	close subproof, 1	$\exists x\exists y\bigl{[}\neg x=y\wedge\forall z((F(z)\vee G(z))\rightarrow(x% =z\vee y=z))\bigr{]}$	$\exists$ E $2$ , $9$ – $30$
$32$	close subproof, 0	$\exists x\exists y\bigl{[}\neg x=y\wedge\forall z((F(z)\vee G(z))\rightarrow(x% =z\vee y=z))\bigr{]}$	$\exists$ E $1$ , $4$ – $31$