Solutions to Chapter 20 Proof-theoretic concepts ‣ Solutions to selected exercices ‣ forall x: Calgary

A. Show that each of the following sentences is a theorem:

1.

$O\rightarrow O$

Line number	Subproof level	Formula	Justification
$1$	open subproof, 1	$O$
$2$	1	$O$	R $1$
$3$	close subproof, 0	$O\rightarrow O$	$\rightarrow$ I $1$ – $2$

2.

$N\vee\neg N$

Line number	Subproof level	Formula	Justification
$1$	open subproof, 1	$\neg(N\vee\neg N)$
$2$	open subproof, 2	$N$
$3$	2	$N\vee\neg N$	$\vee$ I $2$
$4$	2	$\bot$	$\neg$ E $1$ , $3$
$5$	close subproof, 1	$\neg N$	$\neg$ I $2$ – $4$
$6$	1	$N\vee\neg N$	$\vee$ I $5$
$7$	1	$\bot$	$\neg$ E $1$ , $6$
$8$	close subproof, 0	$N\vee\neg N$	IP $1$ – $7$

3.

$J\leftrightarrow[J\vee(L\wedge\neg L)]$

Line number	Subproof level	Formula	Justification
$1$	open subproof, 1	$J$
$2$	1	$J\vee(L\wedge\neg L)$	$\vee$ I $1$
$3$	close subproof, open subproof, 1	$J\vee(L\wedge\neg L)$
$4$	open subproof, 2	$L\wedge\neg L$
$5$	2	$L$	$\wedge$ E $4$
$6$	2	$\neg L$	$\wedge$ E $4$
$7$	2	$\bot$	$\neg$ E $5$ , $6$
$8$	close subproof, 1	$\neg(L\wedge\neg L)$	$\neg$ I $4$ – $7$
$9$	1	$J$	DS $3$ , $8$
$10$	close subproof, 0	$J\leftrightarrow[J\vee(L\wedge\neg L)]$	$\leftrightarrow$ I $1$ – $2$ , $3$ – $9$

4.

$((A\rightarrow B)\rightarrow A)\rightarrow A$

Line number	Subproof level	Formula	Justification
$1$	open subproof, 1	$(A\rightarrow B)\rightarrow A$
$2$	open subproof, 2	$\neg A$
$3$	2	$\neg(A\rightarrow B)$	MT $1$ , $2$
$4$	open subproof, 3	$A$
$5$	3	$\bot$	$\neg$ E $4$ , $2$
$6$	3	$B$	X $5$
$7$	close subproof, 2	$A\rightarrow B$	$\rightarrow$ I $4$ – $6$
$8$	2	$\bot$	$\neg$ E $7$ , $3$
$9$	close subproof, 1	$A$	IP $1$ – $8$
$10$	close subproof, 0	$((A\rightarrow B)\rightarrow A)\rightarrow A$	$\rightarrow$ I $1$ – $9$

B. Provide proofs to show each of the following:

1.

$C\rightarrow(E\wedge G),\neg C\rightarrow G\vdash G$

Line number	Subproof level	Formula	Justification
$1$	0	$C\rightarrow(E\wedge G)$
$2$	0	$\neg C\rightarrow G$
$3$	open subproof, 1	$\neg G$
$4$	open subproof, 2	$C$
$5$	2	$E\wedge G$	$\rightarrow$ E $1$ , $4$
$6$	2	$G$	$\wedge$ E $5$
$7$	2	$\bot$	$\neg$ E $3$ , $6$
$8$	close subproof, 1	$\neg C$	$\neg$ I $4$ – $7$
$9$	1	$G$	$\rightarrow$ E $2$ , $8$
$10$	1	$\bot$	$\neg$ E $3$ , $9$
$11$	close subproof, 0	$G$	IP $3$ – $10$

2.

$M\wedge(\neg N\rightarrow\neg M)\vdash(N\wedge M)\vee\neg M$

Line number	Subproof level	Formula	Justification
$1$	0	$M\wedge(\neg N\rightarrow\neg M)$
$2$	0	$M$	$\wedge$ E $1$
$3$	0	$\neg N\rightarrow\neg M$	$\wedge$ E $1$
$4$	open subproof, 1	$\neg N$
$5$	1	$\neg M$	$\rightarrow$ E $3$ , $4$
$6$	1	$\bot$	$\neg$ E $2$ , $5$
$7$	close subproof, 0	$N$	IP $4$ – $6$
$8$	0	$N\wedge M$	$\wedge$ I $7$ , $2$
$9$	0	$(N\wedge M)\vee\neg M$	$\vee$ I $8$

3.

