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.