Solutions to Chapter 39 Rules for identity

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

1. 1.
   ​

   $P(a)\vee Q(b),Q(b)\to b=c,\neg P(a)⊢Q(c)$

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

2. 2.
   ​

   $m=n\vee n=o,A(n)⊢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. 3.
   ​

   $\forall xx=m,R(m,a)⊢\exists xR(x,x)$

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

4. 4.
   ​

   $\forall x\forall y(R(x,y)\to x=y)⊢R(a,b)\to R(b,a)$

   Line number	Subproof level	Formula	Justification
   1	0	$\forall x\forall y(R(x,y)\to x=y)$
   2	open subproof, 1	$R(a,b)$
   3	1	$\forall y(R(a,y)\to a=y)$	$\forall$E 1
   4	1	$R(a,b)\to a=b$	$\forall$E 3
   5	1	$a=b$	$\to$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)\to R(b,a)$	$\to$I 2–7

5. 5.
   ​

   $\neg \exists x\neg x=m⊢\forall x\forall y(P(x)\to 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)\to P(b)$	$\to$I 7–9
   11	0	$\forall y(P(a)\to P(y))$	$\forall$I 10
   12	0	$\forall x\forall y(P(x)\to P(y))$	$\forall$I 11

6. 6.
   ​

   $\exists xJ(x),\exists x\neg J(x)⊢\exists x\exists y\neg x=y$

   Line number	Subproof level	Formula	Justification
   1	0	$\exists xJ(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	$\perp$	$\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. 7.
   ​

   $\forall x(x=n\leftrightarrow M(x)),\forall x(O(x)\vee \neg M(x))⊢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	$\perp$	$\neg$E 5, 8
   10	close subproof, 0	$\neg \neg O(n)$	$\neg$I 7–9
   11	0	$O(n)$	DNE 10

8. 8.
   ​

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

   Line number	Subproof level	Formula	Justification
   1	0	$\exists xD(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. 9.
   ​

   $\exists x\left[(K(x)\wedge \forall y(K(y)\to x=y))\wedge B(x)\right],K(d)⊢B(d)$

   Line number	Subproof level	Formula	Justification
   1	0	$\exists x[(K(x)\wedge \forall y(K(y)\to x=y)\wedge B(x)]$
   2	0	$K(d)$
   3	open subproof, 1	$(K(a)\wedge \forall y(K(y)\to a=y))\wedge B(a)$
   4	1	$K(a)\wedge \forall y(K(y)\to a=y)$	$\wedge$E 3
   5	1	$K(a)$	$\wedge$E 4
   6	1	$\forall y(K(y)\to a=y)$	$\wedge$E 4
   7	1	$K(d)\to a=d$	$\forall$E 6
   8	1	$a=d$	$\to$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. 10.
    ​

    $⊢P(a)\to \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)\to \forall x(P(x)\vee \neg x=a)$	$\to$I 1–8

B. Show that the following are interderivable:

• ‣
  ​

  $\exists x\left([F(x)\wedge \forall y(F(y)\to x=y)]\wedge x=n\right)$

• ‣
  ​

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

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

In one direction:

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

• ‣
  ​

  $\exists xF(x)\wedge \forall x\forall y\left[(F(x)\wedge F(y))\to x=y\right]$

• ‣
  ​

  $\exists x\left[F(x)\wedge \forall y(F(y)\to x=y)\right]$

• ‣
  ​

  $\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:

And finally, the third proof:

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\left[F(x)\wedge \forall y(F(y)\to x=y)\right]$

• $\exists x\left[G(x)\wedge \forall y(G(y)\to x=y)\right]$

• $\forall x(\neg F(x)\vee \neg G(x))\therefore$

• ∴
  ​

  $\exists x\exists y\left[\neg x=y\wedge \forall z((F(z)\vee G(z))\to (x=z\vee y=z))\right]$