Lecture Notes 6: Conditional and Indirect Derivations

The Conditional Derivation Method (CD)

We have both In and Out rules for all our connectives, except for the arrow.

There is no →I rule!

This makes deriving the conclusion of arguments with SHOW lines that contain arrows nearly impossible.

We now introduce a new way of proving if-then statements. It is not simply a new derivation rule, but a new style of proof.

The basic idea of conditional derivation is that in order to prove that 𝒜 → ℬ, i.e., that if 𝒜  is true, then ℬ  is true, we can take the strategy of assuming temporarily that 𝒜  is true and deriving ℬ  from that assumption.

If we can prove that ℬ  is true by assuming 𝒜 , we know that if 𝒜  were true, ℬ  would have to be true as well, and so, that 𝒜 → ℬ .

Conditional derivation will work when (and only when) our problem contains an if-then statement in the SHOW line. Consider:

We can’t prove this only using the other rules. Instead, we write “CD” for conditional derivation, and then, at line 4, we assume that P is true. Finally, we change what we’re trying to prove.

Once we assume P, we introduce a new SHOW line, because now we’re going to try to show R on the basis of that assumption. (Online, you can introduce a new SHOW line using the second button at the bottom of the current subderivation.)

This gets set up like this:

(“Ass” for “assumption”.)

Now, we do a little “proof within a proof”. In other words, we try to show R, using line 4 (P) as an assumption. This uses DD rules, so we have written in “DD” for the inner SHOW line.

(Each new SHOW line comes along with a new “subderivation box” online to represent this proof within a proof.)

Note that because line 5 is a SHOW line; we cannot use it in our derivation.

We end up drawing a little box within a box. With P as an assumption, the mini-derivation of R is quite easy.

We have now shown R in the normal way. So I have crossed off that “SHOW”.

Where are we now?

We have assumed P, and have successfully shown R on the basis of that assumption.

We are now entitled to regard ourselves as having shown P → R and can cross off the “SHOW” at line 3.

That’s the way CD works.

The final problem looks like the answer to the problem below. (Try it yourself first.)

One thing that is important to remember is that, once a new SHOW line is introduced, your task has changed. You should focus on proving what it says to prove at the new SHOW line, and forget for the moment about trying to get the final conclusion.

Here are some additional examples.

Sometimes when we introduce a new SHOW line as part of a CD, the new SHOW line will itself be an if-then statement. If so, we may do a conditional derivation within a conditional derivation.

We can use CD whenever we wish to prove a conditional (if-then) statement.

It does not need to be the final conclusion of our argument; we may do it as an intermediate step. However, we do need to have the conditional we wish to prove as a SHOW line.

We are allowed to introduce new SHOW lines whenever we wish.

Once we cross-off the “SHOW” of the newly introduced “SHOW” line we can then use it as though it were a normal line.

However, once a box has been drawn around some lines, we cannot use those lines again in our derivation. Examples:

Here, we used CD in proving the SHOW line at line 3, but the ultimate conclusion, the SHOW line at line 2, was not proven by CD, but by →O, which is DD rule, so we write “DD” at 2, and “CD” at line 3.

This basic procedure allows us to use multiple CDs, combined with ↔I, to prove biconditional (iff) statements.

We first prove the conditional one way, and then the other. Then we put them together.

Indeed, this happens so often that Prof. Hardegree has, after his book was published, decided to give it an abbreviation: ↔D. You can use this whenever the SHOW line is a ↔-statement. If you have a crossed-out SHOW line for each direction on the inside, you can cross-off the ↔ SHOW line as well, skipping the ↔I rule.

We can rewrite the above as:

Another:

Lastly, there is a special rule, called “R” for “Repetition”, that we can use if, for some reason, we need to repeat something we already know on a later line—e.g., if needed on a line within a subderivation.

Example:

This rule is not needed very often.

The Indirect Derivation Method (ID)

Indirect derivation, like conditional derivation, is a wholly new way of setting up a proof.

Indirect derivation is used to show that something couldn’t possibly be true, because if it were true, it would lead to something absurd or impossible. Another name for it is “proof by contradiction”, or in Latin, “reductio ad absurdum” (RAA), meaning “reduction to absurdity”.

To do an ID, we first assume that something is true. We then show that this assumption leads to a contradiction, i.e., it leads to something being both true and false.

We then conclude that what we assumed must not be true.

We now introduce a special symbol, “✖”, which we use to signify “the absurd” or the “impossible”.

We then allow ourselves to introduce this in a proof, whenever we get a contradiction, by means of the following rule (✖-In):

The basic structure of an indirect proof is to assume the opposite of what we’re trying to prove, and derive a contradiction. I.e., to show ~𝒜, we assume 𝒜, and show ✖.

Consider the following example. We write “ID” for the show-rule. We then assume A and add a new SHOW line to show the absurd (✖).

We’ll get ✖ by DD. We can do this by showing any contradiction. (Any contradiction will do. It need not be the opposite of what we assumed.)

Once we get ✖ on a line by ✖I, we can cross off the inner SHOW line.

Having shown that a contradiction results when we assume A is true, we can safely conclude that A is false, by ID.

Here is the final problem.

Indirect derivation is very powerful. It can be used for almost any type of problem, and even when what we’re trying to prove is complex.

Here are some additional examples.

(There are quite often multiple ways of doing these problems. E.g., on this last one, at line 11, we could have used 7 and 10 to get Q instead of 3 and 10 to get ~P. This would also have given us a different contradiction (lines 3 and 11). Either way you do it is fine.)

There are, strictly speaking, two forms of indirect proof. The previous examples assume that something is true in order to prove that it is false.

We can also assume that something is false in order to prove that it is true.

This form works almost exactly the same.

We can do indirect derivations within conditional derivations (or, more rarely, vice-versa).

(Remember we can introduce SHOW lines whenever we wish.)

Often, it is helpful to do two indirect derivations in order to prove that a conjunction (and-statment) is true.

Again, this happens often enough that we abbreviate it as &D. A & SHOW line justified by &D can be crossed off if there are crossed-off SHOW lines for each conjunct inside its box. So we can rewrite the above this way, skipping the &I step:

✖I has a companion Out rule, which amounts to the result that anything follows from a contradiction.

However, we never need to use this rule.