Essential Methods of Proof

Why This Matters

In Formal Logic II, you're not just being tested on whether you can recognize a valid argument—you're being tested on whether you can build one from scratch. The methods of proof you'll master here are the fundamental tools logicians and mathematicians use to establish truth with absolute certainty. Understanding these techniques means understanding how knowledge is justified, which connects to everything from soundness and completeness to decidability and formal systems.

Here's the key insight: 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 a student who can follow proofs from one who can construct them.

---

Implication-Based Methods

These methods 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, following the natural "flow" of the implication
• Chain of valid inferences connects your assumption to your conclusion through axioms, definitions, and previously proven theorems
• Best used when the path from $P$ to $Q$ is relatively clear; if you find yourself stuck, consider switching to contraposition or contradiction

Proof by Contraposition

• Prove $\neg Q \rightarrow \neg P$ instead—logically equivalent to $P \rightarrow Q$ by the contrapositive equivalence
• Strategic advantage arises when the negation of the conclusion gives you more concrete information to work with than the original hypothesis
• Common in proofs involving divisibility, irrationality, and set non-membership, where "not having a property" is easier to leverage

Proof by Contradiction

• Assume $\neg S$ where $S$ is your target statement—then derive any contradiction $R \wedge \neg R$
• 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
• Most powerful when direct approaches fail or when the statement involves negation, uniqueness, or infinitude (e.g., proving $\sqrt{2}$ is irrational)

---

Case-Based Methods

When a single argument can't cover all possibilities, these methods let you divide and conquer. The key is ensuring your cases are exhaustive (cover everything) and mutually exclusive (don't overlap unnecessarily).

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
• Disjunction elimination is the underlying logical principle—if $S$ follows from each $C_i$, and 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

Proof by Exhaustion

• Check every single instance—only viable when the domain is finite and small enough to enumerate completely
• Guarantees completeness since no case is left unexamined; often used in combinatorics and computer-verified proofs
• Famous example: the Four Color Theorem was proven by exhaustively checking hundreds of configurations via computer

---

Quantifier-Focused Methods

These methods are specifically designed for statements involving universal ($\forall$) or existential ($\exists$) quantifiers. Choosing the right approach depends entirely on which quantifier you're dealing with.

Universal Proof

• Prove for an arbitrary element—introduce a variable with no special properties, then show the statement holds for it
• Universal generalization allows you to conclude $\forall x \, P(x)$ from a proof of $P(c)$ where $c$ is arbitrary
• Critical requirement: your chosen element must be genuinely arbitrary—using any specific properties invalidates the generalization

Existential Proof

• Show at least one element satisfies the property—either by constructing a specific witness or by indirect argument
• Existential generalization lets you conclude $\exists x \, P(x)$ from $P(c)$ for any specific $c$
• Two flavors: constructive (exhibit the witness) or non-constructive (prove existence without identifying the element)

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)$
• Logical basis: the negation of $\forall x \, P(x)$ is $\exists x \, \neg P(x)$, so one counterexample suffices
• Exam tip: when asked to evaluate a universal claim, always consider whether a simple counterexample exists before attempting a proof

---

Constructive vs. Non-Constructive Methods

This distinction cuts across 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—provides an algorithm, formula, or specific example that witnesses the existential claim
• Philosophically stronger because it gives you the object itself, not just assurance that it's "out there somewhere"
• Required in intuitionistic logic and computer science applications where mere existence isn't useful without a method to find the object

Mathematical Induction

• Prove a base case $P(1)$, then prove the inductive step $P(k) \rightarrow P(k+1)$—together these establish $\forall n \in \mathbb{N} \, P(n)$
• Relies on the well-ordering principle: every non-empty subset of natural numbers has a least element
• Variations include strong induction (assume $P(1), \ldots, P(k)$ to prove $P(k+1)$) and structural induction (for recursively defined objects)

---

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?