Chapter 17 Basic rules for TFL

A formal proof or derivation is a sequence of sentences, some of which are marked as being initial assumptions (or premises). The last line of the formal proof is the conclusion. (Henceforth, we will simply call these ‘proofs’ or ‘derivations’, but be aware that there are informal proofs too.)

As an illustration, consider:

We will start a proof by writing the premise:

Note also that we have drawn a line underneath the premise. Everything written above the line is an assumption. Everything written below the line will either be something which follows from the assumptions, or it will be some new assumption. We are hoping to conclude ‘$\neg A\wedge \neg B$’; so we are hoping ultimately to conclude our proof with

Similarly, suppose we wanted to consider:

The argument has three premises, so we start by writing them all down, numbered, and drawing a line under them:

The very first rule is so breathtakingly obvious that it is surprising we bother with it at all.

If you already have shown something in the course of a proof, the reiteration rule allows you to repeat it on a new line. For example:

Here is a general expression of the rule:

The point is that, if any sentence $𝒜$ occurs on some line, then we can repeat $𝒜$ on later lines. Each line of our proof must be justified by some rule, and here we have ‘R $m$’. This means: Reiteration, applied to line $m$.

Two things need emphasizing. First ‘$𝒜$’ is not a sentence of TFL. Rather, it a symbol in the metalanguage, which we use when we want to talk about any sentence of TFL (see chapter 8). Second, and similarly, ‘$m$’ is not a symbol that will appear on a proof. Rather, it is a symbol in the metalanguage, which we use when we want to talk about any line number of a proof. In an actual proof, the lines are numbered ‘$1$’, ‘$2$’, ‘$3$’, and so forth. But when we define the rule, we use variables like ‘$m$’ to underscore the point that the rule may be applied at any point.

Suppose we want to show that Ludwig is both reactionary and libertarian. One obvious way to do this would be as follows: first we show that Ludwig is reactionary; then we show that Ludwig is libertarian; then we put these two demonstrations together, to obtain the conjunction.

Our natural deduction system will capture this thought straightforwardly. In the example given, we might adopt the following symbolization key:

$R$:

Ludwig is reactionary

$L$:

Ludwig is libertarian

Perhaps we are working through a proof, and we have obtained ‘$R$’ on line $8$ and ‘$L$’ on line $15$. Then on any subsequent line we can obtain ‘$R\wedge L$’ thus:

The rule is called ‘conjunction introduction’ because it introduces the symbol ‘$\wedge$’ into our proof where it may have been absent. Correspondingly, we have a rule that eliminates that symbol. Suppose you have shown that Ludwig is both reactionary and libertarian. You are entitled to conclude that Ludwig is reactionary. Equally, you are entitled to conclude that Ludwig is libertarian. Putting this together, we obtain our conjunction elimination rule(s):

and equally:

The point is simply that, when you have a conjunction on some line of a proof, you can obtain either of the conjuncts by $\wedge$E. One point is worth emphasising: you can only apply this rule when conjunction is the main logical operator. So you cannot infer ‘$D$’ just from ‘$C\vee (D\wedge E)$’!

Even with just these two rules, we can start to see some of the power of our formal proof system. Consider:

• ​

  $[(A\vee B)\to (C\vee D)]\wedge [(E\vee F)\to (G\vee H)]$

• ∴
  ​

  $[(E\vee F)\to (G\vee H)]\wedge [(A\vee B)\to (C\vee D)]$

The main logical operator in both the premise and conclusion of this argument is ‘$\wedge$’. In order to provide a proof, we begin by writing down the premise, which is our assumption. We draw a line below this: everything after this line must follow from our assumptions by (repeated applications of) our rules of inference. So the beginning of the proof looks like this:

It is worth giving another example. Back in section 11.3, we noted that this argument is valid:

To provide a proof corresponding to this argument, we start by writing:

Let’s give one final illustration. When using the $\wedge$I rule, there is no requirement to apply it to different sentences. So, if we want, we can formally prove ‘$A\wedge A$’ from ‘$A$’ thus:

Consider the following argument:

• ​

  If Jane is smart then she is fast.

• ​

  Jane is smart.

• ∴
  ​

  Jane is fast.

This argument is certainly valid, and it suggests a straightforward conditional elimination rule ($\to$E):

This rule is also sometimes called modus ponens. Again, this is an elimination rule, because it allows us to obtain a sentence that may not contain ‘$\to$’, having started with a sentence that did contain ‘$\to$’. Note that the conditional $𝒜\to ℬ$ and the antecedent $𝒜$ can be separated from one another in the proof, and they can appear in any order. However, in the citation for $\to$E, we always cite the conditional first, followed by the antecedent.

The rule for conditional introduction is also quite easy to motivate. The following argument should be valid:

