Proof techniques

Section 0.5 Proof techniques

Proof writing is an art, a technical skill you will hone and refine throughout your career; and like any art, proof writing has many tricks of the trade. We gather a few here in the form of a collection of general proof techniques. Part of mastering these techniques involves understanding the circumstances where they can be of use. When selecting a technique, we are guided in part by the logical structure and particular mathematical content of the proposition under consideration. The proof techniques below are organized under this guiding principle.

Subsection 0.5.1 Logical structure

Subsubsection Implication

By Definition 0.4.1 the only time an implication \(\mathcal{P}\implies\mathcal{Q}\) is false is when \(\mathcal{P}\) is true and \(\mathcal{Q}\) is false. Accordingly, the direct approach to proving an implication \(\mathcal{P}\implies \mathcal{Q}\) is to assume \(\mathcal{P}\) is true, and use this assumption to prove \(\mathcal{Q}\) is true.

A common indirect approach used to prove an implication \(\mathcal{P}\implies \mathcal{Q}\) is to prove its contrapositive \(\neg\mathcal{Q}\implies \neg \mathcal{P} \text{,}\) which is logically equivalent to the original implication. In this case we assume \(\mathcal{Q}\) is not true, and show \(\mathcal{P}\) is not true. (Exercise: use a truth table to show the contrapositive is logically equivalent to the original implication.)

Warning 0.5.1.

The converse of an implication \(\mathcal{P}\implies \mathcal{Q}\) is the implication \(\mathcal{Q}\implies \mathcal{P}\text{;}\) the inverse of \(\mathcal{P}\implies\mathcal{Q}\) is the implication \(\neg\mathcal{P}\implies\neg\mathcal{Q}\text{.}\) Neither the converse nor the inverse is equivalent to the original implication, and thus neither of these can be used to give an indirect proof of \(\mathcal{P}\implies \mathcal{Q}\text{.}\) (Exercise: use a truth table to show that neither the converse nor the inverse implication is logically equivalent to the original implication. )

Subsubsection Disjunction

Again, using Definition 0.4.1, to directly show a disjunction \(\mathcal{P}\text{ or }\mathcal{Q}\) is true, we need only show one the two component propositions is true.

Alternatively, we can prove either of the implications \(\neg\mathcal{P}\implies\mathcal{Q}\) or \(\neg Q\implies \mathcal{P}\text{,}\) both of which are logically equivalent to \(\mathcal{P}\text{ or }\mathcal{Q}\text{.}\) (Exercise: use a truth table to show these three propositions are indeed equivalent!)

Subsubsection Equivalence

The equivalence \(\mathcal{P}\iff\mathcal{Q}\) is logically equivalent to the conjunction

\begin{equation*} (\mathcal{P}\implies\mathcal{Q})\text{ and } (\mathcal{Q}\implies \mathcal{P})\text{.} \end{equation*}

Accordingly, the standard way of proving \(\mathcal{P}\iff \mathcal{Q}\) is to prove the two implications \(\mathcal{P}\implies\mathcal{Q}\) and \(\mathcal{Q}\implies\mathcal{P}\) separately. (Exercise: use a truth table to show these propositions are indeed equivalent!)

Subsubsection Chains of implications/equivalences

The relation “\(\mathcal{P}\) implies \(\mathcal{Q}\)” is transitive: i.e., if \(\mathcal{P}\implies\mathcal{Q}\) and \(\mathcal{Q}\implies\mathcal{R}\text{,}\) then \(\mathcal{P}\implies\mathcal{R}\text{.}\) Similarly, the relation “\(\mathcal{P}\) is equivalent to \(\mathcal{Q}\)” is transitive. This allows us to prove an implication or equivalence via a chain of implications or chain of equivalences. When writing up a proof using this technique, use a vertically aligned format like the example below, treating one implication or equivalence per line, and adding a brief justification to the right:

\begin{align*} \mathcal{P} \amp \iff \mathcal{P_1}\amp\text{(justification)}\\ \amp \iff \mathcal{P_2}\amp\text{(justification)} \\ \amp \phantom{=}\vdots\\ \amp \iff \mathcal{P_n}\amp\text{(justification)} \\ \amp \iff \mathcal{Q}\amp\text{(justification)}\text{.} \end{align*}

It is also possible to build an argument as a hybrid chain of equivalences and implications. In this case the chain is only as strong as its weakest link. For example, a chain of the form

\begin{align*} \mathcal{P} \amp\iff\mathcal{Q} \amp\text{(justification)} \\ \amp\implies \mathcal{R} \amp\text{(justification)} \\ \amp\iff \mathcal{S} \amp\text{(justification)} \end{align*}

