Proof Techniques

Section 1 Proof Techniques

Subsection 1.1 Conditional Logic

Definition 1.1. Conditional Statement (“Implication”).

Let \(P,Q\) be logical statements. The conditional statement \(P\Rightarrow Q\) (read “\(P\) implies \(Q\)”, or “if \(P\text{,}\) then \(Q\)”) is true when either \(P\) is false, or when both \(P\) and \(Q\) are true:

Table 1.2.

\(P\)	\(Q\)	\(P\Rightarrow Q\)
T	T	T
T	F	F
F	T	T
F	F	T

Remark 1.3.

An equivalent form of \(P\Rightarrow Q\) is

\begin{equation*} (\lnot P) \vee Q \quad \text{("not-P, or Q")}. \end{equation*}

The negation of \(P\Rightarrow Q\) is

\begin{equation*} \lnot (P\Rightarrow Q) = P \wedge (\lnot Q) \quad \text{("P and not-Q")}. \end{equation*}

Proof.

That \(P\Rightarrow Q\) is equivalent to \((\lnot P)\vee Q\) can be proven with a truth table:

Table 1.4.

\(P\)	\(\lnot P\)	\(Q\)	\((\lnot P)\vee Q\)
T	F	T	T
T	F	F	F
F	T	T	T
F	T	F	T

(Note that the rightmost column of this table, the truth values of \((\lnot P)\vee Q\text{,}\) are all the same as the truth values in the definition of \(P\Rightarrow Q\text{.}\))

To prove the negation formula, we can use the above along with De Morgan's Laws:

\begin{align*} \lnot\bigl( P\Rightarrow Q\bigr) &\equiv \lnot\bigl( (\lnot P) \vee Q \bigr) && \text{using the equivalence above}\\ &\equiv \lnot(\lnot P) \wedge (\lnot Q) && \text{by De Morgan's Laws}\\ &\equiv P \wedge (\lnot Q). \end{align*}

Definition 1.5. Contrapositive.

The contrapositive of the implication \(P\Rightarrow Q\) is the implication

\begin{equation*} (\lnot Q)\Rightarrow (\lnot P) \qquad \text{(not-Q implies not-P)}. \end{equation*}

Remark 1.6.

The contrapositive of \(P\Rightarrow Q\) is equivalent to \(P\Rightarrow Q\text{.}\) So the contrapositive can be useful to prove \(P\Rightarrow Q\text{:}\) it is often easier to follow.

Proof.

We can prove that \(P\Rightarrow Q\) is equivalent to \((\lnot Q)\Rightarrow (\lnot P)\) using the result of Remark 1.3 as follows:

\begin{align*} (\lnot Q)\Rightarrow (\lnot P) &\equiv \bigl( \lnot (\lnot Q) \bigr) \vee (\lnot P) && \text{by the Remark}\\ &\equiv Q\vee (\lnot P)\\ &\equiv (\lnot P)\vee Q && \text{by symmetry of "or"}\\ &\equiv P\Rightarrow Q && \text{by the Remark}. \end{align*}

Definition 1.7. Converse and Inverse.

The converse of the implication \(P\Rightarrow Q\) is the implication \(Q\Rightarrow P\) (“\(Q\) implies \(P\)”, or “if \(Q\text{,}\) then \(P\)”).

The inverse of the implication \(P\Rightarrow Q\) is the implication \((\lnot P) \Rightarrow (\lnot Q)\) (“not-\(P\) implies not-\(Q\)”).

Warning 1.8.

An implication is not necessarily equivalent to its converse! In other words, \(P\Rightarrow Q\) and \(Q\Rightarrow P\) are in general logically independent statements. We cannot use either to prove the other, so you should never confuse or replace one by the other!

Remark 1.9.

The converse and inverse of an implication are each other's contrapositive (for example, the converse is the contrapositive of the inverse). So in particular they are equivalent one to another! This means the four different implications associated with two logical statements fall into two pairs of equivalents:

Table 1.10.

Implication	Inverse
\(P\Rightarrow Q\)	\(Q\Rightarrow P\)
is equivalent to	is equivalent to
\((\lnot Q)\Rightarrow (\lnot P)\)	\((\lnot P)\Rightarrow (\lnot Q)\)
Contrapositive	Converse

Definition 1.11. Biconditional Statement.

The biconditional statement denoted \(P \Leftrightarrow Q\) and read “\(P\) if and only if \(Q\)”, is the conjunction of the implication \(P\Rightarrow Q\) and its converse \(Q\Rightarrow P\text{:}\)

\begin{equation*} P\Leftrightarrow Q \equiv \bigl( P\Rightarrow Q \bigr) \wedge \bigl( Q\Rightarrow P\bigr). \end{equation*}

In other words, \(P\Leftrightarrow Q\) is true exactly when “\(P\) implies \(Q\) and also \(Q\) implies \(P\)”.

Remark 1.12.

Only when the biconditional \(P\Leftrightarrow Q\) is true do we know that all four of the implications in Table 1.10 are equivalent!

Subsection 1.2 Quantified Logic

Definition 1.13. Universal Quantifier.

The universal quantifier “for-all”, denoted \(\forall\text{,}\) describes a parameterized family of logical statements \(P(x)\) which are true every time \(x\) belongs to a given set \(S\text{:}\)

\begin{align*} \forall x \in S, \; P(x) & \qquad \equiv \qquad&& (x \in S) \Rightarrow P(x).\\ \text{"For all x in S, we have P(x)."} & && \text{"If x is in S, then P(x)."} \end{align*}

Definition 1.14. Existential Quantifier.

The existential quantifier “there-exists”, denoted \(\exists\text{,}\) describes one of a parameterized family of logical statements \(P(x)\) which is true for at least one \(x\) in a given set \(S\text{:}\)

\begin{align*} \exists x \in S, \; P(x) & \qquad \equiv \qquad&& (x \in S) \wedge P(x).\\ \text{"There exists an x in S, such that P(x)."} & && \text{"P(x) is true, and x belongs to S."} \end{align*}

Remark 1.15. Negating quantified statements.

The universal statement \(\forall x\in S, \; P(x)\) is false when it fails for at least one \(x\text{:}\)

\begin{equation*} \lnot\bigl( \forall x\in S, \; P(x) \bigr) \, \equiv \, \exists x\in S, \; \lnot P(x). \end{equation*}

The existential statement \(\exists x\in S, \; P(x)\) is false when it is false for every \(x\text{:}\)

\begin{equation*} \lnot\bigl( \exists x\in S, \; P(x) \bigr) \, \equiv \, \forall x\in S, \; \lnot P(x). \end{equation*}

Remember: negation turns \(\forall\) into \(\exists\) and vice versa. Think: what evidence would be needed to prove this claim is false? “For all” is false if even a single example fails; “there exists” is false only if all possible examples fail.

Proof.

These can be proven by combining the definitions of the quantifiers with the negation forms in Remark 1.3. To negate the universal:

\begin{align*} \lnot\bigl( \forall x\in S,\; P(x)\bigr) &\equiv \lnot\bigl( (x\in S)\Rightarrow P(x)\bigr) && \text{Definition of }\forall\\ &\equiv (x\in S)\wedge (\lnot P(x)) && \text{Negation of implication}\\ &\equiv \exists x\in S, \lnot P(x) && \text{Definition of }\exists \end{align*}

To negate the existential:

\begin{align*} \lnot\bigl( \exists x\in S,\; P(x)\bigr) &\equiv \lnot\bigl( (x\in S)\wedge P(x)\bigr) && \text{Definition of }\exists\\ &\equiv \lnot (x\in S) \vee (\lnot P(x)) && \text{De Morgan's Laws}\\ &\equiv (\lnot P(x)) \vee \lnot(x\in S) && \text{symmetry of "or"}\\ &\equiv \lnot(\lnot P(x)) \Rightarrow \lnot (x\in S) && \text{Definition of }\Rightarrow\\ &\equiv (x\in S) \Rightarrow (\lnot P(x)) && \text{Contrapositive of above}\\ &\equiv \forall x\in S, \; \lnot P(x)&& \text{Definition of }\forall \end{align*}

Subsection 1.3 Proof Strategies

Definition 1.16. Direct Proof.

A direct proof of the implication \(P\Rightarrow Q\) follows the form

Suppose \(P\text{.}\) (Assume that \(P\) is true.)
We wish to show \(Q\text{.}\) (Deduce that \(Q\) is true.)

Definition 1.17. Proof by Contrapositive.

A proof by contrapositive of the implication \(P\Rightarrow Q\) is a proof of its contrapositive \((\lnot Q)\Rightarrow (\lnot P)\text{.}\) The core of the proof is \(direct\text{,}\) so it follows the form

Suppose \(\lnot Q\text{.}\) (Assume that \(Q\) is false.)
We wish to show \(\lnot P\text{.}\) (Deduce that \(P\) is false.)

Remark 1.18.

Writing out the formal definitions of terms is extremely helpful in discovering a proof. Try to lay out all definitions involved, and see how they connect. Often a proof following one of the above forms can be found by writing out the definitions involved in the beginning and the end, and working to see how they might meet in the middle!

Definition 1.19. Proof by Contradiction.

A proof by contradiction of the implication \(P\Rightarrow Q\) is a proof that its negation \(P\wedge (\lnot Q)\) must be false, because a “contradiction” \(R\wedge (\lnot R)\) may be deduced from it. It has the form

Suppose \(P \wedge (\lnot Q)\text{.}\) (Assume that \(P\) is true, but \(Q\) is false.)
We wish to show that \(R\text{.}\) (Deduce that some statement \(R\) is true.)
However, we also will show \(\lnot R\text{.}\) (Deduce that that same \(R\) is also false.)
Since both (2) and (3) cannot simultaneously hold, our assumption (1) cannot hold. Thus, \(P\Rightarrow Q\) must be true.

Remark 1.20.

Proof by contradiction can be useful because it allows you to stipulate (assume the truth) of two statements, \(P\) and \(\lnot Q\text{.}\) This can give you more to work with.

However, we often don't know ahead of time what statement \(R\) will be contradicted. In fact \(R\) is often unrelated to the material of \(P\) and \(Q\text{.}\) Often you don't need to explicitly prove \(R\text{:}\) it may be a statement known to be true from elsewhere. For example, you might deduce in your proof that “\(1/2\) is an integer”, which is the negation of “\(1/2\) is not an integer” which you may have proven long ago in a different course.

Warning 1.21.

Sometimes, a proof writer will say “by contradiction” but their proof in fact follows the proof by contrapositive form. To avoid falling into this trap, ask yourself: what was the \(R\) that was both true and false? If \(R\) was in fact the same as \(P\text{,}\) then the proof is actually by contrapositive -- not contradiction. (This suggests it can be written more simply!)

Definition 1.22. Proving a Universal Statement.

To prove the universal statement \(\forall x\in S, \; P(x)\text{,}\) we must show that \(P(x)\) holds for every choice of \(x\in S\text{.}\)

We do this by using an arbitrary choice: “selecting” a (completely non-specific) element \(x\in S\) and then deducing the truth of \(P(x)\text{.}\) The form is:

Let \(x\in S\) be chosen arbitrarily.
We will show that \(P(x)\text{.}\) (Deduce that \(P(x)\) is true without using any knowledge about \(x\) beyond its belonging to \(S\text{.}\))
Since \(x\) was chosen arbitrarily, we have \(P(x)\) holds for all \(x\in S\text{.}\)

Remark 1.23.

The proof strategy for universal statements in Definition 1.22 is really a direct proof of the universal implication \((x\in S) \Rightarrow P(x)\text{.}\)

Definition 1.24. Proving an Existential Statement.

To prove an existential statement \(\exists x\in S, \; P(x)\text{,}\) we have two choices.

Constructive proof: Explicitly find, or construct, an example of an element \(x\in S\) for which \(P(x)\) is true. For example: a constructive proof of “There exists an even number \(x\) such that \(x\) is prime” might be:

\begin{equation*} \text{Let }x=2. \text{ Then }x\text{ is an even number and }x\text{ is prime.} \end{equation*}
Non-constructive proof: Prove by contradiction that non-existence is impossible. These proofs are sometimes considered less illuminating, but can be simpler to discover when you can't find the right “trick” to construct an example.

A non-constructive proof of “Let \(f(x)\) be a polynomial of degree 3. Then there exists \(a\in\mathbb{R}\) such that \(f(a)=0\)” might be:
1. Suppose this were untrue, and \(f(x)\neq 0\) for all \(x\in \mathbb{R}\text{.}\)
2. Then since \(f\) is a continuous function, either \(f(x) \gt 0\) for all \(x\text{,}\) or \(f(x) \lt 0\) for all \(x\) by the intermediate value theorem.
3. Since all polynomials diverge toward infinity, this means that \(\displaystyle\lim_{x\to -\infty} f(x) = \displaystyle\lim_{x\to +\infty}\text{,}\) that is, \(f\) either approaches \(+\infty\) on both ends, or it approaches \(-\infty\) on both ends.
4. But we know from calculus that this means the degree of \(f\) must be even, not odd, a contradiction. Thus our assumption that \(f(x)\neq 0\) for all \(x\in\mathbb{R}\) must be false.
This proof tells us nothing about “how to find” an \(a\) such that \(f(a)=0\) (that is, how to solve a cubic equation); but it nevertheless tells us that such an \(a\) must exist.

Definition 1.25. Proof by Cases.

Given a universal statement \(\forall x \in S,\; P(x)\text{,}\) a proof by cases is a choice of exhaustive subsets of \(S\text{,}\)

\begin{equation*} S = S_1 \cup S_2 \cup \cdots \cup S_n\; , \end{equation*}

and a separate proof of each of the universal statements \(\forall x \in S_i, \; P(x)\) for \(i=1,2,\ldots,n\text{.}\)

In other words, we come up with a list of separate conditions that \(x\) might satisfy, as long as every \(x\) is guaranteed to satisfy (at least) one of them, and prove the statement is true under each of those conditions (“cases”) one by one.

Remark 1.26.

A common use of proof by cases is for quantified statements over the integers, for which a different proof approach might be needed for even integers than for odd integers. For example:

Proposition 1.27.

For all integers \(n \in \mathbb{Z}\text{,}\) we have that \(n^2\) and \(n\) have the same parity.

Proof.

Case 1: If \(n\) is even. Then there exists \(k\in\mathbb{Z}\) such that \(n=2k\text{.}\) We then have

\begin{equation*} n^2 = (2k)^2 = 4k^2 = 2\bigl( 2k^2 \bigr) = 2 \bigl( k^\prime \bigr) \end{equation*}

and since \(k^\prime=2k^2\) is an integer, we see that \(n^2\) must be even as well.

Case 2: If \(n\) is odd. Then there exists \(k\in\mathbb{Z}\) such that \(n=2k+1\text{.}\) We then have

\begin{equation*} n^2 = (2k+1)^2 = 4k^2+2k+1 = 2\bigl( 2k^2 +k \bigr) + 1 = 2 \bigl( k^\prime \bigr)+1 \end{equation*}

and since \(k^\prime=2k^2+k\) is an integer, we see that \(n^2\) must be odd as well.

Since every integer \(n\) is either even or odd, this covers all cases and the proof is complete.

Definition 1.28. Proof by Induction.

To prove a statement quantified on the natural numbers, \(\forall n\in\mathbb{N}, \; P(n)\text{,}\) we can use a proof by induction of the following form.

Base case: Prove \(P(1)\) is true.
Inductive case: Prove that \(\forall k\in\mathbb{N}\text{,}\) we have \(P(k)\Rightarrow P(k+1)\text{.}\)
Conclude that \(P(n)\) is true for all natural numbers \(n\) by the Principle of Mathematical Induction.

Remark 1.29.

As an example, consider the statement

\begin{equation*} \text{For all natural numbers }n\text{, we have } 1+3+5+\cdots+(2n-1) = n^2. \end{equation*}

Usually, the base case in an induction is a simple statement that can be directly checked, since you can substitute \(1\) for \(n\text{.}\)

Here, the base case is found by substituting \(1\) for \(n\text{:}\)

\begin{align*} 1+3+5+\cdots+(2\cdot 1 - 1) &= 1^2 \\ 1+3+5+\cdots+1 & = 1^2 && \text{but we understand the LHS has only one addend:}\\ 1 &= 1^2 && \text{which is true.} \end{align*}

The inductive implication is usually proven with a direct proof. This begins by stipulating the inductive hypothesis, assuming that \(P(k)\) is true for an arbitrary natural number \(k\text{.}\) Do not overlook this assumption step!

\begin{equation*} \text{Let }k\in\mathbb{N}\text{ be chosen arbitrarily. Assume }1+3+5+\cdots+(2k-1)=k^2\text{ is true.} \end{equation*}

Then, we wish to show that \(P(k+1)\) holds, using the previous assumption. Many times, by writing out and manipulating \(P(k+1)\text{,}\) always looking back at what you assumed, you can see how the assumed true statement \(P(k)\) comes into play.

\begin{equation*} P(k+1): \quad 1+3+5+\cdots+\bigl(2(k+1)-1\bigr) = (k+1)^2 \end{equation*}

To prove this, notice that the unseen second-to-last term in the sum on the LHS is \((2k-1)\text{:}\)

\begin{align*} \underbrace{1+3+5+\cdots+(2k-1)}_{{}=k^2} + \bigl(2(k+1)-1) && \text{by using P(k)}\\ = k^2 + \bigl( 2(k+1)-1\bigr) \\ = k^2 + (2k+2-1) = k^2+2k+1 \\ = (k+1)^2 && \text{which establishes P(k+1) is true.} \end{align*}

Warning 1.30.

Every successful induction proof makes explicit use of the induction hypothesis \(P(k)\text{.}\) You should be able to circle the line of your proof where the assumed truth of that hypothesis was applied. If you cannot... either you have a correct proof that's not by induction, or you have a faulty proof by induction!

Worksheet 1.4 Proof Technique Workbook

Use a direct proof to prove the statements in #1-2.

1.

Prove that the square of a rational number is rational.

2.

Suppose that \(a,b,c\) are integers. Suppose that \(a^2\) divides \(b\text{,}\) and that \(b^3\) divides \(c\text{.}\) Prove that \(a^6\) divides \(c\text{.}\)

3.

Prove that if \(x\) and \(y\) are odd integers, then \(xy\) is an odd integer.

Use an indirect proof (contradiction or contrapositive) to prove the statements in #3-5.

4.

Prove that if \(n\) is a natural number, then \(\displaystyle\frac{n}{n+1} \gt \displaystyle\frac{n}{n+2}\text{.}\)

5.

Let \(n\in \mathbb{Z}\text{.}\) If \(n^2-6n+5\) is even, then \(n\) is odd.

6.

Prove that \(\sqrt{2}\) is an irrational number.

7.

Prove that if \(n^3\) is an odd integer, then \(\text{}\) is an odd integer.

8.

Prove the biconditional statement: Let \(m,n\) be integers. Then \(m\) and \(n\) have the same parity if and only if \(m^2+n^2\) is even.

9.

Prove by induction that for all natural numbers \(n\text{,}\) we have

\begin{equation*} 1+2+3+4+\cdots+n = \frac{n(n+1)}{2}. \end{equation*}

10.

Prove by induction that for all \(n\geq 9\text{,}\) we have \(n! \gt 4^n\text{.}\)