6. Conditional Derivations

[latexpage]

6.1  An argument from Hobbes

In his great work, Leviathan, the philosopher Thomas Hobbes (1588-1679) gives an important argument for government.  Hobbes begins by claiming that without a common power, our condition is very poor indeed.  He calls this state without government, “the state of nature”, and claims

Hereby it is manifest that during the time men live without a common power to keep them all in awe, they are in that condition which is called war; and such a war as is of every man against every man…. In such condition there is no place for industry, because the fruit thereof is uncertain: and consequently no culture of the earth; no navigation, nor use of the commodities that may be imported by sea; no commodious building; no instruments of moving and removing such things as require much force; no knowledge of the face of the earth; no account of time; no arts; no letters; no society; and which is worst of all, continual fear, and danger of violent death; and the life of man, solitary, poor, nasty, brutish, and short.^[8]

Hobbes developed what is sometimes called “contract theory”.  This is a view of government in which one views the state as the product of a rational contract.  Although we inherit our government, the idea is that in some sense we would find it rational to choose the government, were we ever in the position to do so.  So, in the passage above, Hobbes claims that in this state of nature, we have absolute freedom, but this leads to universal struggle between all people.  There can be no property, for example, if there is no power to enforce property rights.  You are free to take other people’s things, but they are also free to take yours.  Only violence can discourage such theft.  But, a common power, like a king, can enforce rules, such as property rights.  To have this common power, we must give up some freedoms.  You are (or should be, if it were ever up to you) willing to give up those freedoms because of the benefits that you get from this.  For example, you are willing to give up the freedom to just seize people’s goods, because you like even more that other people cannot seize your goods.

We can reconstruct Hobbes’s defense of government, greatly simplified, as being something like this:

If we want to be safe, then we should have a state that can protect us.

If we should have a state that can protect us, then we should give up some freedoms.

Therefore, if we want to be safe, then we should give up some freedoms.

Let us use the following translation key.

P:  We want to be safe.

Q:  We should have a state that can protect us.

R:  We should give up some freedoms.

The argument in our logical language would then be:

(P→Q)

(Q→R)

_____

(P→R)

This is a valid argument.  Let’s take the time to show this with a truth table.

The rows in which all the premises are true are the first, fifth, seventh, and eighth rows.  Note that in each such row, the conclusion is true.  Thus, in any kind of situation where the premises are true, the conclusion is true.  This is our semantics for a valid argument.

What syntactic method can we use to prove this argument is valid?  Right now, we have none.  Other than double negation, we cannot even apply any of our inference rules using these premises.

Some logic systems introduce a rule to capture this inference; this rule is typically called the “chain rule”.  But, there is a more general principle at stake here: we need a way to show conditionals.  So we want to take another approach to showing this argument is valid.

6.2  Conditional derivation

As a handy rule of thumb, we can think of the inference rules as providing a way to either show a kind of sentence, or to make use of a kind of sentence.  For example, adjunction allows us to show a conjunction.  Simplification allows us to make use of a conjunction.  But this pattern is not complete:  we have rules to make use of a conditional (modus ponens and modus tollens), but no rule to show a conditional.

We will want to have some means to prove a conditional, because sometimes an argument will have a conditional as a conclusion.  It is not clear what rule we should introduce, however.  The conditional is true when the antecedent is false, or if both the antecedent and the consequent are true.  That’s a rather messy affair for making an inference rule.

However, think about what the conditional asserts:  if the antecedent is true, then the consequent is true.  We can make use of this idea not with an inference rule, but rather in the very structure of a proof.  We treat the proof as embodying a conditional relationship.

Our idea is this:  let us assume some sentence, Φ.  If we can then prove another sentence Ψ, we will have proved that if Φ is true then Ψ is true.  The proof structure will thus have a shape like this:

\[

\fitchctx{
\subproof{\pline{\phi}}{
\ellipsesline\\
\pline{\psi}
}
\fpline{(\phi \lif \psi)}
}
\]

The last line of the proof is justified by the shape of the proof:  by assuming that Φ is true, and then using our inference rules to prove Ψ, we know that if Φ is true then Ψ is true.  And this is just what the conditional asserts.

This method is sometimes referred to as an application of the deduction theorem.  In chapter 17 we will prove the deduction theorem.  Here, instead, we shall think of this as a proof method, traditionally called “conditional derivation”.

A conditional derivation is like a direct derivation, but with two differences.  First, along with the premises, you get a single special assumption, called “the assumption for conditional derivation”.  Second, you do not aim to show your conclusion, but rather the consequent of your conclusion.  So, to show (Φ→Ψ) you will always assume Φ and try to show Ψ.  Also, in our logical system, a conditional derivation will always be a subproof.  A subproof is a proof within another proof.  We always start with a direct proof, and then do the conditional proof within that direct proof.

Here is how we would apply the proof method to prove the validity of Hobbes’s argument, as we reconstructed it above.