• ​

  Ludwig is reactionary.

• ∴
  ​

  If Ludwig is libertarian, then Ludwig is both reactionary and libertarian.

If someone doubted that this was valid, we might try to convince them otherwise by explaining ourselves as follows:

Assume that Ludwig is reactionary. Now, additionally assume that Ludwig is libertarian. Then by conjunction introduction—which we just discussed—Ludwig is both reactionary and libertarian. Of course, that’s conditional on the assumption that Ludwig is libertarian. But this just means that, if Ludwig is libertarian, then he is both reactionary and libertarian.

Transferred into natural deduction format, here is the pattern of reasoning that we just used. We started with one premise, ‘Ludwig is reactionary’, thus:

With this extra assumption in place, we are in a position to use $\wedge$I. So we can continue our proof:

The general pattern at work here is the following. We first make an additional assumption, $𝒜$; and from that additional assumption, we prove $ℬ$. In that case, we know the following: If $𝒜$ is true, then $ℬ$ is true. This is wrapped up in the rule for conditional introduction:

There can be as many or as few lines as you like between lines $i$ and $j$.

It will help to offer a second illustration of $\to$I in action. Suppose we want to consider the following:

We start by listing both of our premises. Then, since we want to arrive at a conditional (namely, ‘$P\to R$’), we additionally assume the antecedent to that conditional. Thus our main proof starts:

The rule $\to$I invoked the idea of making additional assumptions. These need to be handled with some care. Consider this proof:

But suppose we now tried to continue the proof as follows:

We can describe the process of making an additional assumption as one of performing a subproof: a subsidiary proof within the main proof. When we start a subproof, we draw another vertical line to indicate that we are no longer in the main proof. Then we write in the assumption upon which the subproof will be based. A subproof can be thought of as essentially posing this question: what could we show, if we also make this additional assumption?

When we are working within the subproof, we can refer to the additional assumption that we made in introducing the subproof, and to anything that we obtained from our original assumptions. (After all, those original assumptions are still in effect.) At some point though, we will want to stop working with the additional assumption: we will want to return from the subproof to the main proof. To indicate that we have returned to the main proof, the vertical line for the subproof comes to an end. At this point, we say that the subproof is closed . Having closed a subproof, we have set aside the additional assumption, so it will be illegitimate to draw upon anything that depends upon that additional assumption. Thus we stipulate:

This stipulation rules out the disastrous attempted proof above. The application of rule $\to$E on line $5$ requires that we cite two individual lines from earlier in the proof. One of these lines (namely, line $3$) occurs within a subproof (lines $2$–$3$). By line $5$, where we have to cite line $3$, the subproof has been closed. This is illegitimate: we are not allowed to cite line $3$ on line $5$.

Closing a subproof is called discharging the assumptions of that subproof. So we can put the point this way: you cannot refer back to anything that was obtained using discharged assumptions.

Subproofs, then, allow us to think about what we could show, if we made additional assumptions. The point to take away from this is not surprising—in the course of a proof, we have to keep very careful track of what assumptions we are making, at any given moment. Our proof system does this very graphically. (Indeed, that’s precisely why we have chosen to use this proof system.)

Once we have started thinking about what we can show by making additional assumptions, nothing stops us from posing the question of what we could show if we were to make even more assumptions? This might motivate us to introduce a subproof within a subproof. Here is an example using only the rules which we have considered so far:

Again, though, we need to keep careful track of what we are assuming at any given moment. Suppose we tried to continue the proof as follows:

The essential problem is that the subproof that began with the assumption ‘$C$’ depended crucially on the fact that we had assumed ‘$B$’ on line $2$. By line $6$, we have discharged the assumption ‘$B$’: we have stopped asking ourselves what we could show, if we also assumed ‘$B$’. So it is simply cheating, to try to help ourselves (on line $7$) to the subproof that began with the assumption ‘$C$’. Thus we stipulate, much as before, that a subproof can only be cited on a line if it does not occur within some other subproof which is already closed at that line. The attempted disastrous proof violates this stipulation. The subproof of lines $3$–$4$ occurs within a subproof that ends on line $5$. So it cannot be invoked on line $7$.

Here is one further case we have to exclude:

One last point to emphasize how rules can be applied: where a rule requires you to cite an individual line, you cannot cite a subproof instead; and where it requires you to cite a subproof, you cannot cite an individual line instead. So for instance, this is incorrect:

It is always permissible to open a subproof with any assumption. However, there is some strategy involved in picking a useful assumption. Starting a subproof with an arbitrary, wacky assumption would just waste lines of the proof. In order to obtain a conditional by $\to$I, for instance, you must assume the antecedent of the conditional in a subproof.

