2.1: Foundational Proof Techniques - Proof Techniques

2.1: Foundational Proof Techniques

Throughout this section, we will introduce some of the more common proof techniques that are used to verify the truth of a mathematical statement. Remember, all of these techniques assume you have some basic information present and attempt to use the information you have to arrive at the correct conclusion.

It’s important that you’re familiar with the basics of propositional logic before proceeding. Chapter 1.4 serves as a sufficient primer.

Direct Proof

The direct proof is the simplest type of proof. In a direct proof, given certain information, we determine the validity of some other information. Direct proofs are often used in mathematical formulas, where simple arithmetic manipulations of given information can get us where we need to be.

Example

Consider $x, y, z \in \mathbb{Z}^+$. Prove that if $x | y$ and $x | z$, then $x | (y + z)$.

(The notation $a | b$ means “$a$ divides $b$”. Formally, $a | b$ means there is some integer $c$ such that $b = c \cdot a$. We will look at this further in Chapter 3.)

The first step in each proof is representing the information that we are allowed to assume, using precise mathematical notation. We are given that $x$ divides $y$ and that $x$ divides $z$. In mathematical notation, this means that there are integers $a_1$ and $a_2$ such that $a_1 \cdot x = y$ and $a_2 \cdot x = z$. Furthermore, since we are told $x, y$ and $z$ all belong to the set of positive integers, we know that $a_1, a_2$ must also be positive. There is not much more information we can garner from this now, so we look at what we are trying to prove.

By writing out equations relating $x$ and $y$ (and $x$ and $z$), we have concrete information that we can use in our proof. Then:

$y+z = a_1 \cdot x + a_2 \cdot x = (a_1 + a_2) \cdot x$

We have shown that $y+z$ can be written as some positive integer – precisely, $a_1 + a_2$ – multiplied by $x$, hence proving $x$ divides $y+z$. This example gives us the natural flavor of direct proofs – we assume and work with the information we have, and reformulate it to match what we want to prove in some capacity.

Proofs by contradiction stem from a really nice observation. The problem statement remains the same; we are trying to prove that some statement $S$ is true. We begin by assuming $\neg S$ – that is, that $S$ is false - and make a series of implications. One of these implications will state something that contradicts that $S$ is false. Since our initial assumption was that $S$ was false, we know this cannot be the case, thus $S$ must be true, proving our statement.

The contradiction can come about in many ways. For example, showing two things that cannot be equal as equal – such as $0 = 2$ – or showing some given information (which was told to us to be true) is false if statement $S$ is false. Whatever the contradiction might be, this proof technique presents a relatively straightforward way to prove the validity of the statement without worrying about the specific reason why the statement it holds. In specific, proofs by contradiction is powerful when trying to prove a statement which implies non-existence of some entity.

Example

Prove that there is no greatest even integer.

Let’s start by assuming that there is a greatest even integer. Let us call this greatest even integer $m$. Define $n$ to be $m+2$. Then, $n$ is an even integer and it is strictly greater than $m$. Hence, $m$ is not the greatest even integer, which contracts our earlier assumption. This means that there is no greatest even integer.

Example

Prove that the negative of an irrational number is irrational.

To prove this directly, we would need to show that there is no number for which this is not true. Instead, we go by the way of contradiction. We assume the statement is not true. The negation of this sentence states that there exists some irrational number $x$ such that $-x$ is rational. Put concretely, we have $-x = \frac{a}{b}$, for $a, b \in \mathbb{Z}$. We can multiply each side by $-1$ and obtain that $x = -\frac{a}{b} = \frac{-a}{b}$. This shows that $x$ is equal to the quotient of two integers, which proves it to be rational. But, we assumed $x$ to be irrational to begin with. A number can not be rational and irrational at the same time, so we have arrived at a contradiction. Hence, our initial assumption must have been incorrect, and there does not exist any irrational number for which its negation is rational.

Example

Prove that $\sqrt{2}$ is irrational.

This is a classic example of a statement that is proved with a contradiction. Let’s start by assuming that $\sqrt{2}$ is rational, meaning that we can write $\sqrt{2} = \frac{a}{b}$ for $a, b \in \mathbb{Z}$. Furthermore, let’s assume that this is the reduced form of the fraction, i.e. that $\text{gcd}(a, b) = 1$ (this is a crucial step in the proof). Then:

\begin{align*} \sqrt{2} &= \frac{a}{b} \\ 2 &= \frac{a^2}{b^2} \\ 2b^2 &= a^2 \end{align*}

Since we have $a^2 = 2b^2$, we know that $a^2$ must be even (as it can be written as $2 \cdot (\text{some integer})$). If $a^2$ is even, then we must have that $a$ is even (if you don’t believe it, the proof is later in this article!). This means we can say $a = 2k$ for $k \in \mathbb{Z}$. Then:

