Essential Methods of Proof

Why This Matters

In Formal Logic II, you're not just recognizing valid arguments. You're building them from scratch. The methods of proof covered here are the fundamental tools logicians and mathematicians use to establish truth with certainty. Mastering them means understanding how knowledge is justified, which connects directly to topics like soundness and completeness, decidability, and formal systems.

Each proof method exploits a different logical principle. Direct proof leverages the transitivity of implication. Contradiction exploits the law of non-contradiction. Induction relies on the well-ordering of natural numbers. Don't just memorize the steps. Know which logical principle each method depends on and when each method is strategically appropriate. That's what separates following proofs from constructing them.

---

Implication-Based Methods

These are your workhorses for proving conditional statements of the form $P \rightarrow Q$. Each approaches the implication from a different angle, exploiting the logical structure of conditionals.

Direct Proof

Assume the antecedent $P$, then derive the consequent $Q$. This is the most intuitive method because it follows the natural "flow" of the implication.

Your proof will be a chain of valid inferences connecting your assumption to your conclusion, drawing on axioms, definitions, and previously proven theorems. Direct proof works best when the path from $P$ to $Q$ is relatively clear. If you find yourself stuck, that's a signal to consider contraposition or contradiction instead.

Steps:

1. State "Assume $P$."
2. Apply definitions, axioms, or known results to transform $P$ step by step.
3. Arrive at $Q$.
4. Conclude $P \rightarrow Q$.

Proof by Contraposition

Prove $\neg Q \rightarrow \neg P$ instead. This is logically equivalent to $P \rightarrow Q$ by the contrapositive equivalence: $(P \rightarrow Q) \leftrightarrow (\neg Q \rightarrow \neg P)$.

The strategic advantage arises when the negation of the conclusion gives you more concrete information to work with than the original hypothesis. This is common in proofs involving divisibility, irrationality, and set non-membership, where "not having a property" is easier to leverage.

Steps:

1. State "Assume $\neg Q$."
2. Use definitions and valid inferences to derive $\neg P$.
3. Conclude that $P \rightarrow Q$ by contraposition.

Proof by Contradiction

Assume $\neg S$ (where $S$ is your target statement), then derive any contradiction $R \wedge \neg R$. This exploits the law of non-contradiction: since no statement can be both true and false, your assumption $\neg S$ must be false, making $S$ true.

This method is most powerful when direct approaches fail or when the statement involves negation, uniqueness, or infinitude. The classic example is proving $\sqrt{2}$ is irrational.

Steps:

1. State "Assume, for contradiction, that $\neg S$."
2. Reason from $\neg S$ (possibly combined with other known truths) until you derive a statement of the form $R \wedge \neg R$.
3. Conclude that $\neg S$ is false, so $S$ is true.

Note that when $S$ is itself a conditional $P \rightarrow Q$, assuming $\neg S$ means assuming $P \wedge \neg Q$. This is where contradiction and contraposition can feel similar, but contradiction is more general because it can target any statement, not just conditionals.

---

Case-Based Methods

When a single argument can't cover all possibilities, these methods let you divide and conquer. The key requirement is ensuring your cases are exhaustive (they cover every possibility) and ideally mutually exclusive (they don't overlap unnecessarily, though overlap doesn't invalidate the proof).

Proof by Cases

Partition the domain into cases where $C_1 \vee C_2 \vee \ldots \vee C_n$ is a tautology, then prove the statement holds in each case separately.

The underlying logical principle is disjunction elimination: if $S$ follows from each $C_i$, and at least one of the $C_i$ must be true, then $S$ is true. Watch for natural divisions like even/odd, positive/negative/zero, or membership in different subsets.

Steps:

1. Identify a disjunction $C_1 \vee C_2 \vee \ldots \vee C_n$ that is guaranteed to be true (a tautology or a known fact).
2. For each $C_i$, assume $C_i$ and derive the target statement $S$.
3. Conclude $S$ by disjunction elimination.

Proof by Exhaustion

Check every single instance. This is only viable when the domain is finite and small enough to enumerate completely.