only shows that \(\mathcal{P}\implies\mathcal{S}\text{.}\) Indeed, we will have \(\mathcal{P}\iff\mathcal{S}\) if and only if the intervening implication \(\mathcal{Q}\implies\mathcal{R}\) is in fact an equivalence (i.e., the arrow goes both ways).

Warning 0.5.2.

It is often tempting, for the sake of space, to try and prove an equivalence \(\mathcal{P}\iff\mathcal{Q}\) via a chain of equivalences, as opposed to showing \(\mathcal{P}\implies \mathcal{Q}\) and \(\mathcal{Q}\implies\mathcal{P}\) separately. When proceeding in this manner, make doubly sure that each \(\iff\) is indeed an equivalence: i.e., that the implication arrow really goes both ways at each step. Even if each step in your chain truly is an equivalence, you should consider whether this will be obvious to your reader.

The example below provides the proof that a function is invertible if and only if it is bijective (Theorem 0.2.11). The proof nicely illustrates some of the different techniques used for proving implications and equivalences. Additionally, it is a nice example of how to separate out cases of the argument into clearly distinguished steps.

Example 0.5.3. Proof: invertible is equivalent to bijective.

Let \(f\colon X\rightarrow Y\) be a function. Prove: \(f\) is invertible if and only if \(f\) is bijective.

Solution.

Let \(\mathcal{P}\) be the proposition that \(f\) is invertible, and let \(\mathcal{Q}\) be the proposition that \(f\) is bijective. We prove the equivalence \(\mathcal{P}\iff \mathcal{Q}\) by proving the two implications \(\mathcal{P}\implies \mathcal{Q}\) and \(\mathcal{Q}\implies\mathcal{P}\text{.}\)

Proof of \(\mathcal{P}\implies \mathcal{Q}\).

We must show that if \(f\) is invertible, then \(f\) is bijective. Assume \(f\) is invertible. Then \(f\) has an inverse \(f^{-1}\text{.}\) We show separately that \(f\) is injective and surjective, hence bijective.

\(f\) is injective.

We show \(f(x)=f(x')\implies x=x'\) via a chain of implications:

\begin{align*} f(x)=f(x') \amp \implies f^{-1}(f(x))=f^{-1}(f(x'))\\ \amp\implies x=x' \amp (f^{-1}\circ f=\id_X) \text{.} \end{align*}

\(f\) is surjective.

Let \(b\) be an element of \(Y\text{.}\) We must show that there is an \(x\in X\) such that \(f(x)=y\text{.}\) Letting \(x=f^{-1}(y)\text{,}\) we have

\begin{align*} f(x) \amp = f(f^{-1}(y))\\ \amp = y \amp (f\circ f^{-1}=\id_Y)\text{.} \end{align*}

Proof of \(\mathcal{Q}\implies\mathcal{P}\).

We must show that if \(f\) is bijective, then \(f\) is invertible. Assume \(f\) is bijective. First we define a function \(g\colon Y\rightarrow X\) as follows: for all \(y\in Y\text{,}\) let \(g(y)\) be the unique element \(x\in X\) such that \(f(x)=y\text{.}\) Note that our definition of \(g\) uses both that \(f\) is surjective (there is some element \(x\) such that \(f(x)=y\))) and injective (there is exactly one element \(x\) such that \(f(x)=y\)).

We now prove that \(g\) is the inverse of \(f\text{,}\) showing \(g\circ f=\id_X\) and \(f\circ g=\id_Y\) separately.

\(g\circ f=\id_X\).

Take any \(x\in X\) and let \(y=f(x)\text{.}\) By definition of \(g\text{,}\) we have \(g(y)=x\) and hence \(g(f(x))=g(y)=x\text{.}\) This proves \(g\circ f=\id_X\text{.}\)

\(f\circ g=\id_Y\).

Take any \(y\in Y\text{.}\) By definition of \(g\text{,}\) \(g(y)\) is the unique \(x\in X\) such that \(f(x)=y\text{.}\) Thus \(f(g(y))=f(x)=y\text{.}\) This proves \(f\circ g=\id_Y\text{.}\)

Subsubsection Proof by contradiction

The technique of proof by contradiction (or reductio ad absurdum) proves a proposition \(\mathcal{P}\) by (a) assuming the negation \(\neg\mathcal{P}\) is true, and then (b) using this assumption to derive a proposition \(\mathcal{Q}\) known to be false. The choice of falsehood \(\mathcal{Q}\) is completely up to the person providing the proof. However, in order for the proof to be convincing, it should be clear, either logically or because of theory assumed to be known, that \(\mathcal{Q}\) is indeed false.