Equally, it is always permissible to close a subproof (and discharge its assumptions). However, it will not be helpful to do so until you have reached something useful. Once the subproof is closed, you can only cite the entire subproof in any justification. Those rules that call for a subproof or subproofs, in turn, require that the last line of the subproof is a sentence of some form or other. For instance, you are only allowed to cite a subproof for $\to$I if the line you are justifying is of the form $𝒜\to ℬ$, $𝒜$ is the assumption of your subproof, and $ℬ$ is the last line of your subproof.

The rules for the biconditional will be like double-barrelled versions of the rules for the conditional.

In order to prove ‘$F\leftrightarrow G$’, for instance, you must be able to prove ‘$G$’ on the assumption ‘$F$’ and prove ‘$F$’ on the assumption ‘$G$’. The biconditional introduction rule ($\leftrightarrow$I) therefore requires two subproofs. Schematically, the rule works like this:

There can be as many lines as you like between $i$ and $j$, and as many lines as you like between $k$ and $l$. Moreover, the subproofs can come in any order, and the second subproof does not need to come immediately after the first.

The biconditional elimination rule ($\leftrightarrow$E) lets you do a bit more than the conditional rule. If you have the left-hand subsentence of the biconditional, you can obtain the right-hand subsentence. If you have the right-hand subsentence, you can obtain the left-hand subsentence. So we allow:

and equally:

Note that the biconditional, and the right or left half, can be separated from one another, and they can appear in any order. However, in the citation for $\leftrightarrow$E, we always cite the biconditional first.

Suppose Ludwig is reactionary. Then Ludwig is either reactionary or libertarian. After all, to say that Ludwig is either reactionary or libertarian is to say something weaker than to say that Ludwig is reactionary.

Let’s emphasize this point. Suppose Ludwig is reactionary. It follows that Ludwig is either reactionary or a kumquat. Equally, it follows that either Ludwig is reactionary or kumquats are the only fruit. Equally, it follows that either Ludwig is reactionary or God is dead. Many of these are strange inferences to draw, but there is nothing logically wrong with them (even if they maybe violate all sorts of implicit conversational norms).

Armed with all this, we present the disjunction introduction rule(s):

and

Notice that $ℬ$ can be any sentence whatsoever, so the following is a perfectly acceptable proof:

The disjunction elimination rule is slightly trickier. Suppose that either Ludwig is reactionary or he is libertarian. What can you conclude? Not that Ludwig is reactionary; it might be that he is libertarian instead. Equally, not that Ludwig is libertarian; for he might merely be reactionary. Disjunctions, just by themselves, are hard to work with.

But suppose that we could somehow show both of the following: first, that Ludwig’s being reactionary entails that he is an Austrian economist; second, that Ludwig’s being libertarian entails that he is an Austrian economist. Then if we know that Ludwig is either reactionary or libertarian, then we know that, whichever he is, Ludwig is an Austrian economist. This insight can be expressed in the following rule, which is our disjunction elimination ($\vee$E) rule:

This is obviously a bit clunkier to write down than our previous rules, but the point is fairly simple. Suppose we have some disjunction, $𝒜\vee ℬ$. Suppose we have two subproofs, showing us that $𝒞$ follows from the assumption that $𝒜$, and that $𝒞$ follows from the assumption that $ℬ$. Then we can infer $𝒞$ itself. As usual, there can be as many lines as you like between $i$ and $j$, and as many lines as you like between $k$ and $l$. Moreover, the subproofs and the disjunction can come in any order, and do not have to be adjacent.

Some examples might help illustrate this. Consider this argument:

An example proof might run thus:

We have only one connective left to deal with: negation. But to tackle it, we must connect negation with contradiction.

An effective form of argument is to argue your opponent into contradicting themselves. At that point, you have them on the ropes. They have to give up at least one of their assumptions. We are going to make use of this idea in our proof system, by adding a new symbol, ‘$\perp$’, to our proofs. This should be read as something like ‘contradiction!’ or ‘reductio!’ or ‘but that’s absurd!’ The rule for introducing this symbol is that we can use it whenever we explicitly contradict ourselves, i.e., whenever we find both a sentence and its negation appearing in our proof:

It does not matter what order the sentence and its negation appear in, and they do not need to appear on adjacent lines. However, we always cite the line number of the negation first, followed by that of the sentence it is a negation of.

There is obviously a tight link between contradiction and negation. The rule $\neg$E lets us proceed from two contradictory sentences—$𝒜$ and its negation $\neg 𝒜$—to an explicit contradiction $\perp$. We choose the label for a reason: it is the most basic rule that lets us proceed from a premise containing a negation, i.e., $\neg 𝒜$, to a sentence not containing it, i.e., $\perp$. So it is a rule that eliminates $\neg$.

We have said that ‘$\perp$’ should be read as something like ‘contradiction!’ but this does not tell us much about the symbol. There are, roughly, three ways to approach the symbol.

