Proof Techniques

Why We Need Proof Techniques

A proof is a convincing logical argument that a mathematical statement is true. In the parent chapter, you met the general idea of a proof. This chapter focuses on methods for building proofs: common patterns of reasoning that appear again and again.

Each technique is like a tool. No single tool works for every problem, but together they cover most elementary proofs you will see. Later subsections will look closely at specific techniques (direct proof, proof by contradiction, induction). Here, you learn how to recognize when each type of technique is appropriate, and what its basic structure looks like.

We will mainly talk about proving statements of the following forms:

• “for all $x$, $P(x)$ implies $Q(x)$”
• “there exists an $x$ such that $P(x)$”
• simple algebraic or number-theoretic statements

Structure of Statements and Choice of Technique

Before choosing a technique, it helps to look at the logical form of the statement. Typical patterns include:

1. Universal statements: “For all $x$ in some set, $P(x)$ holds.”
• Example: “For all even integers $n$, $n^2$ is even.”
• Common techniques: direct proof, proof by contrapositive, sometimes induction.
2. Implications: “If $P$, then $Q$,” written $P \Rightarrow Q$.
• Example: “If a number is divisible by 4, then it is even.”
• Common techniques: direct proof, proof by contrapositive, proof by contradiction.
3. Existential statements: “There exists an $x$ with property $P(x)$.”
• Example: “There exists an irrational number whose square is rational.”
• Common techniques: constructive existence proof, or non-constructive proof (often using contradiction).
4. Equivalences: “$P$ if and only if $Q$,” written $P \Leftrightarrow Q$.
• Example: “An integer $n$ is even if and only if $n^2$ is even.”
• Common technique: split into two implications: prove $P \Rightarrow Q$ and $Q \Rightarrow P$ separately, possibly using different techniques for each direction.
5. Statements about integers in order: often of the form “for all integers $n \ge n_0$, $P(n)$.”
• Common technique: mathematical induction (a specialized proof method tailored to such statements).

Recognizing these forms helps you to pick a suitable method instead of guessing blindly.

Direct Proof (Overview)

A direct proof of “if $P$, then $Q$” starts from $P$ and, using definitions and known facts, pushes forward to show $Q$.

Very general outline:

1. Assume $P$ is true.
2. Use algebra, known theorems, and definitions to deduce consequences.
3. Conclude $Q$.

When it fits well, a direct proof feels “straight ahead”: you never deny the claim, you simply unfold definitions and manipulate expressions until the conclusion becomes obvious.

Direct proofs are especially common for:

• Very basic arithmetic statements.
• Simple inequalities.
• Properties that follow immediately from definitions.

Details of step-by-step execution and extended examples belong in the dedicated “Direct proof” subsection; here, the important point is recognizing that some proofs genuinely are as straightforward as “start from the hypothesis and calculate.”

Proof by Contrapositive (Overview)

An implication $P \Rightarrow Q$ is logically equivalent to its contrapositive:
$$
P \Rightarrow Q \quad\text{is equivalent to}\quad \lnot Q \Rightarrow \lnot P.
$$

A proof by contrapositive of “if $P$, then $Q$” proceeds by instead proving:
“if $Q$ is false, then $P$ is false.”

Why this helps:

• Sometimes starting from $P$ does not lead easily to $Q$.
• But starting from “$Q$ fails” gives a clearer path to “$P$ fails.”

Outline:

1. Restate “if $P$ then $Q$” as “if not $Q$ then not $P$.”
2. Assume $\lnot Q$.
3. Deduce $\lnot P$.
4. Conclude $P \Rightarrow Q$ is true (because its contrapositive is).

Typical situations where this is effective:

• When $Q$ is a simple condition and its negation is easy to work with.
• When $P$ has a complicated definition, so its negation might be easier to show.
• Number theory statements such as “if $n^2$ is even, then $n$ is even” are often proved via the contrapositive.

Proof by Contradiction (Overview)

In a proof by contradiction, you want to show that a statement $S$ is true. Instead of proving $S$ directly, you:

1. Assume $S$ is false (assume $\lnot S$).
2. Combine this assumption with known facts and definitions.
3. Derive a contradiction: a statement that is impossible, such as:
• both $R$ and $\lnot R$,
• something that contradicts earlier known results,
• or something that violates basic properties of numbers or logic.
4. Conclude that your assumption $\lnot S$ must be wrong, so $S$ is true.

This technique is especially useful:

• When no straightforward construction or direct argument is apparent.
• For many existence results where you can trap a supposed counterexample into an impossible situation.
• In classical proofs showing that certain objects cannot exist, or that certain sets are infinite, etc.

Conceptually, proof by contradiction is more “global” than proof by contrapositive:

