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
editWe 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
editIt'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
editLet'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
editWe 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
editWe 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
editTo 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