1. 1.
   ​

   We might regard ‘$\perp$’ as a new atomic sentence of TFL, but one which can only ever have the truth value False.

2. 2.
   ​

   We might regard ‘$\perp$’ as an abbreviation for some canonical contradiction, such as ‘$A\wedge \neg A$’. This will have the same effect as the above—obviously, ‘$A\wedge \neg A$’ only ever has the truth value False—but it means that, officially, we do not need to add a new symbol to TFL.

3. 3.
   ​

   We might regard ‘$\perp$’, not as a symbol of TFL, but as something more like a punctuation mark that appears in our proofs. (It is on a par with the line numbers and the vertical lines, say.)

There is something very philosophically attractive about the third option, but here we will officially adopt the first. ‘$\perp$’ is to be read as a sentence letter that is always false. This means that we can manipulate it, in our proofs, just like any other sentence.

We still have to state a rule for negation introduction. The rule is very simple: if assuming something leads you to a contradiction, then the assumption must be wrong. This thought motivates the following rule:

There can be as many lines between $i$ and $j$ as you like. To see this in practice, and interacting with negation, consider this proof:

If the assumption that $𝒜$ is true leads to a contradiction, $𝒜$ cannot be true, i.e., it must be false, i.e., $\neg 𝒜$ must be true. Of course, if the assumption that $𝒜$ is false (i.e., the assumption that $\neg 𝒜$ is true) leads to a contradiction, then $𝒜$ cannot be false, i.e., $𝒜$ must be true. So we can consider the following rule:

This rule is called indirect proof, since it allows us to prove $𝒜$ indirectly, by assuming its negation. Formally, the rule is very similar to $\neg$I, but $𝒜$ and $\neg 𝒜$ have changed places. Since $\neg 𝒜$ is not the conclusion of the rule, we are not introducing $\neg$, so IP is not a rule that introduces any connective. It also doesn’t eliminate a connective, since it has no free-standing premises which contain $\neg$, only a subproof with an assumption of the form $\neg 𝒜$. By contrast, $\neg$E does have a premise of the form $\neg 𝒜$: that’s why $\neg$E eliminates $\neg$, but IP does not.¹¹ 1 There are logicians who have qualms about IP, but not about $\neg$E. They are called “intuitionists.” Intuitionists don’t buy our basic assumption that every sentence has one of two truth values, true or false. They also think that $\neg$ works differently—for them, a proof of $\perp$ from $𝒜$ guarantees $\neg 𝒜$, but a proof of $\perp$ from $\neg 𝒜$ does not guarantee that $𝒜$, but only $\neg \neg 𝒜$. So, for them, $𝒜$ and $\neg \neg 𝒜$ are not equivalent.

Using $\neg$I, we were able to give a proof of $\neg \neg 𝒟$ from $𝒟$. Using IP, we can go the other direction (with essentially the same proof).

We need one last rule. It is a kind of elimination rule for ‘$\perp$’, and known as explosion.²² 2 The Latin name for this principle is ex contradictione quodlibet, “from contradiction, anything.” If we obtain a contradiction, symbolized by ‘$\perp$’, then we can infer whatever we like. How can this be motivated, as a rule of argumentation? Well, consider the English rhetorical device ‘…and if that’s true, I’ll eat my hat’. Since contradictions simply cannot be true, if one is true then not only will I eat my hat, I’ll have it too. Here is the formal rule:

Note that $𝒜$ can be any sentence whatsoever.

The explosion rule is a bit odd. It looks like $𝒜$ arrives in our proof like a bunny out of a hat. When trying to find proofs, it is very tempting to try to use it everywhere, since it seems so powerful. Resist this temptation: you can only apply it when you already have $\perp$! And you get $\perp$ only when your assumptions are contradictory.

Still, isn’t it odd that from a contradiction anything whatsoever should follow? Not according to our notion of entailment and validity. For $𝒜$ entails $ℬ$ if⁠f there is no valuation of the sentence letters which makes $𝒜$ true and $ℬ$ false at the same time. Now $\perp$ is a contradiction—it is never true, whatever the valuation of the sentence letters. Since there is no valuation which makes $\perp$ true, there of course is also no valuation that makes $\perp$ true and $ℬ$ false! So according to our definition of entailment, $\perp \models ℬ$, whatever $ℬ$ is. A contradiction entails anything.³³ 3 There are some logicians who don’t buy this. They think that if $𝒜$ entails $ℬ$, there must be some relevant connection between $𝒜$ and $ℬ$—and there isn’t one between $\perp$ and some arbitrary sentence $ℬ$. So these logicians develop other, “relevant” logics in which you aren’t allowed the explosion rule.

These are all of the basic rules for the proof system for TFL.