Example 0.5.4. Proof by contradiction.

Prove by contradiction that \(0\) has no multiplicative inverse in the reals: i.e., there is no \(r\in\R\) such that \(r\cdot 0=1\text{.}\)

Solution.

We prove the claim by contradiction. Assume there is an \(r\in \R\) such that \(r\cdot 0=1\text{.}\) Since \(r\cdot 0=0\) for any \(r\in \R\) (a property of multiplication by 0), we have \(1=r\cdot 0=0\text{:}\) a contradiction since \(1\ne 0\text{.}\) We conclude that there is no \(r\in \R\) such that \(r\cdot 0=1\text{.}\)

Remark 0.5.5.

Proof by contradiction resembles, but is not quite the same thing as proving an implication via its contrapositive. Letting \(F\) denote an arbitrary falsehood (the \(\mathcal{Q}\) described above) what we do in a proof by contradiction is show that the implication \(\neg \mathcal{P}\implies F\) is true. Since \(F\) is false, and the implication is true, \(\neg \mathcal{P}\) must be false: equivalently, \(\mathcal{P}\) must be true.

Subsection 0.5.2 Equalities

Equality is not as simple as it may seem. In general an equality is a mathematical statement of the form

\begin{equation} \text{LHS}=\text{RHS}\text{.}\tag{0.5.1} \end{equation}

Here “LHS” and “RHS” stand for left- and right-hand side, respectively. What exactly such an equality means depends very much on what kind of mathematical objects the two sides of the equation are: e.g., numbers, sets, functions, etc. Below we discuss equality for objects of a particular type in detail. (See Subsection 0.5.3 and Subsection 0.5.4.) In all settings, the notion of equality will be transitive: i.e., if \(x=y\) and \(y=z\text{,}\) then \(x=z\text{.}\) We use transitivity implicitly when proving an equality via a chain of equalities as described below.

Subsubsection Chain of equalities

(0.5.1)

\begin{align*} \text{LHS} \amp =\text{something}\amp (\text{justifiction})\\ \amp =\text{something}\amp (\text{justifiction})\\ \amp \phantom{=}\vdots \\ \amp=\text{RHS} \amp (\text{justifiction})\text{.} \end{align*}

Warning 0.5.6.

Never attempt to prove an equality by starting off with the equality you wish to prove, and then deduce a series of further equalities ending in some inanity: e.g.,

\begin{align*} \text{LHS}\amp =\text{RHS} \\ \text{something}\amp=\text{something} \\ \amp\phantom{=}\vdots \\ 0 \amp = 0\text{.} \end{align*}

What this suggests is that you are in fact proving an implication: namely, if the desired equality is true, then \(0=0\text{.}\) Clearly this is not what we set out to prove! This type of fallacious argument is called “begging the question” (petitio princippii in Latin), as we assume that which was to be proven.

Subsection 0.5.3 Basic set properties

Subsubsection Set inclusion

Let \(A\) and \(B\) be sets. By Definition 0.1.3, to prove \(A\subseteq B\) we must show that for all elements \(x\) we have

\begin{equation*} x\in A\implies x\in B\text{.} \end{equation*}

This requires proving the implication above for a general element \(x\text{,}\) and we may use any of the techniques described in Implication and Chains of implications/equivalences to do so.

Subsubsection Set equality

Let \(A\) and \(B\) be sets. To prove \(A=B\) directly using Definition 0.1.2 we must show that for all elements \(x\) we have

\begin{equation*} x\in A \iff x\in B\text{.} \end{equation*}

To prove this universal equivalence, we must give an argument for the equivalence that holds for a general element \(x\text{.}\)

Alternatively, you can prove \(A=B\) by proving the two set inclusions \(A\subseteq B\) and \(B\subseteq A\) separately. This is equivalent to proving the two implications \(x\in A\implies x\in B\) and \(x\in B\implies x\in A\) separately.

Subsection 0.5.4 Basic function properties

Subsubsection Function equality

According to Definition 0.2.5, in order to show functions \(f\) and \(g\) are equal we must

show that \(f\) and \(g\) have the same domain \(X\) and codomain \(Y\text{,}\) and
show that \(f(x)=g(x)\) for all \(x\in X \text{.}\)

The universal quantifier “for all \(x\in X\)” of item (ii) gives this subtask the feel of proving an identity: we must show that equality \(f(x)=g(x)\) holds for all \(x\in X\text{.}\) By the same token, to show (ii) does not hold, it suffices to show that \(f(x)\ne g(x)\) for some \(x\in X\text{.}\)

