Chapter 22 Soundness and completeness

In chapter 20, we saw that we could use derivations to test for the same concepts we used truth tables to test for. Not only could we use derivations to prove that an argument is valid, we could also use them to test if a sentence is a tautology or a pair of sentences are equivalent. We also started using the single turnstile the same way we used the double turnstile. If we could prove that $\mathscr{A}$ was a tautology using a truth table, we wrote $\vDash\mathscr{A}$ , and if we could prove it using a derivation, we wrote $\vdash\mathscr{A}$ .

You may have wondered at that point if the two kinds of turnstiles always worked the same way. If you can show that $\mathscr{A}$ is a tautology using truth tables, can you also always show that it is a theorem using a derivation? Is the reverse true? Are these things also true for valid arguments and pairs of equivalent sentences? As it turns out, the answer to all these questions and many more like them is yes. We can show this by defining all these concepts separately and then proving them equivalent. That is, we imagine that we actually have two notions of validity, valid ${}_{\vDash}$ and valid ${}_{\vdash}$ and then show that the two concepts always work the same way.

To begin with, we need to define all of our logical concepts separately for truth tables and derivations. A lot of this work has already been done. We handled all of the truth table definitions in chapter 12. We have also already given proof-theoretic definitions for theorems and pairs of logically equivalent sentences. The other definitions follow naturally. For most logical properties we can devise a test using derivations, and those that we cannot test for directly can be defined in terms of the concepts that we can define.

For instance, we defined a theorem as a sentence that can be derived without any premises (p. 20). Since the negation of a contradiction is a tautology, we can define an inconsistent sentence in TFL as a sentence whose negation can be derived without any premises.¹¹ 1 Note that $\lnot\mathscr{A}$ is a theorem if⁠f $\mathscr{A}\vdash\bot$ . The syntactic definition of a contingent sentence is a little different. We don’t have any practical, finite method for proving that a sentence is contingent using derivations, the way we did using truth tables. So we have to content ourselves with defining “contingent sentence” negatively. A sentence is proof-theoretically contingent in TFL if it is neither a theorem nor an inconsistent sentence.

A collection of sentences is inconsistent in TFL if and only if one can derive the contradiction $\bot$ from them. Consistency, on the other hand, is like contingency, in that we do not have a practical finite method to test for it directly. So again, we have to define a term negatively. A collection of sentences is consistent in TFL if and only if they are not inconsistent.

Finally, an argument is provably valid in TFL if and only if there is a derivation of its conclusion from its premises. All of these definitions are given in table 22.1.

Concept	Truth table (semantic) definition	Proof-theoretic (syntactic) definition
Tautology/ theorem	A sentence whose truth table only has Ts under the main connective	A sentence that can be derived without any premises.
Contradiction/ inconsistent sentence	A sentence whose truth table only has Fs under the main connective	A sentence whose negation can be derived without any premises
Contingent sentence	A sentence whose truth table contains both Ts and Fs under the main connective	A sentence that is not a theorem or contradiction
Equivalent sentences	The columns under the main connectives are identical.	The sentences can be derived from each other
Unsatisfiable/ inconsistent sentences	Sentences which do not have a single line in their truth table where they are all true.	Sentences from which one can derive the contradiction $\bot$
Satisfiable/ Consistent sentences	Sentences which have at least one line in their truth table where they are all true.	Sentences from which one cannot derive the contradiction $\bot$
Valid argument	An argument whose truth table has no lines where there are all Ts under main connectives for the premises and an F under the main connective for the conclusion.	An argument where one can derive the conclusion from the premises.

Table 22.1: Two ways to define logical concepts.

All of our concepts have now been defined both semantically (using valuations and truth tables) and proof-theoretically (on the basis of natural deduction). How can we establish that these definitions always work the same way? A full proof here goes well beyond the scope of this book. However, we can sketch what it would be like. We will focus on showing the two notions of validity to be equivalent. From that the other concepts will follow quickly. The proof will have to go in two directions. First we will have to show that things which are proof-theoretically valid will also be semantically valid. In other words, everything that we can prove using derivations could also be proven using truth tables. Put symbolically, we want to show that valid ${}_{\vdash}$ implies valid ${}_{\vDash}$ . Afterwards, we will need to show things in the other directions, valid ${}_{\vDash}$ implies valid ${}_{\vdash}$

This argument from $\vdash$ to $\vDash$ is the problem of soundness . A proof system is sound if there are no derivations of arguments that can be shown invalid by truth tables. Demonstrating that the proof system is sound would require showing that any possible proof is the proof of a valid argument. It would not be enough simply to succeed when trying to prove many valid arguments and to fail when trying to prove invalid ones. The proof itself requires some care. In a nutshell, it involves showing that every inference rule preserves the property that its conclusion is entailed by the premises of the proof together with whatever assumptions are open. You can find the details of this proof worked out in chapter 48.

Soundness means that $\mathscr{A}\vdash\mathscr{B}$ implies $\mathscr{A}\vDash\mathscr{B}.$ What about the other direction, that is, why think that every argument that can be shown valid using truth tables can also be proven using a derivation?