$(Z\wedge K)\leftrightarrow(Y\wedge M),D\wedge(D\rightarrow M)\vdash Y\rightarrow Z$

Line number	Subproof level	Formula	Justification
$1$	0	$(Z\wedge K)\leftrightarrow(Y\wedge M)$
$2$	0	$D\wedge(D\rightarrow M)$
$3$	0	$D$	$\wedge$ E $2$
$4$	0	$D\rightarrow M$	$\wedge$ E $2$
$5$	0	$M$	$\rightarrow$ E $4$ , $3$
$6$	open subproof, 1	$Y$
$7$	1	$Y\wedge M$	$\wedge$ I $6$ , $5$
$8$	1	$Z\wedge K$	$\leftrightarrow$ E $1$ , $7$
$9$	1	$Z$	$\wedge$ E $8$
$10$	close subproof, 0	$Y\rightarrow Z$	$\rightarrow$ I $6$ – $9$

4.

$(W\vee X)\vee(Y\vee Z),X\rightarrow Y,\neg Z\vdash W\vee Y$

Line number	Subproof level	Formula	Justification
$1$	0	$(W\vee X)\vee(Y\vee Z)$
$2$	0	$X\rightarrow Y$
$3$	0	$\neg Z$
$4$	open subproof, 1	$W\vee X$
$5$	open subproof, 2	$W$
$6$	2	$W\vee Y$	$\vee$ I $5$
$7$	close subproof, open subproof, 2	$X$
$8$	2	$Y$	$\rightarrow$ E $2$ , $7$
$9$	2	$W\vee Y$	$\vee$ I $8$
$10$	close subproof, 1	$W\vee Y$	$\vee$ E $4$ , $5$ – $6$ , $7$ – $9$
$11$	close subproof, open subproof, 1	$Y\vee Z$
$12$	1	$Y$	DS $11$ , $3$
$13$	1	$W\vee Y$	$\vee$ I $12$
$14$	close subproof, 0	$W\vee Y$	$\vee$ E $1$ , $4$ – $10$ , $11$ – $13$

C. Show that each of the following pairs of sentences are interderivable:

1.

$R\leftrightarrow E$ , $E\leftrightarrow R$

Line number	Subproof level	Formula	Justification
$1$	0	$R\leftrightarrow E$
$2$	open subproof, 1	$E$
$3$	1	$R$	$\leftrightarrow$ E $1$ , $2$
$4$	close subproof, open subproof, 1	$R$
$5$	1	$E$	$\leftrightarrow$ E $1$ , $4$
$6$	close subproof, 0	$E\leftrightarrow R$	$\leftrightarrow$ I $2$ – $3$ , $4$ – $5$

Line number	Subproof level	Formula	Justification
$1$	0	$E\leftrightarrow R$
$2$	open subproof, 1	$E$
$3$	1	$R$	$\leftrightarrow$ E $1$ , $2$
$4$	close subproof, open subproof, 1	$R$
$5$	1	$E$	$\leftrightarrow$ E $1$ , $4$
$6$	close subproof, 0	$R\leftrightarrow E$	$\leftrightarrow$ I $4$ – $5$ , $2$ – $3$

2.

$G$ , $\neg\neg\neg\neg G$

Line number	Subproof level	Formula	Justification
$1$	0	$G$
$2$	open subproof, 1	$\neg\neg\neg G$
$3$	1	$\neg G$	DNE $2$
$4$	1	$\bot$	$\neg$ E $1$ , $3$
$5$	close subproof, 0	$\neg\neg\neg\neg G$	$\neg$ I $2$ – $4$

Line number	Formula	Justification
$1$	$\neg\neg\neg\neg G$
$2$	$\neg\neg G$	DNE $1$
$3$	$G$	DNE $2$

3.

$T\rightarrow S$ , $\neg S\rightarrow\neg T$

Line number	Subproof level	Formula	Justification
$1$	0	$T\rightarrow S$
$2$	open subproof, 1	$\neg S$
$3$	1	$\neg T$	MT $1$ , $2$
$4$	close subproof, 0	$\neg S\rightarrow\neg T$	$\rightarrow$ I $2$ – $3$

Line number	Subproof level	Formula	Justification
$1$	0	$\neg S\rightarrow\neg T$
$2$	open subproof, 1	$T$
$3$	open subproof, 2	$\neg S$
$4$	2	$\neg T$	$\rightarrow$ E $1$ , $3$
$5$	2	$\bot$	$\neg$ E $2$ , $4$
$6$	close subproof, 1	$\neg\neg S$	$\neg$ I $3$ – $5$
$7$	1	$S$	DNE $6$
$8$	close subproof, 0	$T\rightarrow S$	$\rightarrow$ I $2$ – $7$

