Method 35

Use proof by contradiction.

Class of Method

  A Primary Proof Strategy.

Use When

When the problem gives you little to work with to manipulate mathematics to prove your theorem, or when the desired conclusion has the word "no" or "not" in it [39].

How

1.  Assume the opposite of the conclusion.  

2.  Then restart the problem-solving process with the added information where what you "want" is to imply any false statement from the information in the problem.

3.  Go to method 7 (experimentation) using the information in the problem including the assumed opposite of the conclusion, and search for information in that subroutine that you know is false or is likely false.  

4.  Try to prove the false statement using general problem-solving skills.

5.  If the previous step does not give you relatively quick success, then add to your strategy to also search for any information that can be implied by "working forwards" from the given information in the problem including the opposite of the conclusion.  You do this by searching for any statements that can be implied from the information that would be false thus allowing you to obtain a contradiction.

6.  Taking into account your success or failure of applying this method, choose the next heuristic (method) you will use based upon good defeasible reasoning or by using the general method given on page 100.

Example

See example problems 5 and 7 of chapter 6 (Examples of Problem Solving)

Method 36

Use proof by contra-positive.  This means that if you are trying to show that , then proving  proves that  due to that fact that  which says that these are logically equivalent statements.

Class of Method

  A Primary Proof Strategy.

Use When

When the conclusion you are to prove has "no" or "not" in it [39], or when proving  has proven difficult.

How

1.  Assume the opposite of the conclusion (i.e. ).

2.  Then restart the problem-solving process for this new problem.

3.  Taking into account your success or failure of applying this method, choose the next heuristic (method) you will use based upon good defeasible reasoning or by using the general method given on page 100.

Method 37

Apply methods of showing uniqueness.

Use When

When the conclusion you are trying to prove is about uniqueness.

How

Use one of the following methods given your information:

Sub-Method I)  Suppose there are two entities with the unique defining properties you want to show and restart the problem-solving process of showing that they are either equal or imply some other contradiction using the assumptions (i.e. given information) in the problem.

Sub-Method II)  Consider how you could reformulate the problem to an equivalent problem of other theorems about uniqueness, etc.

-Taking into account your success or failure of applying this method, choose the next heuristic (method) you will use based upon good defeasible reasoning or by using the general method given on page 100.

Example

See example problem 14 of chapter 6 (Examples of Problem Solving).

Method 38

Construct the entity you need to show exists.

Use When

When other methods of showing existence are difficult to use such as the extremal principle, the pigeonhole principle, or completeness of sets.  Also do this whenever your problem asks for the specific construction of an entity, or you need to find the specific entity as part of solving another problem.

How

-Start at the beginning of the problem-solving process with your problem of construction excluding the pigeonhole and extremal principles from being primary methods to solve your problem.

Notes

Using the method of construction means you create the entity you wish to show exists, or you give an algorithm that guarantees the creation of the entity from the information you have available in the problem.  It is solving to find the specific defining properties of the entity.  

Other useful theorems exist for showing existence that do not use construction directly such as theorems about existence—especially completeness theorems and axioms, fixed point theorems, etc.

Method 39

Use the pigeonhole principle.

Class of Method

A common strategy for showing existence.

Use When

When showing that there exists an element of a finite set with property Q, or if you can restate your problem into a statement of existence of an element of a finite set with property Q.

How

1.  Consider the (n) entities of which you want to show at least one of those entities as having a specific property Q.  Consider what property P that if true for two of the (n) entities would imply that property Q held for at least one of those two entities.

2.  Restart the problem-solving process on the following sub-problem:  Consider how you could separate all possible specifications of those (n) entities into (n - 1) classes where if two of the (n) entities are in the same class, then both of those in that class would have property P.  Do this by considering what restrictions (or various possible different combinations of restrictions for different classes) would force property P on two items if both were in that class.  Then consider how to separate all possible specifications of the (n) entities into (n - 1) classes with any of the possible combinations of restrictions that would force property P on two items that were in the same class.

3.  If the previous step proves difficult for the P chosen in step (1), then go back to step (1) and find another P that would make step (2) easier to do successfully.

4.  By the pigeonhole principle, two elements exist with property P, and therefore at least one element with property Q.

5.  Taking into account your success or failure of applying this method, choose the next heuristic (method) you will use based upon good defeasible reasoning or by using the general method given on page 100.

Notes

There is a (less commonly used) strong form of the pigeonhole principle whose process is similar to that above.

This method does not find the element of a finite set with property Q—it only shows that there is an element with property Q.

Example

See example problems 15 and 16 of chapter 6 (Examples of Problem Solving).

Method 40

Use proof by induction.

Class of Method

A common proof strategy.

Use When

When there is a pattern or relationship you have observed that is a function of the counting numbers n = 1, 2, 3, 4…

How

1.  Solve the sub-problem of proving that the pattern or relationship holds true for n = 1.

2.  Solve the sub-problem of proving that if the pattern or relationship holds true for n, then it holds true for n+1.

3.  The statement is true for all n by induction.

4.  Taking into account your success or failure of applying this method, choose the next heuristic (method) you will use based upon good defeasible reasoning or by using the general method given on page 100.

Example problem

See example problem 17 of chapter 6 (Examples of Problem Solving).

Method 41

Cantor diaganolization

Class of Method

A specialized problem-solving method.

Use When

When proving uncountability.

Method 42

Method of infinite descent

Class of Method

A specialized problem-solving method.

Use When

When a Diophantine equation is involved.  

How

-Create and follow a plan similar to the example 5 of chapter 6 (Examples of Problem Solving).

Notes

This method centers on proof by contradiction combined with use of the extremal principle.

Method 43

Jeopardy proof

Class of Method

A specialized problem-solving method.

Use When

When proving combinatorial identities and both sides of the desired identity are complicated examples of combinatorial counting.

How

-Consider what one side of the equation is counting in various types of problems that the other side of the identity could likely be constructed as counting the same circumstance.

-Restart the problem-solving process on each of these new given sub-problems.