This is the problem of completeness. A proof system has the property of completeness if and only if there is a derivation of every semantically valid argument. Proving that a system is complete is generally harder than proving that it is sound. Proving that a system is sound amounts to showing that all of the rules of your proof system work the way they are supposed to. Showing that a system is complete means showing that you have included all the rules you need, that you haven’t left any out. Showing this is beyond the scope of this book. The important point is that, happily, the proof system for TFL is both sound and complete. This is not the case for all proof systems or all formal languages. Because it is true of TFL, we can choose to give proofs or give truth tables—whichever is easier for the task at hand.

Now that we know that the truth table method is interchangeable with the method of derivations, you can chose which method you want to use for any given problem. Students often prefer to use truth tables, because they can be produced purely mechanically, and that seems ‘easier’. However, we have already seen that truth tables become impossibly large after just a few sentence letters. On the other hand, there are a couple situations where using proofs simply isn’t possible. We syntactically defined a contingent sentence as a sentence that couldn’t be proven to be a tautology or a contradiction. There is no practical way to prove this kind of negative statement. We will never know if there isn’t some proof out there that a statement is a contradiction and we just haven’t found it yet. We have nothing to do in this situation but resort to truth tables. Similarly, we can use derivations to prove two sentences equivalent, but what if we want to prove that they are not equivalent? We have no way of proving that we will never find the relevant proof. So we have to fall back on truth tables again.

Table 22.2 summarizes when it is best to give proofs and when it is best to give truth tables.

Logical property	To prove it present	To prove it absent
Being a theorem	Derive the sentence	Find a false line in the truth table for the sentence
Being a contradiction	Derive the negation of the sentence	Find a true line in the truth table for the sentence
Contingency	Find a false line and a true line in the truth table for the sentence	Prove the sentence or its negation
Equivalence	Derive each sentence from the other	Find a line in the truth tables for the sentence where they have different values
Consistency	Find a line in truth table for the sentence where they all are true	Derive a contradiction from the sentences
Validity	Derive the conclusion from the premises	Find a line in the truth table where the premises are true and the conclusion false.

Table 22.2: When to provide a truth table and when to provide a proof.

Practice exercises

A. Use either a derivation or a truth table for each of the following.

1.

Show that $A\rightarrow[((B\wedge C)\vee D)\rightarrow A]$ is a theorem.
2.

Show that $A\rightarrow(A\rightarrow B)$ is not a theorem.
3.

Show that the sentence $A\rightarrow\neg{A}$ is not a contradiction.
4.

Show that the sentence $A\leftrightarrow\neg A$ is a contradiction.
5.

Show that the sentence $\neg(W\rightarrow(J\vee J))$ is contingent.
6.

Show that the sentence $\neg(X\vee(Y\vee Z))\vee(X\vee(Y\vee Z))$ is not contingent.
7.

Show that the sentence $B\rightarrow\neg S$ is equivalent to the sentence $\neg\neg B\rightarrow\neg S$ .
8.

Show that the sentence $\neg(X\vee O)$ is not equivalent to the sentence $X\wedge O$ .
9.

Show that the sentences $\neg(A\vee B)$ , $C$ , $C\rightarrow A$ are jointly inconsistent.
10.

Show that the sentences $\neg(A\vee B)$ , $\neg{B}$ , $B\rightarrow A$ are jointly consistent.
11.

Show that $\neg(A\vee(B\vee C))$ $\therefore$ $\neg{C}$ is valid.
12.

Show that $\neg(A\wedge(B\vee C))$ $\therefore$ $\neg{C}$ is invalid.

B. Use either a derivation or a truth table for each of the following.

1.

Show that $A\rightarrow(B\rightarrow A)$ is a theorem.
2.

Show that $\neg(((N\leftrightarrow Q)\vee Q)\vee N)$ is not a theorem.
3.

Show that $Z\vee(\neg Z\leftrightarrow Z)$ is contingent.
4.

Show that $(L\leftrightarrow((N\rightarrow N)\rightarrow L))\vee H$ is not contingent.
5.

Show that $(A\leftrightarrow A)\wedge(B\wedge\neg B)$ is a contradiction.
6.

Show that $(B\leftrightarrow(C\vee B))$ is not a contradiction.
7.

Show that $((\neg X\leftrightarrow X)\vee X)$ is equivalent to $X$ .
8.

Show that $F\wedge(K\wedge R)$ is not equivalent to $(F\leftrightarrow(K\leftrightarrow R))$ .
9.

Show that the sentences $\neg(W\rightarrow W)$ , $(W\leftrightarrow W)\wedge W$ , $E\vee(W\rightarrow\neg(E\wedge W))$ are jointly inconsistent.
10.

Show that the sentences $\neg R\vee C$ , $(C\wedge R)\rightarrow\neg R$ , $(\neg(R\vee C)\rightarrow R)$ are jointly consistent.
11.

Show that $\neg\neg(C\leftrightarrow\neg C),((G\vee C)\vee G)\therefore((G\rightarrow C)% \wedge G)$ is valid.
12.

Show that $\neg\neg L,(C\rightarrow\neg L)\rightarrow C)\therefore\neg C$ is invalid.