Exhaustion guarantees completeness since no case is left unexamined. It's often used in combinatorics and computer-verified proofs. A famous example: the Four Color Theorem was proven by exhaustively checking a large (but finite) set of configurations via computer.

---

Quantifier-Focused Methods

These methods target statements involving universal ($\forall$) or existential ($\exists$) quantifiers. Which approach you choose depends on which quantifier you're dealing with and whether you're proving or disproving.

Universal Proof

Prove the statement for an arbitrary element. You introduce a variable with no special properties beyond membership in the relevant domain, then show the statement holds for it.

The rule of universal generalization allows you to conclude $\forall x \, P(x)$ from a proof of $P(c)$ where $c$ is arbitrary. The critical requirement: your chosen element must be genuinely arbitrary. If you use any specific properties (like "let $c = 3$" or "since $c$ is even"), you've lost generality and the proof is invalid.

Existential Proof

Show that at least one element satisfies the property. You can do this either by constructing a specific witness or by indirect argument.

The rule of existential generalization lets you conclude $\exists x \, P(x)$ from $P(c)$ for any specific $c$. There are two flavors:

• Constructive: Exhibit a specific witness. For example, to prove "there exists an even prime," just present $2$.
• Non-constructive: Prove that something must exist without identifying it. Proof by contradiction is the typical vehicle here (see the section below on constructive vs. non-constructive methods).

Proof by Counterexample

Disprove a universal claim by finding one failure. A single counterexample to $\forall x \, P(x)$ establishes $\exists x \, \neg P(x)$, which is the negation of the original claim.

This works because the negation of $\forall x \, P(x)$ is $\exists x \, \neg P(x)$, so one counterexample is logically sufficient. When asked to evaluate a universal claim, always consider whether a simple counterexample exists before attempting a full proof.

---

Constructive vs. Non-Constructive Methods

This distinction cuts across the other categories and reflects a deep philosophical divide in logic and mathematics about what "existence" means.

Constructive Proof

Explicitly build the object claimed to exist. A constructive proof provides an algorithm, formula, or specific example that witnesses the existential claim.

This is philosophically stronger because it gives you the object itself, not just assurance that it's "out there." Constructive proof is required in intuitionistic logic, where the law of excluded middle ($P \vee \neg P$) is not assumed. It's also essential in computer science applications where mere existence isn't useful without a method to compute the object.

Mathematical Induction

Prove a base case, then prove the inductive step. Together these establish $\forall n \in \mathbb{N} \, P(n)$.

Induction relies on the well-ordering principle: every non-empty subset of natural numbers has a least element. If $P$ failed for some $n$, there would be a smallest such $n$, but the inductive step rules that out.

Steps:

1. Base case: Prove $P(1)$ (or whatever the starting value is).
2. Inductive hypothesis: Assume $P(k)$ for an arbitrary $k \geq 1$.
3. Inductive step: Using the assumption $P(k)$, prove $P(k+1)$.
4. Conclude $\forall n \in \mathbb{N} \, P(n)$ by the principle of mathematical induction.

Variations:

• Strong induction: In the inductive step, assume $P(1), P(2), \ldots, P(k)$ (all predecessors) to prove $P(k+1)$. Useful when $P(k+1)$ depends on cases earlier than $P(k)$.
• Structural induction: Used for recursively defined objects (like formulas, trees, or lists). The base case covers the atomic objects, and the inductive step covers each recursive constructor.

---

Quick Reference Table

---

Self-Check Questions

1. You need to prove "If $n^2$ is even, then $n$ is even." Which method would be most efficient, and why is direct proof awkward here?

2. What logical equivalence makes proof by contraposition valid? Write out the equivalence using $P$ and $Q$.

3. Compare mathematical induction and proof by exhaustion: both can prove universal statements over finite domains, so when would you choose one over the other?

4. A classmate claims "All prime numbers are odd." What method would you use to respond, and what specific example would you provide?

5. Explain why proof by contradiction can establish existence ($\exists x \, P(x)$) without being constructive. What assumption do you negate, and what does the contradiction tell you?