Lecture Notes: Proof

1. Introduction to Proofs

A proof is defined as an argument that establishes the truth of a theorem. Logic serves as the essential tool for analyzing these proofs. While there are formal rules of inference, there are multiple methods to prove a theorem.

2. Direct Proofs

Direct proofs are often used for theorems of the form (if , then ).

• Method: Assume is true.
• Goal: Directly prove that is true to maintain the truth of the implication .
• Logic: If were false while is true, the implication would be false.

Example 1: Sum of Odd and Even Integers

Statement: For all integers and , if is odd and is even, then is odd.

Proof:

1. Hypothesis (): Assume is odd and is even.
   • , where .
   • , where .
2. Conclusion (): We examine .
   
   
3. Let . Since , then .
4. Thus, , which is the definition of an odd integer.
5. Result: is odd.

Example 2: Algebraic Proof

Statement: For all integers , is a perfect square.

Proof:

1. Expand and simplify the expression:
   
   
2. Factor the result:
   
3. Since is an integer, is also an integer. Therefore, is a perfect square.

3. Disproving with Counterexample

To disprove a statement of the form , one only needs to find a single instance (counterexample) where the statement holds false.

Example: Disprove that for all , is a prime number.

• Test : (Prime)
• Test : (Prime)
• Test : (Prime)
• Counterexample ( ): . Since 9 is not prime, the theorem is disproven.

4. Proof by Contradiction

To prove is true, we assume the negation of the conclusion.

• Method: Assume is true and is false ().
• Goal: Show that this assumption leads to a contradiction (proving is false). This implies we must accept is true.

Example: Prove that for every , if is even, then is even.

1. Hypothesis (): is even.
2. Assumption (): is odd.
3. If is odd, for some .
4. Substitute into :
   
   
5. This result shows is odd, which contradicts the hypothesis that is even.
6. Therefore, by contradiction, if is even, must be even.

5. Proof by Contrapositive

The implication is logically equivalent to its contrapositive .

• Method: Instead of proving directly, prove that if is false, then is false.

Example: Prove "For all , if is irrational, then is irrational".

1. Contrapositive Statement: If is rational, then is rational.
2. Proof:
   • Assume is rational. Then where and .
   • Square :
     
   • Since are integers, are integers. Thus, is a rational number.
3. Since the contrapositive is true, the original statement is true.

6. Proof by Cases (Exhaustive Proof)

This method is used when the hypothesis naturally divides into distinct cases. You must prove the theorem holds for all possible cases.

Example 1: Prove that for every real number , .

• Case 1 ( ): If is positive, , so the statement holds.
• Case 2 ( ): If is 0, , so the statement holds.
• Case 3 ( ): If is negative, (since is positive), so the statement holds.
• Conclusion: By combining all cases, for all real numbers.

Example 2: Prove has no solution in positive integers.

• Since are positive integers and the result is 40, the possible values are limited.
• Bounds:
  • (Possible ).
  • (Possible ).
• One can exhaustively check all combinations of and to show none equal 40.

7. Proofs of Equivalence

Theorems of the form " if and only if " ( ) require proving two implications:

1. (If then )
2. (If then )

Example: Prove that for every integer , is odd if and only if is even.

1. Part 1 ( ): If is odd, then is even.
   • . (Even)
2. Part 2 ( ): If is even, then is odd.
   • . (Odd)
3. Conclusion: The equivalence is true.