Chapter 16 The very idea of natural deduction

Way back in chapter 2, we said that an argument is valid if⁠f there is no case in which all of the premises are true and the conclusion is false.

In the case of TFL, this led us to develop truth tables. Each line of a complete truth table corresponds to a valuation. So, when faced with a TFL argument, we have a very direct way to assess whether there is a valuation on which the premises are true and the conclusion is false: just thrash through the truth table.

However, truth tables may not give us much insight. Consider two arguments in TFL:

	$\displaystyle P\vee Q,\neg P$	$\displaystyle\therefore Q$
	$\displaystyle P\rightarrow Q,P$	$\displaystyle\therefore Q$

Clearly, these are valid arguments. You can confirm that they are valid by constructing four-line truth tables, but we might say that they make use of different forms of reasoning. It might be nice to keep track of these different forms of inference.

One aim of a natural deduction system is to show that particular arguments are valid, in a way that allows us to understand the reasoning that the arguments might involve. We begin with very basic rules of inference. These rules can be combined to offer more complicated arguments. Indeed, with just a small starter pack of rules of inference, we hope to capture all valid arguments.

This is a very different way of thinking about arguments.

With truth tables, we directly consider different ways to make sentences true or false. With natural deduction systems, we manipulate sentences in accordance with rules that we have set down as good rules. The latter promises to give us a better insight—or at least, a different insight—into how arguments work.

The move to natural deduction might be motivated by more than the search for insight. It might also be motivated by necessity. Consider:

$A_{1}\rightarrow C_{1}$
∴

$(A_{1}\wedge(A_{2}\wedge(A_{3}\wedge(A_{4}\wedge A_{5}))))\rightarrow((((C_{1}% \vee C_{2})\vee C_{3})\vee C_{4})\vee C_{5})$

To test this argument for validity, you might use a 1,024-line truth table. If you do it correctly, then you will see that there is no line on which all the premises are true and on which the conclusion is false. So you will know that the argument is valid. (But, as just mentioned, there is a sense in which you will not know why the argument is valid.) But now consider:

$A_{1}\rightarrow C_{1}$
∴

$(A_{1}\wedge(A_{2}\wedge(A_{3}\wedge(A_{4}\wedge(A_{5}\wedge(A_{6}\wedge(A_{7}% \wedge(A_{8}\wedge(A_{9}\wedge A_{10})))))))))\rightarrow(((((((((C_{1}\vee C_% {2})\vee C_{3})\vee C_{4})\vee C_{5})\vee C_{6})\vee C_{7})\vee C_{8})\vee C_{% 9})\vee C_{10})$

This argument is also valid—as you can probably tell—but to test it requires a truth table with $2^{20}=1{,}048{,}576$ lines. In principle, we can set a machine to grind through truth tables and report back when it is finished. In practice, complicated arguments in TFL can become intractable if we use truth tables.

When we get to first-order logic (FOL) (beginning in chapter 23), though, the problem gets dramatically worse. There is nothing like the truth table test for FOL. To assess whether or not an argument is valid, we have to reason about all interpretations, but, as we will see, there are infinitely many possible interpretations. We cannot even in principle set a machine to grind through infinitely many possible interpretations and report back when it is finished: it will never finish. We either need to come up with some more efficient way of reasoning about all interpretations, or we need to look for something different.

There are, indeed, systems that codify ways to reason about all possible interpretations. They were developed in the 1950s by Evert Beth and Jaakko Hintikka, but we will not follow this path. We will, instead, look to natural deduction.

Rather than reasoning directly about all valuations (in the case of TFL), we will try to select a few basic rules of inference. Some of these will govern the behaviour of the sentential connectives. Others will govern the behaviour of the quantifiers and identity that are the hallmarks of FOL. The resulting system of rules will give us a new way to think about the validity of arguments. The modern development of natural deduction dates from simultaneous and unrelated papers by Gerhard Gentzen and Stanisław Jaśkowski (1934). However, the natural deduction system that we will consider is based largely around work by Frederic Fitch (first published in 1952).