Big Assumption with Conditional and Indirect Proofs

Conditional proof and indirect proof involve an assumption, which is an additional premise that you don’t know is true but you assume is true.

Conditional Proof

Understanding conditional proof

Conditional proof allows you to use part of the conclusion as a premise that you can use to prove the rest of the conclusion.

To prove the validity of an argument whose conclusion is in the form x → y (that is, any →-statement), you can follow these steps:

1. Detach the sub-statement x.
2. Add x to your list of premises as an assumed premise (AP).
3. Prove the sub-statement y as if it were the conclusion.

 

\begin{align*} P \rightarrow \neg Q, P \vee \neg R: Q\rightarrow ((\neg P \wedge \neg R) \vee Q \rightarrow P) \end{align*}

Proof:

\begin{align*} &1 \quad P \rightarrow \neg Q \tag P \\ &2 \quad P \vee \neg R \tag { P } \\ &3 \quad Q \tag{ AP} \\ &4 \quad \neg P \tag{ 1,3 MT } \\ &5\quad \neg R \tag{ 2,4 DS } \\ &6\quad \neg P \wedge \neg R \tag{ 4,5 Conj } \\ &7 \quad (\neg P \wedge \neg R) \vee (Q\rightarrow P) \tag { 6 Add } \\ &8 \quad Q \rightarrow ((\neg P\wedge \neg R) \vee (Q\rightarrow P) \tag { 3,7 CP } \end{align*}

 

Flipping conclusion with Contra

To take full advantage of this section, you have to first remember that you can use every →-statement in two ways: The way it is and in its Contra form.

 

\begin{align*} P \rightarrow Q, R \vee (Q\rightarrow P):\neg (P \leftrightarrow Q)\rightarrow R \end{align*}

Proof:

\begin{align*} &1 \quad P \rightarrow Q \tag { p } \\ &2 \quad R \vee (Q\rightarrow P) \tag { p } \\ &3 \quad \neg R \tag{ AP } \\ &4 \quad Q \rightarrow P \tag{ 2,3 DS } \\ &5\quad (P \rightarrow Q) \wedge (Q \rightarrow P) \tag{ P } \\ &6\quad P \leftrightarrow Q \tag{5 Equiv } \\ &7 \quad \neg R \rightarrow (P \leftrightarrow Q) \tag {3-6 CP } \\ &8 \quad \neg (P \leftrightarrow Q) \rightarrow R \tag { 7 Contra } \end{align*}

 

Winning through implication

You can also turn any $\vee$-statement into a →-statement by using Impl . Using Impl makes any 0-statement a potential candidate for conditional proof.

 

\begin{align*} P:\neg R\vee(Q\rightarrow(P\wedge R)) \end{align*}

Proof:

\begin{align*} &1 \quad P \tag { P } \\ &2 \quad R\wedge Q \tag { AP } \\ &3 \quad R \tag{ 2 Simp } \\ &4 \quad P \wedge R \tag{ 1,3 Conj } \\ &5\quad (P \wedge Q )\rightarrow(P\wedge Q) \tag{ 2-4 CP } \\ &6\quad R \rightarrow(Q\rightarrow(P\wedge R)) \tag{ 5 Exp } \\ &7 \quad \neg R \vee (Q\rightarrow(P\wedge R)) \tag { 6 Impl } \end{align*}

 

Stacking assumptions

After you assume a premise, if the new conclusion is a →-statement (or can be turned into one), you can assume another premise. This is nice way to get two (or more!) assumptions for the price of one. Here’s an example:

\begin{align*} \neg Q \vee R: (P\vee R)\rightarrow ((Q\wedge S)\rightarrow (R\wedge S)) \end{align*}

Proof:

\begin{align*} &1 \quad \neg Q \vee R \tag { P } \\ &2 \quad (P\vee R) \tag { AP } \\ &3 \quad Q\wedge S \tag{ AP } \\ &4 \quad Q \tag{3 Simp } \\ &5 \quad S \tag{3 Simp } \\ &6 \quad R \tag{ 1,4 DS} \\ &7 \quad R \wedge S \tag { 5.6 Conj } \\ &8 \quad (Q\wedge S)\rightarrow (R\wedge S) \tag { 3-7 CP } \\ &9 \quad (P\vee R)\rightarrow ((Q\wedge S)\rightarrow (R\wedge S)) \tag{ 2-8 CP } \end{align*}

 

 

Indirect Proof

Introducing indirect proof

Indirect proof (also called proof by contradiction) is a type of logical judo. The idea here is to assume that the conclusion is false and then show why this assumption is wrong. Success means that your conclusion was true all along.

To prove that any argument is valid, you can follow these steps:

1. Negate the conclusion.
2. Add the negation to your list of premises as an assumption.
3. Prove any contradictory statement (any statement of the form $x \wedge \neg x$).

 

\begin{align*} P\rightarrow(Q\wedge \neg R), R: \neg (P\vee \neg R) \end{align*}

Proof:

\begin{align*} &1 \quad P\rightarrow(Q\wedge \neg R) \tag { P } \\ &2 \quad R \tag { P } \\ &3 \quad P\vee \neg R \tag{ AP } \end{align*}

Your goal now is to prove a statement and its negation, then use them to build a contradictory $\wedge$-statement, like this:

\begin{align*} \\ &4 \quad P \tag{ 2,3 DS } \\ &5\quad Q \wedge \neg R \tag{ 1,4 MP } \\ &6\quad \neg R \tag{ Simp } \end{align*}

At this point, you’ve derived both R and $\neg R$, so you can build them into a single contradictory statement as follows:

\begin{align*} \\ &7 \quad R\wedge \neg R \tag { 2,6 Conj } \end{align*}

The assumption has led to an impossible situation, so you know that the AP must be false. If $P\vee \neg R$ is false, then $\neg (P\vee \neg R)$ must be true:

\begin{align*} &8 \quad \neg (P\vee \neg R) \tag { 3-7 IP } \end{align*}

Proving short conclusions

As I mention in Chapter 9, arguments where the conclusion is shorter than the premises tend to be more difficult to prove than those where the conclusion is longer, because breaking down long premises can be tricky.

However, indirect proof works especially well when the conclusion is shorter than the premises because the negated conclusion becomes a nice short premise for you to use. For example, consider this argument:

\begin{align*} \neg ((\neg P \vee Q)\wedge R)\rightarrow S,P\vee \neg R, \neg Q \vee S:S \end{align*}

Proof:

\begin{align*} &1 \quad \neg ((\neg P \vee Q)\wedge R)\rightarrow S \tag { P } \\ &2 \quad P\vee \neg R \tag { P } \\ &3 \quad \neg Q \vee S \tag{ P } \\ &4 \quad \neg S \tag{AP } \\ &5 \quad (\neg P \vee Q) \wedge R \tag{ 1,4 MT } \\ &6 \quad \neg P \vee Q \tag{5 Simp } \\ &7 \quad R \tag { 5 Simp } \\ &8 \quad P \tag { 2,7 DS } \\ &9 \quad Q \tag{ 6,8 DS } \\ &10 \quad S \tag{ 3,9 DS } \end{align*}

Remember: When you’re doing an indirect proof, don’t be fooled into thinking you’re done after you prove the conclusion. Remember that you also need to build a contradictory statement.

In this case, the AP leads to its own negation, which allows you to complete the proof:

\begin{align*} \\ &11 \quad S \wedge \neg S \tag { 4,10 Conj } \\ &12 \quad S \tag { 4-11 CP} \end{align*}

Superficially, line 12 looks like line 10, but now you’ve discharged the AP, so the proof is complete.

 

Combining Conditional and Indirect Proofs

\begin{align*} \neg P \wedge Q\rightarrow(\neg R \wedge S), Q: R\rightarrow P \end{align*}

Proof:

\begin{align*} &1 \quad \neg P \wedge Q\rightarrow(\neg R \wedge S) \tag { P } \\ &2 \quad Q \tag { P } \\ &3 \quad \neg (\neg P \wedge Q) \vee (\neg R \wedge S) \tag{1 Impl } \\ &4 \quad R \tag{AP (for conditional proof) } \\ &5 \quad \neg P \tag{AP (for indirect proof) } \end{align*}

Now the goal is to find a contradiction:

\begin{align*} \\ &6 \quad \neg P \wedge Q \tag{ 2,5 Conj } \\ &7 \quad \neg R \wedge S \tag { 1,6 MP } \\ &8 \quad \neg R \tag { 7 Simp } \end{align*}

Now you’re ready to discharge the AP for the indirect proof:

\begin{align*} \\ &9 \quad R\wedge \neg R \tag{ 4,8 Conj } \\ &10 \quad P \tag{ 5-9 IP } \\ &11 \quad R\rightarrow P \tag{4-10 CP } \end{align*}

When using conditional and indirect proof methods together, discharge your APs starting with the last one you added (here, AP of indirect proof is the last one) and work your way back to the first.