Mathematical Proof and the Principles of Mathematics/Logic/Indirect proofs

In the previous section we looked at rules of inferences having to do with implication. Most theorems in mathematics take the form of an implication so these are very important. (In a sense, all theorems in mathematics take the form of an implication, but we'll get into that later.)

But there is much more to logic than implication, so we're going to need some additional rules of inferences for the other logical connectives. The most basic of these is the method of proof by contradiction.

Contradiction

We start by introducing the concept of a contraction. You can think of this as a statement which is known to be false. It is somewhat ironic that such a statement would play an important role in logic where the idea is to show certain statements are always true.

There are few logical symbols which mean a contradiction; one is $\bot$ and in this case the symbol for a statement which is always true is $\top$. Perhaps the $\top$ was chosen for its resemblance to the letter 'T' for True, and turning it upside-down is meant to indicate the opposite. Another symbol is $\Box$, and in this case the symbol $\blacksquare$ stands for a statement which is always true. Since we're avoiding the use of such symbols for the most part, we'll just spell out the word $False$ for proofs in tabular format. For proofs given in prose style, it's common to write something like "This is absurd," or "This is a contradiction." The word 'contradiction' itself comes from a Latin phrase meaning to 'speak against', referring to statements which each mean the opposite of other other.

Negation

It's possible to use implication and contradiction alone to 'define' all the remaining logical connectives. To start with, we can take the statement

$P$ implies $False$

to be the definition of

not $P$.

We've already given a definition of 'not $P$' in the section on logical connectives, and now we've created a new, competing definition. This is fine as long was we can be assured that the two definitions agree with each other. So we need to satisfy ourselves that the statement

$P$ implies $False$

is False when $P$ is True and True when $P$ is False. But the statement $P$ implies $Q$ was defined to be False when $P$ is True and $Q$ is False, and defined to be True when $P$ is False and $Q$ is False. So the definitions agree.

Given such a definition, we can create two new rules of inference. The first substitutes the defined expression for its definition, and the second makes the opposite substitution. So we have

From not $P$ deduce $P$ implies $False$

and

From $P$ implies $False$ deduce not $P$.

By combining these with rules from the previous page we get the more usable forms

From $P$, not $P$ deduce $False$

and

If by making the assumption $P$ one can derive $False$, then deduce not $P$.

Example Proof #1

Let's start by using the above rules to prove

Prop. 1: $P$ implies not not $P$.

This is an implication so we start by assuming the hypothesis and deriving the conclusion, so the proof takes the form

Line	Statement	Justification
1	$P$	Hypothesis
(something)
n	not not $P$	?
n+1	$P$ implies not not $P$	From 1 and n

The goal now is to prove not not $P$, but we can do that by assuming not $P$ and deriving a contradiction. The new form of the proof is

Line	Statement	Justification
1	$P$	Hypothesis
2	not $P$	Hypothesis
(something)
n−1	$False$	?
n	not not $P$	From 2 and n−1
n+1	$P$ implies not not $P$	From 1 and n

At this point we need to prove $False$, but the statements $P$ and not $P$ are already assumed, so it's just a matter of filling in the final touches.

Line	Statement	Justification
1	$P$	Hypothesis
2	not $P$	Hypothesis
3	$P$	Iterating 1
4	$False$	Contradiction between 2 and 3
5	not not $P$	From 2 and 4
6	$P$ implies not not $P$	From 1 and 5

In prose form:

Prop. 1: $P$ implies not not $P$.

Proof: Assume $P$. Now assume not $P$. We have both not $P$ and $P$ by the original assumption, which is a contradiction. So the assumption not $P$ must be false, in other words not not $P$. From the original assumption $P$ it follows that not not $P$, so we can conclude that $P$ implies not not $P$.

Example Proof #2

We prove

Prop. 2: ($P$ implies $Q$) implies (not $Q$ implies not $P$).

For any implication $P$ implies $Q$, the implication not $Q$ implies not $P$ is called its 'contrapositive'. As we shall see, the contrapositive is logically equivalent to the original implication, unlike the converse. Prop. 2 is the first step in proving that equivalence.

You can prove this from scratch, which is left as an exercise, but another approach is it use Prop. 5 on the previous page as a shortcut. Restated as a rule of inference, this proposition says

From $P$ implies $Q$ deduce that ($Q$ implies $R$) implies ($P$ implies $R$).

This produces a simpler proof

Line	Statement	Justification
1	$P$ implies $Q$	Hypothesis
2	not $Q$	Hypothesis
3	$Q$ implies $False$	Definition of 'not'
4	$P$ implies $Q$	Iterating 1
5	($Q$ implies $False$) implies ($P$ implies $False$).	4, Prop. 5 from previous page
6	$P$ implies $False$	From 3 and 5
7	not $P$	Definition of 'not'
8	not $Q$ implies not $P$	From 2 and 7
9	($P$ implies $Q$) implies (not $Q$ implies not $P$).	From 1 and 8

Method of indirect proof

We nearly have a very useful and important method of proof know as proof by contradiction, or for those who like Latin, Reductio ad absurdum which roughly translated mean reduction to the absurd. A proof that uses this method is called an indirect proof since it's not as straightforward as a so called direct proof which relies on the methods used up to now.

To use this method to prove a statement $P$, assume that it is false and then derive a contraction. If the assumption that a statement is false leads to an impossibility, then the statement must be other than false, or true. To put this another way, if by assuming not $P$ you can derive a contradiction, that is if not not $P$, then you can deduce $P$.

We'll restate this in the form of a new rule of deduction

From not not $P$ deduce $P$.

An alternate formulation is

If by making the assumption not $P$ one can derive $False$, then deduce $P$.

This is the last rule of inference which cannot be derived from definitions or other rules of inference. We will be defining disjunction, conjunction and equivalence as we did for negation, and those definitions produce two rules of inference each, but the can be derived by proving an implication as with Prop. 2 on the previous page.

Example proofs #3 and #4

To put this rule of inference to work, let's start with the converse to Prop. 1:

Prop. 3: not not $P$ implies $P$.

This is follows easily and the proof is left as an exercise.

Prop. 4: (not $Q$ implies not $P$) implies ($P$ implies $Q$)

Start by constructing an outline as before.

Line	Statement	Justification
1	not $Q$ implies not $P$	Hypothesis
2	$P$	Hypothesis
(something)
n−1	$Q$	?
n	$P$ implies $Q$	From 2 and n−1
n+1	(not $Q$ implies not $P$) implies ($P$ implies $Q$)	From 1 and n

At this point we need to prove $Q$ but direct proof doesn't seem to work, so assume not $Q$ and try to derive a contradiction.

Line	Statement	Justification
1	not $Q$ implies not $P$	Hypothesis
2	$P$	Hypothesis
3	not $Q$	Hypothesis
(something)
n−2	$False$	?
n−1	$Q$	From 3 and n−2
n	$P$ implies $Q$	From 2 and n−1
n+1	(not $Q$ implies not $P$) implies ($P$ implies $Q$)	From 1 and n

We now have enough assumptions to start filling in some inferences and complete the proof.

Line	Statement	Justification
1	not $Q$ implies not $P$	Hypothesis
2	$P$	Hypothesis
3	not $Q$	Hypothesis
4	not $Q$ implies not $P$	Iterating 1
5	not $P$	From 3 and 4
6	$P$	Iterating 2
7	$False$	From 5 and 6
8	$Q$	From 3 and 7
9	$P$ implies $Q$	From 2 and 8
10	(not $Q$ implies not $P$) implies ($P$ implies $Q$)	From 1 and 9

To put this in prose form:

Prop. 4: (not $Q$ implies not $P$) implies ($P$ implies $Q$)

Proof: Assume not $Q$ implies not $P$. Now assume $P$. We need to prove $Q$, so suppose otherwise, in other words not $Q$. Then not $P$ by the first assumption. But this together with the second assumption is a contradiction. The assumption not $Q$ leads to a contradiction so $Q$. Therefore $P$ implies $Q$. From the original assumption not $Q$ implies not $P$ it follows that $P$ implies $Q$, so we can conclude that (not $Q$ implies not $P$) implies ($P$ implies $Q$).

Note that, even though it's not strictly necessary, we stated what was to be proved next and inserted a little road sign in the form of 'suppose otherwise' to signal that an indirect argument is coming up. Other phrases that serve the same purpose may include 'assume not' and 'if false then'.

Left to the reader

Prop. 5: not ($P$ implies $Q$) implies not $Q$

Prop. 6: not ($P$ implies $Q$) implies $P$

Prop. 7: (($P$ implies $Q$) implies $P$) implies $P$

Prop. 8: not $P$ implies ($P$ implies $Q$)

Prop. 9: $False$ implies $Q$

Prop. 10: not $False$