4.

$U\rightarrow I$ , $\neg(U\wedge\neg I)$

Line number	Subproof level	Formula	Justification
$1$	0	$U\rightarrow I$
$2$	open subproof, 1	$U\wedge\neg I$
$3$	1	$U$	$\wedge$ E $2$
$4$	1	$\neg I$	$\wedge$ E $2$
$5$	1	$I$	$\rightarrow$ E $1$ , $3$
$6$	1	$\bot$	$\neg$ E $5$ , $4$
$7$	close subproof, 0	$\neg(U\wedge\neg I)$	$\neg$ I $2$ – $6$

Line number	Subproof level	Formula	Justification
$1$	0	$\neg(U\wedge\neg I)$
$2$	open subproof, 1	$U$
$3$	open subproof, 2	$\neg I$
$4$	2	$U\wedge\neg I$	$\wedge$ I $2$ , $3$
$5$	2	$\bot$	$\neg$ E $4$ , $1$
$6$	close subproof, 1	$\neg\neg I$	$\neg$ I $3$ – $5$
$7$	1	$I$	DNE $6$
$8$	close subproof, 0	$U\rightarrow I$	$\rightarrow$ I $2$ – $7$

5.

$\neg(C\rightarrow D),C\wedge\neg D$

Line number	Subproof level	Formula	Justification
$1$	0	$C\wedge\neg D$
$2$	0	$C$	$\wedge$ E $1$
$3$	0	$\neg D$	$\wedge$ E $1$
$4$	open subproof, 1	$C\rightarrow D$
$5$	1	$D$	$\rightarrow$ E $4$ , $2$
$6$	1	$\bot$	$\neg$ E $5$ , $3$
$7$	close subproof, 0	$\neg(C\rightarrow D)$	$\neg$ I $4$ – $6$

Line number	Subproof level	Formula	Justification
$1$	0	$\neg(C\rightarrow D)$
$2$	open subproof, 1	$D$
$3$	open subproof, 2	$C$
$4$	2	$D$	R $2$
$5$	close subproof, 1	$C\rightarrow D$	$\rightarrow$ I $3$ – $4$
$6$	1	$\bot$	$\neg$ E $5$ , $1$
$7$	close subproof, 0	$\neg D$	$\neg$ I $2$ – $6$
$8$	open subproof, 1	$\neg C$
$9$	open subproof, 2	$C$
$10$	2	$\bot$	$\neg$ E $9$ , $8$
$11$	2	$D$	X $10$
$12$	close subproof, 1	$C\rightarrow D$	$\rightarrow$ I $9$ – $11$
$13$	1	$\bot$	$\neg$ E $12$ , $1$
$14$	close subproof, 0	$\neg\neg C$	$\neg$ I $8$ – $13$
$15$	0	$C$	DNE $14$
$16$	0	$C\wedge\neg D$	$\wedge$ I $15$ , $7$

6.

$\neg G\leftrightarrow H$ , $\neg(G\leftrightarrow H)$

Line number	Subproof level	Formula	Justification
$1$	0	$\neg G\leftrightarrow H$
$2$	open subproof, 1	$G\leftrightarrow H$
$3$	open subproof, 2	$G$
$4$	2	$H$	$\leftrightarrow$ E $2$ , $3$
$5$	2	$\neg G$	$\leftrightarrow$ E $1$ , $4$
$6$	2	$\bot$	$\neg$ E $3$ , $5$
$7$	close subproof, open subproof, 2	$\neg G$
$8$	2	$H$	$\leftrightarrow$ E $1$ , $7$
$9$	2	$G$	$\leftrightarrow$ E $2$ , $8$
$10$	2	$\bot$	$\neg$ E $9$ , $7$
$11$	close subproof, 1	$\bot$	LEM $3$ – $6$ , $7$ – $10$
$12$	close subproof, 0	$\neg(G\leftrightarrow H)$	$\neg$ I $2$ – $11$

