Indirect Proof (IP)

Indirect proof (IP), also called proof by contradiction, is the second new method. To show a statement is true, you assume it is false and show that leads to a contradiction. The layout is the same subproof you used in Conditional Proof (CP).

Key idea

To prove $A$ by IP: assume $\neg A$ (justified AIP) in a subproof. Derive a contradiction, a line of the form $q \land \neg q$. Close the subproof and write $A$, justified "IP i–j". (If you assumed $B$ instead, IP gives $\neg B$.)

Why it works

If the premises together with $\neg A$ lead to $q \land \neg q$, which is false in every row, then the premises and $\neg A$ cannot all be true. So whenever the premises are true, $\neg A$ is false, which means $A$ is true. IP is the formal version of "that can't be right, so the opposite must be".

Indirect proof: assume, reach q ∧ ¬q, conclude the negation of the assumption.

Worked examples

Worked example: Prove a letter

Premises $p \lor q$ and $\neg q$. Prove $p$ by IP.

Line 3: $\neg p$ (AIP).
Line 4: $q$ by DS 1, 3.
Line 5: $q \land \neg q$ by Conj 4, 2.
Line 6: $p$ by IP 3–5.

Answer: IP gives the opposite of the assumption $\neg p$, which is $p$.

Worked example: What to assume

You want $\neg (r \land s)$ by IP. What do you assume?

Assume the negation of the goal: $\neg \neg (r \land s)$.
IP also lets you assume $r \land s$ directly, since its negation is the goal.

Answer: $r \land s$ (or $\neg \neg (r \land s)$).

Worked example: Reaching the contradiction

Inside an IP subproof you have $t$ on line 5 and $\neg t$ on line 7. What next?

Join them by Conj.

Answer: $t \land \neg t$ by Conj 5, 7; then close with IP.

Common mistake

Stopping when you reach some line that looks false, such as $\neg p$ when you "know" $p$. The subproof must end in an explicit contradiction of the form $q \land \neg q$, written on one line. If you have $q$ and $\neg q$ on separate lines, use Conj to put them together before you close.

Any contradiction will do; it need not involve the letters of the conclusion.

Notice how IP differs from CP. CP proves a conditional and gives you something to aim for: the consequent. IP can prove anything, but the target inside the subproof is vaguer: any contradiction at all. A good strategy is to look for a formula and its negation that are both within reach, then aim for each of them.

IP is often the easiest way to prove a negation, or a simple letter that appears only deep inside the premises. When nothing else suggests itself, assume the opposite of the conclusion and look for two lines that clash.

Indirect Proof (IP)

Worked examples

Practice

Builds on

Leads to

Sources and further reading