Methods of Mathematical Proof

A mathematical proof is a sequence of logical statements showing that if certain assumptions (axioms or previously proven theorems) are true, then a conclusion must also be true. Proofs are the “currency” of mathematics; a conjecture remains a mere hypothesis until it is anchored into the mathematical landscape by a rigorous proof. In this lesson, we examine the primary taxonomy of proof methods.

1. Direct Proof

The most straightforward form of reasoning is the Direct Proof. To prove $P⟹Q$, we assume the prefix $P$ (the hypothesis) is true and use a chain of established truths to show that $Q$ (the conclusion) must also be true.

Example: Prove that the sum of two even integers is always even.

1. Assume $x$ and $y$ are even. By definition, $x=2k$ and $y=2m$ for some integers $k,m$.
2. Consider the sum $x+y=2k+2m$.
3. Factor out the common term: $2(k+m)$.
4. Since the sum of two integers $k+m$ is an integer $n$, then $x+y=2n$.
5. By definition, $2n$ is even. $\square$

2. Proof by Contraposition

This method relies on the logical equivalence between a statement and its contrapositive: $(P⟹Q)\equiv (\neg Q⟹\neg P)$. Sometimes, it is easier to prove that the failure of the conclusion implies the failure of the hypothesis.

Example: Prove that for any integer $n$, if $n^2$ is even, then $n$ is even.

1. The contrapositive is: “If $n$ is odd, then $n^2$ is odd.”
2. Assume $n$ is odd. Then $n=2k+1$ for some integer $k$.
3. Calculate $n^2=(2k+1{)}^2=4k^2+4k+1=2(2k^2+2k)+1$.
4. Since $2(2k^2+2k)$ is an integer, $n^2$ is of the form $2m+1$ and is therefore odd.
5. Since the contrapositive is true, the original statement is true.

3. Proof by Contradiction (Reductio ad Absurdum)

To prove $P$, we assume $\neg P$ and demonstrate that this assumption leads to a logical contradiction (e.g., $0=1$ or “the number is both even and odd”). If the negation leads to an impossibility, then $P$ must be true.

Example: The Irrationality of $\sqrt{2}$

1. Assume $\sqrt{2}$ is rational. Then $\sqrt{2}=\frac{a}{b}$ where $a,b$ are integers in simplest form (no common factors).
2. Square both sides: $2=\frac{a^2}{b^2}⟹2b^2=a^2$.
3. Since $a^2$ is a multiple of $2$, $a$ must be even (as proven by contraposition previously). Let $a=2k$.
4. Substitute: $2b^2=(2k{)}^2=4k^2⟹b^2=2k^2$.
5. This implies $b^2$ is even, so $b$ is even.
6. If $a$ and $b$ are both even, they have a common factor of $2$, contradicting the assumption that $\frac{a}{b}$ was in simplest form.
7. Thus, the assumption that $\sqrt{2}$ is rational is false.

4. Existence Proofs: Constructive vs. Non-Constructive

Existence theorems prove that an object with certain properties exists ($\exists xP(x)$).

• Constructive Proof: Provides an explicit example or a algorithm to find the object.
• Non-Constructive Proof: Shows that the object must exist without identifying it. A classic example uses the Law of the Excluded Middle.

Non-Constructive Example: Prove there exist irrational numbers $x,y$ such that $x^y$ is rational.

1. Consider ${\sqrt{2}}^{\sqrt{2}}$.
2. If this is rational, we are done ($x=y=\sqrt{2}$).
3. If it is irrational, let $x={\sqrt{2}}^{\sqrt{2}}$ and $y=\sqrt{2}$. Then $x^y=({\sqrt{2}}^{\sqrt{2}}{)}^{\sqrt{2}}={\sqrt{2}}^2=2$, which is rational.
4. In either case, such a pair exists, though we haven’t determined which pair it is!

5. Counterexamples and Disproof

To disprove a universal statement $\forall xP(x)$, we only need one counterexample—a single element $c$ such that $\neg P(c)$.

Example: Disprove “Every odd number is prime.”

1. Let $n=9$.
2. $n$ is odd, but $n=3\times 3$, so it is not prime.
3. The statement is false.

Proof by Cases (Exhaustion)

If the domain can be partitioned into a finite number of cases, we can prove the statement for each case separately. This is common in discrete math and group theory.

Example: Prove that $n^2+n$ is always even for any integer $n$.

1. Case 1: $n$ is even. $n=2k⟹(2k{)}^2+2k=4k^2+2k=2(2k^2+k)$, which is even.
2. Case 2: $n$ is odd. $n=2k+1⟹(2k+1{)}^2+(2k+1)=4k^2+4k+1+2k+1=4k^2+6k+2=2(2k^2+3k+1)$, which is even.
3. Since $n$ must be either even or odd, the statement is true for all $n$.

Higher-Level Structure: Lemma, Theorem, Corollary

Mathematical papers organize proofs using hierarchy:

• Definition: Sets the terms.
• Lemma: A “helper” theorem; a minor result used to prove a larger one.
• Theorem: A significant mathematical result.
• Corollary: A result that follows immediately from a theorem.
• Scholium: An explanatory remark or additional information.

Knowledge Check

By internalizing these methods, you gain the ability to navigate complex mathematical landscapes with certainty, moving beyond mere calculation into the realm of structured discovery.