\begin{align*} 2b^2 &= (2k)^2 \\ 2b^2 &= 4k^2 \\ b^2 &= 2k^2 \end{align*}

Same logic applies: we now have that $b^2$ is even, and therefore $b$ is even.

Stop for a moment: can you spot the contradiction?

If both $a, b$ are even, then $\text{gcd}(a, b)$ is at least $2$. This contradicts what we stated earlier – we assumed that $\text{gcd}(a, b) = 1$. This implies that our original assumption was false, thus proving that $\sqrt{2}$ is indeed irrational.

Getting a handle on this proof technique is tricky, and only practice can really solidify a true understanding of it.

Proof by Contraposition

Recall from Chapter 1.4, the contrapositive of an implication $P \implies Q$ is $\neg Q \implies \neg P$. Implications and their contrapositives are logically equivalent statements. Contrapositives are useful in cases where we are asked to prove some statement $Q$ from some set of information $P$: instead of proceeding with a direct proof, we can instead assume that $Q$ is false ($\neg Q$) and make a series of logical deductions that imply that $P$ is false ($\neg P$). In many cases, this is easier to do than proving that $P$ implies $Q$ directly.

Example

Prove that if $x^2$ is even, then $x$ is even.

We could use a direct proof for this problem (you should try it on your own!), though we will use prove this through contraposition to introduce the general problem solving technique.

Here, $P$ is the statement “$x^2$ is even”, while $Q$ is “$x$ is even.” Thus, the contrapositive states that if $x$ is not even, then $x^2$ is not even either. Proving this will prove our original statement.

So we begin. If $x$ is not even, then $x$ is odd. Hence, $x^2$ is the product of two odd numbers, which in itself is odd. So, $x^2$ is not even, and we have proven the contrapositive. The validity of our original statement is then asserted.

Just because our problem statement looks like an implication, doesn’t mean we need to use a proof by contraposition.

Our initial statement that we negate can also be an implication! Suppose we want to show that $P \implies Q$. This is equivalent to showing that $\neg P \vee Q$ is always true. To show a contradiction, we can start by assuming $\neg (\neg P \vee Q)$, i.e. $P \wedge \neg Q$, and showing a contradiction.

Suppose we want to show that $x^2 \text{ is even} \implies x \text{ is even}$, i.e. that $(x^2 \text{ is odd} \vee x \text{ is odd})$ always holds a true value. The negation of this looks like $x^2 \text{ is even} \wedge x \text{ is odd}$.

If we assume the negation to be true, we have that $x^2$ is even and $x \text{ is odd}$. If we suppose $x$ is odd, we can write it as $2k + 1, k \in \mathbb{Z}^+$, and we can write $x^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$. However, this proves that $x^2$ must be odd if $x$ is odd, meaning that the assumption $x^2 \text{ is even} \wedge x \text{ is odd}$ was false. Thus, the original statement $(x^2 \text{ is odd} \vee x \text{ is odd})$, i.e. $x^2 \text{ is even} \implies x \text{ is odd}$, is true.

Vacuous Proofs

Remember, implications are nothing but logical expressions with a truth value. By proving an implication, we are proving that the truth value of an implication is true. Many of the proof statements that we’ve seen so far require us to prove something of the form $P \implies Q$, and we assume that $P$ is true. The only way for $P \implies Q$ to have a value of true when $P$ is true, is for $Q$ to be true.

$P$ $Q$ $P \implies Q$ $\neg P \vee Q$
True True True True
True False False False
False True True True
False False True True

However, the implication $P \implies Q$ is also true whenever $P$ is false. Consider the following statement:

If the earth is flat, then all dogs can fly.

The truth value of this implication, is true! This is because the earth is certainly not flat (we won’t prove that here… maybe ask Kyrie Irving?). If we let $P$ represent “the earth is flat” and $Q$ represent “all dogs can fly”, since $P$ is false, it doesn’t matter what $Q$ is: $P \implies Q$ is a true value.

One way to think of this is, if the left hand side $P$ is true, the laws of our universe don’t hold. But if the laws of our universe don’t hold, then anything is possible – it doesn’t matter if $Q$ is true or false.

Example

Prove that if $2x^2 - 4x + 2 < 0$, for $x \in \mathbb{R}$, then $5 > 7$.

Usually, we assume the left hand side to be true, but let’s look a little further here. The quadratic $2x^2 - 4x + 2$ can be written as $2(x-1)^2$, which sits on the $x$-axis. Therefore, it has a minimum value of $0$, and is never less than $0$. This means the left hand side is always false, thus the implication is always true.

