Key Takeaways: Direct Proof and Contraposition

A one-page reference card. Reread it before an exam or before writing your next proof.

What a proof is

A proof = a finite chain of logically valid steps establishing a claim for every case at once. Testing checks finitely many inputs; a proof leaves none unchecked. "Passes all tests" = conjecture; "proved" = theorem.

Vocabulary of results

Term Meaning
Theorem Proved-true statement (usually important).
Lemma Proved-true helper, a stepping stone to a theorem.
Corollary Follows quickly from a theorem already proved.
Conjecture Believed true, not yet proved.

The three definitions (all are existentials in disguise)

Term Definition Quantified form
$n$ even $n = 2k$, some integer $k$ $\exists k \in \mathbb{Z},\ n = 2k$
$n$ odd $n = 2k+1$, some integer $k$ $\exists k \in \mathbb{Z},\ n = 2k+1$
$a \mid b$ (divides) $b = ac$, some integer $c$ ($a \neq 0$) $\exists c \in \mathbb{Z},\ b = ac$

Notation: $a \mid b$ is a statement (true/false); $a / b$ is a number. Never write "$3 \mid 12 = 4$". Also: $n$ even $\iff 2 \mid n$.

The master habit (every even/odd/divisibility proof)

Unpack → compute → repackage. 1. Unpack each hypothesis: turn a definition into an equation, naming the witness ("$n = 2k+1$ for some integer $k$"; "$b = as$ for some integer $s$"). 2. Compute: do the algebra, keeping the target definition's shape in view. 3. Repackage: exhibit the witness for the goal ("let $m = \dots$; then $n^2 = 2m+1$, so $n^2$ is odd").

The two strategies

Strategy Prove $P \rightarrow Q$ by… Assume Derive Reach for it when
Direct arguing forward $P$ $Q$ the hypothesis gives you an equation to work with
Contraposition proving $\neg Q \rightarrow \neg P$ $\neg Q$ $\neg P$ the conclusion is "negative" / direct stalls (e.g. "$n^2$ odd $\Rightarrow n$ odd")

Biconditional $P \leftrightarrow Q$: prove both $P \rightarrow Q$ and $Q \rightarrow P$ (may use different strategies for each direction).

Converse vs. contrapositive (do not confuse)

Of $P \rightarrow Q$ Form Equivalent to original?
Converse $Q \rightarrow P$ NO
Contrapositive $\neg Q \rightarrow \neg P$ YES ($P \rightarrow Q \equiv \neg Q \rightarrow \neg P$)

Mnemonic: converse = swap; contrapositive = swap and negate both. Only the contrapositive is safe to prove in place of the original. (Contrapositive of $\forall x,\ P(x)\rightarrow Q(x)$ keeps the $\forall$: $\forall x,\ \neg Q(x)\rightarrow\neg P(x)$.)

Two "easy-row" proofs

  • Vacuous proof: hypothesis $P$ is always false → $P \rightarrow Q$ holds automatically.
  • Trivial proof: conclusion $Q$ is always true → $P \rightarrow Q$ holds without using $P$.

Choosing a strategy

Claim is "for all x, P(x) -> Q(x)"?
  ├─ Conclusion gives you an equation to build on?      → DIRECT proof
  ├─ Conclusion is "negative" / direct attack stalls?   → CONTRAPOSITION (assume not-Q, derive not-P)
  ├─ It's "P if and only if Q"?                         → prove BOTH directions
  ├─ Hypothesis is never true?                          → VACUOUS proof
  └─ Conclusion is always true?                         → TRIVIAL proof
Claim is "there exists x with Q(x)"?                    → EXHIBIT one witness (one example IS a proof)
Claim is a universal you suspect is false?              → hunt for a COUNTEREXAMPLE (Ch. 2)

Common pitfalls

Pitfall Fix
Proving the converse ($Q\rightarrow P$) State $P$ and $Q$ first; assume the right one.
Proof by example for a $\forall$ claim Fix an arbitrary variable, never a specific number.
Reusing a name: $a=2k,\ b=2k$ Fresh names: $a=2j,\ b=2k$.
Begging the question (assuming the goal) Each step from definitions/hypotheses/prior results only.
Dividing by a possibly-zero quantity Multiply instead; or case-split on zero.
(Existential) thinking one example is too weak For $\exists$, one witness is the whole proof.

Reading a proof critically

  1. Name the claim's form (conditional? $\forall$? $\exists$?).
  2. Find the strategy (assume $P$ = direct; assume $\neg Q$ = contraposition; assume whole claim false = contradiction, Ch. 5).
  3. Check variables are arbitrary, hypothesis assumed (not the converse).
  4. Justify every step — name the definition/identity. A step you can't justify is a hole.
  5. Verify the last line states the actual claim (not a near-miss). Hunt for the dropped case (e.g. $km=1$ over $\mathbb{Z}$ has two solutions, $1$ and $-1$).

Toolkit addition

logic.py: find_counterexample(predicate, domain) (returns the first $x$ failing predicate, else None) and holds_for_all(predicate, domain). A returned $x$ disproves a $\forall$ claim; None is evidence, not a proof.