Subsubsection Injective, surjective, bijective

Let \(f\colon X\rightarrow Y\) be a function.

Injectivity.

To show \(f\) is injective, we must show that the implication

\begin{equation*} f(x)=f(x')\implies x=x' \end{equation*}

holds for all \(x,x'\in \text{.}\) Frequently it will be convenient to prove the (universal) contrapositive:

\begin{equation*} x\ne x'\implies f(x)\ne f(x') \end{equation*}

for all \(x,x'\in X\text{.}\)

Similarly, to show \(f\) is not injective, we simply have to find \(x, x'\in X\) satisfying \(x\ne x'\) and \(f(x)=f(x')\text{.}\)

Surjectivity.

To prove \(f\) is surjective, we must prove the universal quantification:

\begin{equation*} \text{for all } y\in Y, \text{ there exists an } x\in X\ \text{ such that } f(x)=y\text{.} \end{equation*}

To prove \(f\) is not surjective, we must prove the negation of this proposition (Remark 0.4.9): i.e., there exists a \(y\in Y\) for which there is no \(x\in X\) with \(f(x)=y\text{.}\)

Bijectivity.

To show \(f\) is bijective directly using Definition 0.2.7, we must show that \(f\) is injective and surjective. This is equivalent to showing that for \(y\in Y\) there exists a unique element \(x\in X\) such that \(f(x)=y\text{.}\)

Alternatively, using Theorem 0.2.11 we can show that \(f\) is bijective by providing an inverse function \(f^{-1}\colon Y\rightarrow X\text{.}\)

Subsection 0.5.5 Mathematical induction

Mathematical induction is a technique for proving universal quantifications of the form

\begin{equation*} \text{For all integers } n\geq b, \, P(n)\text{,} \end{equation*}

where \(b\) is a fixed starting integer, called the base, and \(P\) is a predicate defined on the integers. If the setting makes clear that \(n\) ranges over integers, we write such propositions using logical notation as

\begin{equation*} \forall n\geq b\, P(n)\text{.} \end{equation*}

Subsubsection Proof by induction

Suppose \(P\) is a predicate of integers. To prove the proposition \(\forall n\geq b\, P(n)\) by induction (sometimes called weak induction), we proceed in two steps.

Base step.

Show that \(P(b)\) is true.

Induction step.

Prove the universal implication

\begin{equation*} \forall n\geq b\, P(n)\implies P(n+1)\text{.} \end{equation*}

In practice, if proving the implication \(P(n)\implies P(n+1)\) directly, this means we assume \(P(n)\) is true (the induction hypothesis), and use this assumption to show \(P(n+1)\) is true.

Remark 0.5.7. “Step 0” of induction.

When meeting a proposition in the wild that we wish to prove by induction, you should first take care to model the proposition in the form

\begin{equation*} \forall n\geq b\, P(n)\text{.} \end{equation*}

Make explicit the predicate \(P\) in question, as well as the base case \(b\text{.}\) We illustrate this preparatory “Step 0” in the examples below.

Example 0.5.8. Weak induction.

Prove the identity

\begin{equation*} \sum_{k=1}^n k=\frac{n(n+1)}{2} \end{equation*}

for all \(n\geq 1\text{.}\) Recall:

\begin{equation*} \sum_{k=1}^n k=1+2+\cdots +n\text{.} \end{equation*}

Solution.

We prove the proposition by induction.

Step 0: preparation.

The proposition is modeled logically as \(\forall n\geq 1 \, P(n)\text{,}\) where \(P(n)\) is the proposition that

\begin{equation*} \sum_{k=1}^n k=\frac{n(n+1)}{2}\text{.} \end{equation*}

Base step: \(n=1\).

The proposition \(P(1)\) is the statement that

\begin{equation*} 1=\frac{1(1+1)}{2}\text{,} \end{equation*}

which is clearly true.

Induction step.

We must show the universal implication

\begin{equation*} \forall n\geq 1\, P(n)\implies P(n+1)\text{.} \end{equation*}

Let \(n\geq 1\text{,}\) and assume \(P(n)\) is true: i.e.,

\begin{equation*} \sum_{k=1}^n k=\frac{n(n+1)}{2} \end{equation*}

The proposition \(P(n+1)\) states that

\begin{equation*} \sum_{k=1}^{n+1} k=\frac{(n+1)(n+2)}{2}\text{.} \end{equation*}

We prove this, assuming \(P(n)\text{,}\) via a chain of equalities:

\begin{align*} \sum_{k=1}^{n+1} k\amp= \sum_{k=1}^{n} k+(n+1) \\ \amp=\frac{n(n+1)}{2}+n+1\amp (\text{induction hyp.}) \\ \amp =\frac{n(n+1)+2(n+1)}{2}\\ \amp =\frac{(n+1)(n+2)}{2}\text{,} \end{align*}

as desired.

Having completed our base and induction steps, our proof is now finished.

So why does proof by induction work? In other words, why is it a valid proof technique? Imagine our propositions \(P(n)\) as forming an infinite ladder that we wish to ascend. Cautious climbers that we are, we only will step on a rung if we know the corresponding proposition is true. Knowing \(P(b)\) is true (the base step) allows us to step onto the first rung. The universal implication \(\forall n\geq b\, P(n)\implies P(n+1)\) (induction step) gives us a rule that says if rung \(n\) is secure (i.e., true), then so is rung \(n+1\text{.}\) Since this rule holds for all rungs (i.e., for all \(n\geq b\)), we can safely ascend the entire ladder!

Figure 0.5.9. Mathematical induction as ladder of propositions

Subsubsection Proof by strong induction

Suppose \(P\) is a predicate of integers. To prove the proposition \(\forall n\geq b P(n)\) by strong induction, we proceed in two steps.

Base step: \(n=b\).

Show that \(P(b)\) is true.

Strong induction step.

Prove the universal implication

\begin{equation*} \forall n\geq b\, \left(P(b)\land P(b+1)\cdots \land P(n)\right) \implies P(n+1)\text{.} \end{equation*}

This technique is called strong induction, as now the induction hypothesis is much stronger: to prove this implication directly we assume \(P(k)\) is true for all \(1\leq k\leq n\) (not just \(k=n\) as in weak induction), and use this assumption to show \(P(n+1)\) is true.

In fact, strong induction is, logically speaking, no stronger than weak induction. Both techniques apply to propositions of the form \(\forall n\geq b\, P(n)\text{,}\) and you are free to choose which form of induction to use each time. We typically use strong induction out of convenience, when the nature of the predicate \(P\) is such that we can prove \(P(n+1)\) most elegantly by assuming \(P(b), P(b+1), \dots, P(n)\text{,}\) as opposed to just \(P(n)\text{.}\) The following example is characteristic in this regard.

Example 0.5.10. Strong induction.

Prove that every integer \(n\geq 2\) can be written as a product of primes.

Solution.

We prove the statement by induction.

Step 0: preparation.

The proposition is modeled logically as \(\forall n\geq 2\, P(n)\text{,}\) where \(P(n)\) is the proposition that \(n\) is a product of primes.

Base step: \(n=2\).

The proposition \(P(2)\) asserts that \(2\) is a product of primes. This is true since \(2\) is itself prime, hence a product of one prime number.

Strong induction step.

We must show the universal implication

\begin{equation*} \forall n\geq 2\, \left( P(1)\land P(2)\land\cdots \land P(n)\right)\implies P(n+1)\text{.} \end{equation*}

Let \(n\geq 2\text{,}\) and assume \(P(k)\) is true for all \(2\leq k\leq n\text{:}\) i.e., for all such \(k\) we assume \(k\) can be written as a product of primes. We use this assumption to prove \(P(n+1)\text{:}\) i.e., that \(n+1\) is a product of primes. We proceed in two cases, depending on whether \(n+1\) is itself prime.

Case 1: \(n+1\) is prime.

If \(n+1\) is prime, then it is trivially a product of one prime number, just as with the base case.

Case2 : \(n+1\) is not prime.

If \(n+1\) is not prime, then we can factor \(n+1\) nontrivially as \(n+1=k_1k_2\text{.}\) Here “nontrivially” means that we have \(2\leq k_1,k_2\leq n\text{.}\) Using the strong induction hypothesis, we may assume that \(k_1\) and \(k_2\) are both products of primes: i.e., we have

\begin{align*} k_1 \amp=p_1p_2\cdots p_r \amp k_2=q_1q_2\cdots q_s\text{,} \end{align*}

where \(p_i\) and \(q_j\) are prime for all \(1\leq i\leq r\) and \(1\leq j\leq s\text{.}\) It follows that

\begin{equation*} n+1=k_1k_2=p_1p_2\cdots p_rq_1q_2\cdots q_s\text{,} \end{equation*}

and hence that \(n+1\) is also a product of primes, as desired.

Having completed the base and induction steps, our proof by induction is now finished.