Introduction to Proofs

Overview

What Is a Proof?

A mathematical proof is a rigorous argument that establishes the truth of a statement beyond any doubt. Unlike science, which relies on experiments and observations, mathematics demands absolute certainty through logical deduction. A proof starts from accepted truths (axioms, definitions, or previously proven theorems) and uses logical rules to arrive at the desired conclusion.

Definition

Theorem, Axiom, Lemma, Corollary

Axiom: A statement accepted as true without proof (a starting assumption). Definition: A precise description of a mathematical concept. Theorem: A statement that has been proven to be true. Lemma: A "helper" theorem, proven as a stepping stone to a bigger result. Corollary: A result that follows easily from a theorem.

Definition

Hypothesis and Conclusion

Most theorems have the form "If P, then Q" (P → Q).

P is called the hypothesis (or premises) - what we assume to be true. Q is called the conclusion - what we want to show follows from P.

Example: "If n is an even integer, then n² is even." Hypothesis: n is an even integer. Conclusion: n² is even.

Overview

Common Proof Strategies

There are several standard proof techniques:

1. Direct Proof: Assume the hypothesis, reason step by step to the conclusion. 2. Proof by Contrapositive: Prove ¬Q → ¬P instead of P → Q. 3. Proof by Contradiction: Assume the statement is false and derive a contradiction. 4. Mathematical Induction: Prove a base case, then prove the inductive step. 5. Proof by Cases: Split into exhaustive cases and prove each one.

Note

Common Definitions Used in Proofs

Even integer: n = 2k for some integer k. Odd integer: n = 2k + 1 for some integer k. Rational number: r = a/b where a, b are integers and b ≠ 0. Divisibility: a | b means b = a × k for some integer k.

Example

Reading a Simple Proof

Claim: The sum of two even integers is even.

Proof: Let m and n be even integers. By definition, m = 2a and n = 2b for some integers a and b. Then m + n = 2a + 2b = 2(a + b). Since a + b is an integer, m + n is even by definition. QED.

Note

Writing Good Proofs

Tips for writing clear proofs: 1. State what proof technique you are using. 2. Clearly identify your assumptions. 3. Justify each step with a definition, theorem, or logical rule. 4. Write in complete sentences - a proof is an argument, not a calculation. 5. End with "QED," "□," or a clear concluding sentence.