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

From Wikibooks, open books for an open world
Jump to navigation Jump to search

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[edit]

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 and in this case the symbol for a statement which is always true is . Perhaps the 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 , and in this case the symbol 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 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[edit]

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

implies

to be the definition of

not .

We've already given a definition of 'not ' 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

implies

is False when is True and True when is False. But the statement implies was defined to be False when is True and is False, and defined to be True when when is False and 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 deduce implies

and

From implies deduce not .

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

From , not deduce

and

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

Example Proof #1[edit]

Let's start by using the above rules to prove

Prop. 1: implies not not .

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 Hypothesis
(something)
n not not ?
n+1 implies not not From 1 and n

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

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

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

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

In prose form:

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

Example Proof #2[edit]

We prove

Prop. 2: ( implies ) implies (not implies not ).

For any implication implies , the implication not implies not 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 implies deduce that ( implies ) implies ( implies ).

This produces a simpler proof

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

Method of indirect proof[edit]

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 , 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 you can derive a contradiction, that is if not not , then you can deduce .

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

From not not deduce .

An alternate formulation is

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

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[edit]

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

Prop. 3: not not implies .

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

Prop. 4: (not implies not ) implies ( implies )

Start by constructing an outline as before.

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

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

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

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

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

To put this in prose form:

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

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[edit]

Prop. 5: not ( implies ) implies not
Prop. 6: not ( implies ) implies
Prop. 7: (( implies ) implies ) implies
Prop. 8: not implies ( implies )
Prop. 9: implies
Prop. 10: not