This may seem a little confusing – we’re not proving $5 > 7$. We’re only showing that if $2(x-1)^2 < 0$ (for some real $x$), then $5 > 7$.

Proof by Cases

In many instances, we may find it easier to view a statement as the combination of many sub-cases. By proving each possible sub-case, we can prove the validity of the full statement. The technique we use for each sub-case can be any one of the above.

Example

Prove that the cube of any integer is either a multiple of 9, 1 more than a multiple of 9, or one less than a multiple of 9.

The cases we break this proof into may seem rather arbitrary, but the more we practice this sort of proof, the more natural it will seem.

Our proof revolves around the fact that when dividing an integer by 3, there are 3 possible remainders – 0, 1, or 2.

• Case 1: $n = 3k$
First, we look at numbers that are divisible by 3, which we can represent as $3k$ for some positive integer $k$. Cubing $n$, we get $n^3 = (3k)^3 = 27k^3 = 9(3k^3)$. Clearly, for all $k$, this is a multiple of $9$, therefore we’ve proved the statement for all integers that are multiples of 3.

• Case 2: $n = 3k + 1$
Next, we explore the case where there is a remainder of 1 after dividing by 3, so the number is $3k + 1$ for some $k$. Cubing $n$ yields $n^3 = (3k+1)^3 = 27k^3 + 27k^2 + 9k + 1 = 9(3k^3 + 3k^2 + k) + 1$, which shows that in this case $n^3$ is 1 greater than a multiple of 9. Thus, we’ve proved the statement for all integers that have remainder 1 when divided by 3.

• Case 3: $n = 3k + 2$
The last case is when a number has a remainder of 2 when being divided by 3. This means we can write $n$ as $3k+2$; equivalently, we can write $n$ as being 1 less than a multiple of 3, i.e. $n = 3k - 1$ (think about why this is true). Then, $n^3 = (3k-1)^3 = 27k^3 - 27k^2 + 9k - 1 = 9(3k^3 - 3k^2 + k) - 1$, which shows in this case that $n^3$ is 1 less than a multiple of 9. Now, we’ve proved the statement for all integers that have remainder 2 when divided by 3.

We have considered three cases, and these three cases make up the whole universe of integers. Either an integer is divisible by 3, one more than a multiple of 3, or 2 more than a multiple of 3 (and consequently, 1 less than some other multiple of 3). The statement holds for these three cases, so it holds for every integer.

Counterexamples

“Proof by Counterexample” isn’t a proof technique. Instead, we use counterexamples to show that statements aren’t true. For example, to prove that not all dogs are labradors, we would have to show there exists at least one dog that isn’t a labrador.

Example

Prove or disprove: All Pythagorean triplets are of the form $(3k, 4k, 5k)$ for $k \in \mathbb{R}$.

Consider the triplet $(8, 15, 17)$. We have that $8^2 + 15^2 = 17^2$, but $(8, 15, 17) \neq (3k, 4k, 5k)$ for any real number $k$. This is a counterexample, so the original statement is not true.

Faulty Proofs

To round up our discussion, let’s take a look at a few convincing arguments that look like proofs, but have some holes in them.

Example

Prove $1 = 2$.

Let $x = y$. Then:

\begin{align*} x^2 &= xy \\ x^2 - y^2 &= xy - y^2 \\ (x+y)(x-y) &= y(x-y) \\ x + y &= y \\ 2y &= y \\ 2 &=1 \end{align*}

Where did we go wrong? Try and identify the issues with the above proof before reading ahead.

• Since $x = y$, $x - y = 0$. From the third to fourth line, we divided by $0$, which is not a valid step.
• In the second last step, to solve $2y = y$, we re-arrange so that we have $y$ on one side. What we did, dividing by $y$, is problematic as $y$ could’ve been $0$.

Let’s look at another proof of the same statement:

“Assume $1 = 2$. Multiply both sides by $0$, yielding $0 = 0$. This is a true statement, therefore $1 = 2$.”

Where was the mistake in the proof? The arithmetic was sound; both sides multiplied by 0 is, indeed, 0. No step we made was incorrect, so we have to go back to our initial assumption. We assumed what we were trying to prove, which is a common mistake when writing proofs. This can cause us to falsely prove a lot of false things, including that every number is equal (by our proof above).

Faulty Logic

Some other pieces of faulty logic found in proofs include:

• Dividing by something which could be 0
• Not switching inequalities when working with negative numbers
• Using an example as a proof for a statement which applies to multiple cases
• Introducing a variable twice with two different values

In closing, there are multiple ways to prove any one statement. They may all use the same proof technique, but use the given information differently. In the next article, we will round out our proof toolbox with a more complicated proof technique – mathematical induction.