Conditional & Indirect Proofs

This is a work-in-progress. I will be updating this often!

It’s my sincere hope that my website will be useful to you. Logic is a wonderful “science” to learn and, of course, to practice and apply.

Please take a look at my tutorial. It will give you the tools to master logic.
If you profit from it or enjoy it, please consider supporting my work.

— George Wick

Introduction
Conditional Proofs (CP)
4 examples of conditional proofs
Indirect Proofs (IP)
3 examples of indirect proofs (a.k.a. reductio ad absurdums)

Introduction

Propositional logic allows us to prove arguments in a truth table or deductively using the basic rules of inference and basic rules of logical equivalency. Assuming the premises we start with are true, a valid argument will lead to a true conclusion. Deductive proofs are formally constructed where each derivation is explicitly listed and justified step-by-step.

Direct proofs are sometimes very difficult.
And a direct proof might actually be impossible to construct.
Yet we luckily have more techniques to help us!

Conditional proofs allow us to make assumptions. Based on the assumption of the proposition Φ, we might be able to derive, based on Φ and our given premises P1, P2, …, Pn, the proposition ψ. When that’s the case, we can conclude that Φ→ψ. That is, if the assumption is true, then what follows from that assumption will be true.

Indirect proofs, similarly, make assumptions. Based on the assumption of the proposition Φ, we might be able to derive, based on Φ and our given premises P1, P2, …, Pn, the proposition of the form ψ& ~ψ. Since ψ& ~ψ is a contradiction, it cannot be true. What led to it, also, cannot be true because it entails a contradiction. Therefore, we conclude ~Φ.

Anytime we make assumptions, we need to “quarantine” them. In a proof, we can make any assumptions we like, though we need to mark them as such. And anything derived from an assumption must be marked as such. (We’ll see this with the examples below).

Conditional Proofs

Example 1. . .

Premise: “If Michelle goes to Chicago, then Justin goes to Chicago.”
Premise: “If Anthony goes to Tampa, then Justin doesn’t go to Chicago.”
Conclusion: “Thus, if Anthony goes to Tampa, Michelle doesn’t go to Chicago.”

There’s no easy way to formally prove this without using a conditional proof!
Let’s first “translate” it into the language of propositional logic:
M→J, A→~J ⊢ A→~M

With a conditional proof, this is actually quite easy.

The moment we make an assumption in a proof, we must “quarantine” it. For our purposes, the assumption zone is underlined and indented.

Based on the assumption (ASSUM) of A, we were able to eventually derive ~M.

Thus, we can, by a conditional proof (CP), infer that A→~M with lines 3 to 5.

This proof makes intuitive sense, correct? I think so. Just assume that Anthony goes to Tampa. If he does, then Justin doesn’t go to Chicago; but, if Justin doesn’t go to Chicago, then Michelle doesn’t go to Chicago. Therefore, if Anthony goes to Tampa, then Michelle doesn’t go to Chicago.

This example shows “real world” relevancy! It’s not just a game of moving around symbols. A conditional proof can be applied to real life situations.

Example 2. . .

“Either the witness is not telling the truth or Brown was home by eleven. If Brown was home by eleven then he saw his uncle. If he saw his uncle then he knows who was there earlier. Therefore, if the witness is telling the truth then Brown knows who was there earlier.”

This is borrowed from First Course in Mathematical Logic by Patrick Suppes and Shirley Hill on page 135.

Let’s first “translate” it into the language of propositional logic:
~WvB, B→U, U→E ⊢W→E

In this proof, we didn’t start with a conditional proof (CP) from the outset, but that’s OK.

We assumed (ASUM) W on line 5. Lines 5 to 8 are in “quarantine.” From W we eventually were able to derive E.

Thus, by a conditional proof (CP), we were able to reach the conclusion W→E.

The argument was a kind of “puzzle.” Imagine if it were more difficult! Symbolic logic can help us simplify matters.

It’s a pretty cool argument.

Example 3. . .
Premise: P→(Q→R)
Premise: P→(S→R)
Premise: ~R
Conclusion: P→~(QvS)

In this proof, we started right away with the assumption of P.

Via a series of derivations with our basic rules of inference, we then reached ~(QvS).

Thus, by a conditional proof, we reached P→~(QvS).

Not too bad.

Example 4. . .
Premise: PvQ→(R→S&T)
Premise: TvQ→U
Conclusion: P→(R→U)

Sometimes we need to make assumptions within assumptions!

That we had to prove P→(R→U) itself indicated that possibility because we have a conditional within a conditional.

In this proof, we assumed P. Within that we assumed R. This second assumption is within the first and so it is indented more.

Notice that we got R→U with our conditional proof with lines 4 to 11. Then we got P→(R→U) with our conditional proof with lines 3 to 12.

Indirect Proofs (Reductio ad Absurdum)

An indirect proof can, in some sense, be thought of as a special case of the conditional proof. That’s because it starts out with an assumption. That assumption, however, leads to a contradiction. We could think of it as setting up this conditional: Φ→ψ&~ ψ.

Since ψ&~ ψ is a contradiction, Φ cannot be true and, therefore, this must mean that ~Φ is true. By the Law of Excluded Middle, a proposition must either be true or false (exclusively). This means that if Φ is false, then ~Φ is true.

Such a basic law of thought — for example, the Law of Excluded Middle — is fundamental!

Example 5. . .
“If God changes, then he changes for the worse or for the better. If he changes for the better, then he isn’t perfect. If he’s perfect, then he doesn’t change for the worse. Therefore, if God is perfect, he doesn’t change.”

This is borrowed from Harry Gensler’s Introduction to Logic on page 160.

Let’s “translate” it into the language of propositional logic:
C→WvB, B→~P, P→~W ⊢ P→~C

Like any indirect proof, we’ll assume the contradictory of what we desire to prove.

So, we’ll assume ~(P→~C). Because it’s an assumption, we’ll place what’s derived from it in “quarantine.”

Our goal, with any indirect proof, is to derive a contradiction. Using our rules of inference and rules of replacement, we can derive P and ~P. On line 15 we put them together in a conjunction to explicitly state the contradiction derived.

Remember, the assumption leading to that contradiction must be false.

Outside of “quarantine,” we state our derivation through the indirect proof of ~~(P→~C). Via double negation (DN) we get our conclusion of P→~C.

Example 6 . . .
Premise: PvQ→R&S
Premise: ~(S&P)
Conclusion: ~P

This indirect proof (IP) starts with assuming P, which is the contradictory of ~P. Sometimes we just have to “play” around to see what happens. With some luck, we might “spot” a contradiction.

We can do a modus ponens (MP) inference with our P if we form the PvQ with the addition rule. R&S can then be used as the basis to find our contradiction.

S&~S was derived based on the assumption of P. Hence, because P is false, ~P must be true.

There is no exact “recipe” in these proofs. Often, there is more than one way to prove a proposition.

Example 7. . .
Premise: P→Q&R
Premise: S→TvP
Premise: T→U&R
Conclusion: S→R

Just as we can do conditional proofs within conditional proofs, we can do indirect proofs within indirect proofs.

Proofs that require that are usually tricky. Consider this proof in its broad outline. First, there’s the main indirect proof from lines 4 to 23. Second, there’s an indirect proof within it from lines 12 to 17.

Sometimes to get what we want, we should assume! We wanted a T; so, we tried to see what happens when we assume ~T. A contradiction was derived; hence, we can use T to do the modus ponens (MP) inference to get that U&R.

It was that that allowed us to get our contradiction for the main indirect proof to arrive at the desired conclusion.

Try it on your own.