\[

\fitchprf{\pline[1.] {(P \lif Q)} [premise]\\
\pline[2.]{(Q \lif R))} [premise]\\
}
{
\subproof{\pline[3.]{P}[assumption for conditional derivation]}{
\pline[4]{Q}[modus ponens, 1, 3]\\
\pline[5.]{R}[modus ponens, 2, 4]
}
\pline[6.]{(P \lif R)}[conditional derivation, 3-5]
}

\]

Our Fitch bars make clear what is a sub-proof here; they let us see this as a direct derivation with a conditional derivation embedded in it.  This is an important concept:  we can have proofs within proofs.

An important principle is that once a subproof is done, we cannot use any of the lines in the subproof.  We need this rule because conditional derivation allowed us to make a special assumption that we use only temporarily.  Above, we assumed P.  Our goal is only to show that if P is true, then R is true.  But perhaps P isn’t true.  We do not want to later make use of P for some other purpose.  So, we have the rule that when a subproof is complete, you cannot use the lines that occur in the subproof.  In this case, that means that we cannot use lines 3, 4, or 5 for any other purpose than to show the conditional (P→R).  We cannot now cite those individual lines again.  We can, however, use line 6, the conclusion of the subproof.

The Fitch bars—which we have used before now in our proofs only to separate the premises from the later steps—now have a very beneficial use.  They allow us to set aside a conditional derivation as a subproof, and they help remind us that we cannot cite the lines in that subproof once the subproof is complete.

It might be helpful to give an example of why this is necessary.  That is, it might be helpful to give an example of an argument made invalid because it makes use of lines in a finished subproof.  Consider the following argument.

If you are Pope, then you have a home in the Vatican.

If you have a home in the Vatican, then you hear church bells often.

_____

If you are Pope, then you hear church bells often.

That is a valid argument, with the same form as the argument we adopted from Hobbes.  However, if we broke our rule about conditional derivations, we could prove that you are Pope.  Let’s use this key:

S:  You are Pope.

T:  You have a home in the Vatican.

U:  You hear church bells often.

Now consider this “proof”:

\[

\fitchprf{\pline[1.]{(S \lif T)} [premise]\\
\pline[2.]{(T \lif U))} [premise]\\
}
{
\subproof{\pline[3.]{S}[assumption for conditional derivation]}{
\pline[4]{T}[modus ponens, 1, 3]\\
\pline[5.]{U}[modus ponens, 2, 4]
}
\pline[6.]{(S \lif U)}[conditional derivation, 3-5]\\
\pline[7.]{S}[repeat, 3]
}

\]

And, thus, we have proven that you are Pope.  But, of course, you are not the Pope.  From true premises, we ended up with a false conclusion, so the argument is obviously invalid.  What went wrong?  The problem was that after we completed the conditional derivation that occurs in lines 3 through 5, and used that conditional derivation to assert line 6, we can no longer use those lines 3 through 5.  But on line 7 we made use of line 3.  Line 3 is not something we know to be true; our reasoning from lines 3 through line 5 was to ask, if S were true, what else would be true?  When we are done with that conditional derivation, we can use only the conditional that we derived, and not the steps used in the conditional derivation.

6.3  Some additional examples

Here are a few kinds of arguments that help illustrate the power of the conditional derivation.

This argument makes use of conjunctions.

(P→Q)

(R→S)

_____

((P^R)→(Q^S))

We always begin by constructing a direct proof, using the Fitch bar to identify the premises of our argument, if any.

\[
\fitchprf{\pline[1.]{(P \lif Q)} [premise]\\
\pline[2.]{(R \lif S)} [premise]\\
}
{
}
\]

Because the conclusion is a conditional, we assume the antecedent and show the consequent.

\[

\fitchprf{\pline[1.]{(P \lif Q)} [premise]\\
\pline[2.]{(R \lif S)} [premise]\\
}
{
\subproof{\pline[3.]{(P \land R)}[assumption for conditional derivation]}{
\pline[4]{P}[simplification, 3]\\
\pline[5.]{Q}[modus ponens, 1, 4]\\
\pline[6.]{R}[simplification, 3]\\
\pline[7.]{S}[modus ponens, 2, 6]\\
\pline[8.]{(Q \land S)}[adjunction, 5, 7]
}
\pline[9.]{((P \land R) \lif (Q \land S))}[conditional derivation, 3-8]

}
\]

Here’s another example.  Note that the following argument is valid.

(P→(S→R))

(P→(Q→S))

_____

(P→(Q→R))

The proof will require several embedded subproofs.

\[
\fitchprf{\pline[1.]{(P \lif (S \lif R))} [premise]\\
\pline[2.]{(P \lif (Q \lif S))} [premise]\\
}
{
\subproof{\pline[3.]{P}[assumption for conditional derivation]}{
\subproof{\pline[4.]{Q} [assumption for conditional derivation]}{
\pline[5.]{(Q \lif S)}[modus ponens, 2, 3]\\
\pline[6.]{S}[modus ponens, 5, 4]\\
\pline[7.]{(S \lif R)}[modus ponens, 1, 3]\\
\pline[8.]{R}[modus ponens, 7, 6]
}
\pline[9.]{(Q \lif R)}[conditional derivation, 4-8]
}
\pline[10.]{(P \lif (Q \lif R))}[conditional derivation, 3-9]

}
\]

