Proofs are based in large part upon the Rules of Inference found in the text. Each transition from one statement to the next in a proof must be justified by one of these or other rules, axioms or previously proven theorems.

Common mistakes in reasoning are referred to as fallacies. The use of a fallacy always makes a proof invalid but does not necessarily mean that the statement to be proven is false. For example a man may erroneously reason that "I will never be trampled by an elephant in Charlottesville because my lucky nose ring protects me." Although it is almost certainly true that he will never be trampled by an elephant in Charlottesville it is not due to the protective powers of his nose ring.

Examples of many fallacies are given by category in the text.

Methods of Proving Theorems

There are several methods (or approaches) to proving theorems. Theorems (even quite complex ones) are ordinarily presentable in the form p Þ q where p and q are statements.

Take, for example, the famous Pythagorean Theorem.

"If c is the length of the hypotenuse of a right triangle and a and b are the lengths of the remaining two sides

Then c² = a² + b²

Recall that If p Then q is equivalent to p Þ q.

When we employ rules of inference, axioms and previously proven theorems to directly prove that p implies q we are employing the method called Direct Proof. Since the implication p Þ q is always true if p is false to complete a direct proof we need only prove that if p is true then q is true.

Recall that the contrapositive of the statement p Þ q is the statement Ø q Þ Ø p. Recall as well that the contrapositive is equivalent to the original statement. Therefore we may prove that p Þ q by proving that if q is false then p is false. This approach is called Indirect Proof.

Recall that a tautology is a statement that is always true. For example p Þ p \/ q is a tautology since it is true regardless of the truth-values of p and q. Recall, also, that a contradiction is a statement that is always false. For example p /\ Ø p is always false and is, therefore, a contradiction.

Since p Þ q can only be false when p = true and q = false we prove that p Þ q by showing that p = true and q = false is impossible. We do this by showing that p /\ Ø q leads to a contradiction.

I.e. we show that p /\ Ø q Þ F. This is called a Proof by Contradiction.

We sometimes are required to prove a statement false rather than prove it true. The most straightforward method of proving a statement false is to find a counterexample; i.e. an instance for which the statement is false.

Prove or disprove the following statement.

"Every number of the form 2^N -1 is a prime number when N is a prime number."

Let N = 11 (a prime) then 2^N -1 = 2047 = 23 * 89

Therefore 2^N -1 is not a prime number for N = 11 and the statement is proven false.

Quite often it is difficult to prove a theorem for all cases at once. It may be easier to prove the theorem for special cases. If we prove the theorem for all possible cases then we have a valid proof of the theorem.

Example:

Prove that the square of any positive integer when divided by 4 has a remainder of 0 or 1.

Proof:

Let N be a positive integer.

Case I: N is even

Then N = 2· I for some positive integer I

N² = 4· I²

Therefore N² is divisible by 4 and, thus, has a remainder of 0 when divided by 4.

Case II: N is odd

Then N = 2· J -1 for some positive integer J

N² = 4· J² - 4· J + 1

4 divides 4· J² - 4· J,

Therefore, 4· J² - 4· J + 1 has a remainder of 1 when divided by 4.

QED

Since every positive integer must be either even or odd and we proved the theorem for both of these cases we have proven the theorem.

Existence proofs prove that an object (number, set, etc.) with certain properties exists. Existence proofs that actually find an object with the desired properties are called Constructive. Existence proofs that prove the existence of an object with the desired properties without actually finding it are called Nonconstructive.

• First, carefully write down exactly what you are trying to prove. It is best if it is written down both formally (symbolic logic implication) and informally, if possible.
• Next, collect all pertinent information - axioms, theorems, lemmas, definitions, previously proven problems. At nearly every step in your proof you will need to use one of these devices. Missing a critical one can easily prevent you from completing the proof.
• Gain an understanding of the problem. Make up sample data. Prove weaker results. All this will give you insight into how to appoach the problem.
• Finally, list potential methods of proof in the order in which you will try to apply them (until one succeeds, of course).
• Generally one does not have to "start from scratch" in proving results. Mathemeticians have been proving thorems for thousands of year. It is likely that you will be able to mimic the proof of a similar problem. The key is in understanding the problem.