Line number	Subproof level	Formula	Justification
$1$	0	$\neg(G\leftrightarrow H)$
$2$	open subproof, 1	$\neg G$
$3$	open subproof, 2	$\neg H$
$4$	open subproof, 3	$G$
$5$	3	$\bot$	$\neg$ E $4$ , $2$
$6$	3	$H$	X $5$
$7$	close subproof, open subproof, 3	$H$
$8$	3	$\bot$	$\neg$ E $7$ , $3$
$9$	3	$G$	X $8$
$10$	close subproof, 2	$G\leftrightarrow H$	$\leftrightarrow$ I $4$ – $6$ , $7$ – $9$
$11$	2	$\bot$	$\neg$ E $10$ , $1$
$12$	close subproof, 1	$H$	IP $3$ – $11$
$13$	close subproof, open subproof, 1	$H$
$14$	open subproof, 2	$G$
$15$	open subproof, 3	$G$
$16$	3	$H$	R $13$
$17$	close subproof, open subproof, 3	$H$
$18$	3	$G$	R $14$
$19$	close subproof, 2	$G\leftrightarrow H$	$\leftrightarrow$ I $15$ – $16$ , $17$ – $18$
$20$	2	$\bot$	$\neg$ E $19$ , $1$
$21$	close subproof, 1	$\neg G$	$\neg$ I $14$ – $20$
$22$	close subproof, 0	$\neg G\leftrightarrow H$	$\leftrightarrow$ I $2$ – $12$ , $13$ – $21$

D. If you know that $\mathscr{A}\vdash\mathscr{B}$ , what can you say about $(\mathscr{A}\wedge\mathscr{C})\vdash\mathscr{B}$ ? What about $(\mathscr{A}\vee\mathscr{C})\vdash\mathscr{B}$ ? Explain your answers.
If $\mathscr{A}\vdash\mathscr{B}$ , then $(\mathscr{A}\wedge\mathscr{C})\vdash\mathscr{B}$ . After all, if $\mathscr{A}\vdash\mathscr{B}$ , then there is some proof with assumption $\mathscr{A}$ that ends with $\mathscr{B}$ , and no undischarged assumptions other than $\mathscr{A}$ . Now, if we start a proof with assumption $(\mathscr{A}\wedge\mathscr{C})$ , we can obtain $\mathscr{A}$ by $\wedge$ E. We can now copy and paste the original proof of $\mathscr{B}$ from $\mathscr{A}$ , adding 1 to every line number and line number citation. The result will be a proof of $\mathscr{B}$ from assumption $\mathscr{A}\wedge\mathscr{C}$ .

However, we cannot prove much from $(\mathscr{A}\vee\mathscr{C})$ . After all, it might be impossible to prove $\mathscr{B}$ from $\mathscr{C}$ .

E. In this chapter, we claimed that it is just as hard to show that two sentences are not interderivable, as it is to show that a sentence is not a theorem. Why did we claim this? (Hint: think of a sentence that would be a theorem if⁠f $\mathscr{A}$ and $\mathscr{B}$ were interderivable.)
Consider the sentence $\mathscr{A}\leftrightarrow\mathscr{B}$ . Suppose we can show that this is a theorem. So we can prove it, with no assumptions, in $m$ lines, say. Then if we assume $\mathscr{A}$ and copy and paste the proof of $\mathscr{A}\leftrightarrow\mathscr{B}$ (changing the line numbering), we will have a deduction of this shape:

Line number	Formula	Justification
$1$	$\mathscr{A}$
$m+1$	$\mathscr{A}\leftrightarrow\mathscr{B}$
$m+2$	$\mathscr{B}$	$\leftrightarrow$ E $m+1$ , $1$

This will show that $\mathscr{A}\vdash\mathscr{B}$ . In exactly the same way, we can show that $\mathscr{B}\vdash\mathscr{A}$ . So if we can show that $\mathscr{A}\leftrightarrow\mathscr{B}$ is a theorem, we can show that $\mathscr{A}$ and $\mathscr{B}$ are interderivable.

Conversely, suppose we can show that $\mathscr{A}$ and $\mathscr{B}$ are interderivable. Then we can prove $\mathscr{B}$ from the assumption of $\mathscr{A}$ in $m$ lines, say, and prove $\mathscr{A}$ from the assumption of $\mathscr{B}$ in $n$ lines, say. Copying and pasting these proofs together (changing the line numbering where appropriate), we obtain:

Line number	Subproof level	Formula	Justification
$1$	open subproof, 1	$\mathscr{A}$
$m$	1	$\mathscr{B}$
$m+1$	close subproof, open subproof, 1	$\mathscr{B}$
$m+n$	1	$\mathscr{A}$
$m+n+1$	close subproof, 0	$\mathscr{A}\leftrightarrow\mathscr{B}$	$\leftrightarrow$ I $1$ – $m$ , $m+1$ – $m+n$

This shows that $\mathscr{A}\leftrightarrow\mathscr{B}$ is a theorem.

There was nothing special about $\mathscr{A}$ and $\mathscr{B}$ in this. So what this shows is that the problem of showing that two sentences are interderivable is, essentially, the same problem as showing that a certain kind of sentence (a biconditional) is a theorem.