6.4  Theorems

Conditional derivation allows us to see an important new concept.  Consider the following sentence:

((P→Q) →(¬Q→¬P))

This sentence is a tautology.  To check this, we can make its truth table.

This sentence is true in every kind of situation, which is what we mean by a “tautology”.

Now reflect on our definition of “valid”:  necessarily, if the premises are true, then the conclusion is true.  What about an argument in which the conclusion is a tautology?  By our definition of “valid”, an argument with a conclusion that must be true must be a valid argument—no matter what the premises are!  (If this confuses you, look back at the truth table for the conditional.  Our definition of valid includes the conditional: if the premises are true, then the conclusion is true.  Suppose now our conclusion must be true.  Any conditional with a true consequent is true.  So the definition of “valid” must be true of any argument with a tautology as a conclusion.)  And, given that, it would seem that it is irrelevant whether we have any premises at all, since any will do.  This suggests that there can be valid arguments with no premises.

Conditional derivation lets us actually construct such arguments.  First, we will draw our Fitch bar for our main argument to indicate that we have no premises.   Then, we will construct a conditional derivation.  It will start like this:

\[
\fitchprf{}
{
\subproof{\pline[1.]{(P \lif Q)}[assumption for conditional derivation]}{
}

}
\]

But what now?  Well, we have assumed the antecedent of our sentence, and we should strive now to show the consequent.  But note that the consequent is a conditional.  So, we will again do a conditional derivation.

\[
\fitchprf{}
{
\subproof{\pline[1.]{(P \lif Q)}[assumption for conditional derivation]}{
\subproof{\pline[2.]{\lnot Q} [assumption for conditional derivation]}{
\pline[3.]{\lnot P}[modus tollens, 1, 2]\\
}
\pline[4.]{(\lnot Q \lif \lnot P)}[conditional derivation, 2-3]
}
\pline[5.]{((P \lif Q) \lif (\lnot Q \lif \lnot P))}[conditional derivation, 1-4]

}

\]

This is a proof, without premises, of ((P→Q)→(¬Q→¬P)).  The top of the proof shows that we have no premises.  Our conclusion is a conditional, so, on line 1, we assumed the antecedent of the conditional.  We now have to show the consequent of the conditional; but the consequent of the conditional is also a conditional, so we assumed its antecedent on line 2.   Line 4 is the result of the conditional derivation from lines 2 to 3.  Lines 1 through 4 tell us that if (P→Q) is true, then (¬Q→¬P) is true.  And that is what we conclude on line 5.

We call a sentence that can be proved without premises a “theorem”.  Theorems are special because they reveal the things that follow from logic alone.  It is a very great benefit of our propositional logic that all the theorems are tautologies.  It is an equally great benefit of our propositional logic that all the tautologies are theorems.  Nonetheless, these concepts are different.  “Tautology” refers to a semantic concept:  a tautology is a sentence that must be true.  “Theorem” refers to a concept of syntax and derivation:  a theorem is a sentence that can be derived without premises.

Theorem:  a sentence that can be proved without premises.

Tautology:  a sentence of the propositional logic that must be true.

6.5  Problems

1. Prove the following arguments are valid.  This will require conditional derivation.

1. Premise:  (P→Q), (S→R).  Conclusion:  ((¬Q ^ ¬R) → (¬P ^ ¬S).
2. Premise:  (P→Q).  Conclusion: ((P ^ R) →Q).
3. Premise:  ((R^Q) → S), (¬P→(R^Q)).  Conclusion: (¬S→P).
4. Premise:  (P→¬Q).  Conclusion:  (Q→¬P).
5. Premises:  (P→Q), (P→R).  Conclusion:  (P→(Q^R))).
6. Premises:  (P→(Q→R)), Q.  Conclusion:  (P→R).

2. Prove the following theorems.

1. (P→P).
2. ((P → Q) → ((R → P) → (R → Q))).
3. ((P → (Q→R)) → ((P → Q) → (P → R)).
4. ((¬P→Q) → (¬Q→P)).
5. (((P→Q) ^ (P→R)) → (P→(Q^R))).

3. Make a truth table for each of the following complex sentences, in order to see when it is true or false.  Identify which are tautologies.  Prove the tautologies.

1. ((P → Q) → Q).
2. (P → (P → Q)).
3. (P → (Q → P)).
4. (P→¬P).
5. (P→¬¬P).

4. In normal colloquial English, write your own valid argument with at least two premises and with a conclusion that is a conditional. Your argument should just be a paragraph (not an ordered list of sentences or anything else that looks like formal logic).  Translate it into propositional logic and prove it is valid.