Mathematical Proof Techniques College Reference Cheat Sheet

Key Facts

• A direct proof of $P \Rightarrow Q$ assumes $P$ is true and uses definitions, known results, and valid algebra to derive $Q$.
• A contrapositive proof uses the logically equivalent statement $\neg Q \Rightarrow \neg P$ to prove $P \Rightarrow Q$.
• A proof by contradiction assumes $P$ is true and $Q$ is false, then derives an impossibility such as $R \land \neg R$.
• To prove $\forall x \in S,\ P(x)$ by cases, split $S$ into exhaustive cases $S_1, S_2, \ldots, S_k$ and prove $P(x)$ in every case.
• Weak induction proves $P(n)$ for all $n \geq n_0$ by proving $P(n_0)$ and then proving $P(k) \Rightarrow P(k+1)$ for every $k \geq n_0$.
• Strong induction proves $P(n)$ for all $n \geq n_0$ by proving base cases and then proving $P(n_0) \land \cdots \land P(k) \Rightarrow P(k+1)$.
• An existence proof establishes $\exists x \in S$ such that $P(x)$, either by constructing such an $x$ or proving one must exist indirectly.
• To prove uniqueness, first prove existence of an object $x$ with property $P(x)$, then prove that if $P(a)$ and $P(b)$, then $a=b$.

Vocabulary

Implication

An implication is a statement of the form $P \Rightarrow Q$, meaning that whenever $P$ is true, $Q$ must also be true.

Contrapositive

The contrapositive of $P \Rightarrow Q$ is $\neg Q \Rightarrow \neg P$, and it is logically equivalent to the original implication.

Contradiction

A contradiction is a statement that cannot be true, such as $R \land \neg R$ or an equation like $0=1$.

Induction Hypothesis

The induction hypothesis is the temporary assumption that $P(k)$, or several earlier statements, are true during the induction step.

Counterexample

A counterexample is one specific value or object that makes a universal statement $\forall x,\ P(x)$ false.

Uniqueness

Uniqueness means that at most one object satisfies a property, often proved by showing $P(a) \land P(b) \Rightarrow a=b$.