04 Proof Techniques

A structured guide to selecting, organizing, and writing valid mathematical proofs, including direct proofs, contrapositives, contradiction, cases, counterexamples, and clear mathematical exposition.

Foundations of

A shows that a conclusion follows from definitions, assumptions, and established results. It must cover every object described by the claim, not merely several examples.

Many claims can be expressed as an implication:

P\implies Q.

This means that whenever $P$ is true, $Q$ must also be true. The is

\neg Q\implies\neg P.

These two implications are logically equivalent. By contrast, the converse $Q\implies P$ is not generally equivalent to the original implication.

A useful opening routine is:

Identify the domain and the quantifiers.
Rewrite technical terms using their definitions.
Separate the hypotheses from the desired conclusion.
Test small or boundary cases before choosing a proof strategy.

The main goal is not only to reach a true conclusion, but to make clear why each step follows from the preceding information.

Takeaway: Translate the claim into a precise logical form before deciding how to prove it.

Direct Proofs and Definitions

In a , assume the hypotheses and move step by step toward the conclusion. For a universal statement, begin with an satisfying the hypotheses.

A standard pattern is:

State the assumptions.
Introduce arbitrary objects in the required domain.
Apply definitions and known facts.
Derive the desired conclusion.
State explicitly that the claim has been proved.

For example, suppose $a$ and $b$ are even integers. By the definition of evenness, there exist integers $m$ and $n$ such that

a=2m\qquad\text{and}\qquad b=2n.

Then

a+b=2m+2n=2(m+n).

Because $m+n$ is an integer, $a+b$ has the form required for an even integer. Therefore, the sum of two even integers is even.

The key step is not the numerical appearance of the variables; it is the precise use of the definition. Similar substitutions can make many proofs concise and rigorous.

Takeaway: When definitions provide a usable algebraic form, a is often the clearest method.

Contrapositives and Logical Equivalence

Some implications are easier to prove after reversing the logical direction through negation. To prove $P\implies Q$ , assume $\neg Q$ and derive $\neg P$ . Because the is logically equivalent to the original implication, this establishes the desired result.

Consider the claim: if $n^2$ is odd, then $n$ is odd. Its says that if $n$ is not odd, then $n^2$ is not odd. For an integer, not being odd means being even, so write $n=2k$ for some integer $k$ . Then

n^2=(2k)^2=4k^2=2(2k^2),

which is even. Thus $n^2$ is not odd, proving the and therefore the original claim.

Do not confuse this method with proving the converse. The converse of “if it is raining, then the ground is wet” is “if the ground is wet, then it is raining,” whereas the is “if the ground is not wet, then it is not raining.”

Takeaway: Use negation strategically, and keep the hypothesis, conclusion, converse, and distinct.

Contradiction as an Indirect Method

A begins by assuming that the desired statement is false. The argument then derives an impossibility, such as an equation that cannot hold, a violation of a definition, or a conflict with a known theorem.

To show that $\sqrt{2}$ is irrational, suppose for contradiction that it is rational. Then there are integers $p$ and $q$ , with $q\ne 0$ and $\gcd(p,q)=1$ , such that

\sqrt{2}=\frac{p}{q}.

Squaring and multiplying by $q^2$ gives

p^2=2q^2.

Thus $p^2$ is even, so $p$ is even. Write $p=2r$ . Substitution yields

(2r)^2=2q^2,

so $q^2=2r^2$ , and therefore $q$ is even as well. Both $p$ and $q$ are even, contradicting $\gcd(p,q)=1$ . The assumption that $\sqrt{2}$ is rational is impossible, so $\sqrt{2}$ is irrational.

For an implication $P\implies Q$ , contradiction typically assumes both $P$ and $\neg Q$ , then shows that these assumptions cannot all be true. This differs from the , which proves the separate implication $\neg Q\implies\neg P$ .

Takeaway: Choose contradiction when the negation creates a strong structural restriction or an immediate impossibility.

Cases, Testing, and Counterexamples

A divides the domain into possibilities and proves the conclusion in every case. The cases must be exhaustive: every object satisfying the hypotheses must occur in at least one case.

For every integer $n$ , consider the claim that $n^2-n$ is even. There are two cases.

If $n$ is even, write $n=2k$ . Then
$n^2-n=n(n-1)=2k(n-1),$
which is even.
If $n$ is odd, then $n-1$ is even. Therefore, the product $n(n-1)$ is even.

Every integer is either even or odd, so the cases cover all possibilities. Hence $n^2-n$ is even for every integer $n$ .

Cases can also distinguish positive, zero, and negative values; membership or nonmembership in a set; graph configurations; or branches of a piecewise definition. Overlapping cases are permitted, but missing cases make the proof incomplete.

Before attempting a universal proof, test the statement for small values, boundary values, negative values when allowed, and values near a change in definition. If one valid exception is found, use it as a instead of trying to prove a false claim.

Takeaway: A case split succeeds only when every allowed possibility is covered and each case is justified.

Writing and Choosing Proofs

A well-written proof makes its logical dependencies visible. State the claim and the domain of its variables, use arbitrary objects for universal claims, and define every introduced variable. Explain important transitions instead of presenting an unexplained chain of equations.

Useful signals include “Assume” for hypotheses, “By definition” for foundational steps, “Therefore” for deductions, and “Hence” for conclusions. Keep notation consistent, check edge cases, and avoid circular reasoning: the conclusion, or an equivalent statement, cannot be assumed as part of the proof.

A practical decision process is:

Unpack the definitions.
Try a .
Consider the if the negated conclusion is easier to use.
Look for natural exhaustive cases.
Test small and boundary values for counterexamples.
Use contradiction when the negation produces a useful impossibility.
Rewrite the final argument so that it is complete, organized, and readable.

A compact direct-proof template is:

Claim. State the proposition and its domain.
Proof. Let the objects be arbitrary and satisfy the hypotheses. By a definition or known result, derive the needed statement. Therefore, the conclusion holds. $\square$

A proof may begin informally during discovery, but the final version should make all assumptions, quantifiers, definitions, and transitions explicit.

Takeaway: Correct reasoning becomes persuasive when the written structure shows exactly why the conclusion follows.

Foundations of Mathematical Proof