• Contrapositive: you still prove an implication, but from $\lnot Q$ to $\lnot P$.
• Contradiction: you start from the negation of the whole statement and show that leads to absurdity.

In practice, many contradiction proofs will contain a contrapositive argument as one step, but the overall structure rests on the “assume the opposite and reach absurdity” approach.

Proofs of Equivalence (“If and Only If”)

Statements of the form
$$
P \quad\text{if and only if}\quad Q
$$
mean that both $P \Rightarrow Q$ and $Q \Rightarrow P$ are true.

To prove this, you normally split the work:

1. Prove “if $P$ then $Q$.”
2. Prove “if $Q$ then $P$.”

Each direction can use any suitable technique:

• One direction might be direct.
• The other might be via contrapositive or contradiction.

A common stylistic convention:

• Clearly label each direction (e.g., write “($\Rightarrow$)” above the first and “($\Leftarrow$)” above the second).
• Treat each as a separate mini-proof.

Existence Proofs: Constructive vs Non-Constructive

Many theorems assert that something exists:

• “There exists a real number with property $P$.”
• “There exists a solution to this equation.”

There are two common styles of proof here.

Constructive existence proofs

A constructive proof of an existence statement actually produces an example:

1. Explicitly define a specific object.
2. Show that this object has the required property.

For instance, to prove “there exists an even integer greater than 10,” you could say:
“Take $12$. It is an integer, it is even, and $12 > 10$.”

Constructive proofs are usually preferred when possible because they give you more information—an explicit witness, not just a logical guarantee.

Non-constructive existence proofs

A non-constructive proof of existence shows that some object with the property must exist, without necessarily telling you which one.

These often use contradiction:

1. Assume no such object exists.
2. Derive a contradiction.
3. Conclude that at least one such object must exist.

Non-constructive proofs commonly appear in more advanced mathematics, but even in elementary settings they arise when the exact object is hard to specify.

Counterexamples: Disproving Statements

Not all work with proofs is about showing statements are true. Sometimes you must decide whether a claim is true or false.

For many universal statements (“for all $x$, $P(x)$ holds”), you can disprove them by giving a counterexample:

• A counterexample is a specific case where the statement fails.
• To show “for all $x$, $P(x)$” is false, you only need one $x$ such that $P(x)$ is false.

General pattern:

1. Find a candidate object $a$.
2. Compute or reason to show that $P(a)$ is false.
3. Conclude the universal statement is false.

Counterexamples are extremely powerful:

• They completely settle the question of “is this always true?”
• They often suggest how a claim must be corrected or strengthened to become true.

Mathematical Induction (Conceptual Overview)

Mathematical induction is a specialized proof technique for statements about integers of the form
$$
P(1), P(2), P(3), \dots
$$
or, more generally, all integers $n \ge n_0$.

Although the detailed procedure belongs in the “Mathematical induction” subsection, the conceptual idea fits among proof techniques:

1. Base step: Show that $P(n_0)$ is true for the starting value $n_0$.
2. Inductive step: Show that if $P(k)$ is true for some integer $k \ge n_0$, then $P(k+1)$ is also true.

If both steps succeed, then $P(n)$ is true for all integers $n \ge n_0$.

Induction is not just “doing an example and guessing.” It is a fully rigorous method: the inductive step does not just check $k=1$; it proves a general implication $P(k) \Rightarrow P(k+1)$ that applies to every $k$ in the domain.

Combining Techniques

Real proofs often blend multiple techniques:

• Start with a direct argument, then at a key moment use a contradiction step.
• Prove an equivalence by using direct proof in one direction and contrapositive in the other.
• Use induction to prove a general formula, but inside the inductive step you use straightforward algebraic manipulation (a form of direct proof).
• Disprove a conjecture by finding a counterexample, and then use that example to guide the construction of a more precise theorem that you do then prove directly.

Being flexible with these tools is more important than memorizing rigid rules. Over time, your choice of technique becomes guided by experience: you start to recognize when a direct approach is messy, when a contrapositive looks promising, or when the statement’s shape suggests induction.

Strategy and Practice

To become comfortable with proof techniques:

• Analyze the statement’s logical form (universal, existential, implication, equivalence, about integers, etc.).
• Choose a likely technique:
• Implication with a simple hypothesis: try direct proof.
• Implication where the conclusion has a simple negation: consider contrapositive.
• “For all integers $n$…” formulas: consider induction.
• Existence statements: try to construct an example; if hard, think about non-constructive methods.
• Suspected false universal statement: search for a counterexample.
• Write clearly: mark assumptions, separate cases, and indicate when you have reached the conclusion or a contradiction.

Later subsections will go into detail with templates and step-by-step examples of direct proof, proof by contradiction, and induction. Here you should retain the big picture: each named technique is a standard pattern of reasoning that you can recognize and deliberately apply.