Common Proof Types

Note: If you're familiar with proofs, you might find this one simple, so feel free to skip it.

Direct proof

Many statements can be proven directly. By this, I mean that to prove the statement $P \Rightarrow Q$, we assume that $P$ is true and deduce that $Q$ must be true. There's nothing more direct than this!

Let's describe some examples. You're probably familiar with what “even” and “odd” means, but since we want to be precise about things, let's define them here. We say an integer $n$ is even if there exists an integer $k$ such that $n = 2k$. We say an integer $n$ is odd if there exists an integer $k$ such that $n = 2k+1$. For example,

Now, let's prove something basic about evenness.

Proposition 1. Let $x$ be an integer. If $x$ is even, then $x^2$ is even.

Proof. We prove it directly and assume that $x$ is even. By definition, $x = 2k$ for some integer $k$. Thus, $x^2 = (2k)^2 = 4k^2 = 2(2k^2)$. Since there exists an integer $l$ such that $x^2 = 2l$ (namely $l = 2k^2$), we conclude that $x^2$ even.

I know that showing that the square of an even number is also even is pretty basic. But it illustrates the idea behind proofs, and direct proofs in particular.

Here's another one.

Proposition 2. The sum of two odd numbers is even.

Before we go into the proof, notice that this statement is not of the form $P \Rightarrow Q$. But we can rephrase it to be of that form: "If $x$ and $y$ are odd numbers, then $x+y$ is even."

Proof. Let's prove directly and assume $x$ and $y$ are odd. By definition, there are integers $k$ and $l$ such that $x = 2k+1$ and $y = 2l+1$. Thus, $x+y = 2k+1 + 2l+1 = 2(k+l+1)$, proving that $x+y$ is even.

You can probably find the proofs of the following statements yourself:

Proposition 3. The sum of two even numbers is even.

Proposition 4. The sum of an odd number and an even number is odd.

Proposition 5. The product of two odd numbers is odd.

Please try proving them as simple exercises.

Proof by contrapositive

This style of proof is more indirect. To prove $P \Rightarrow Q$, we prove its contrapositive instead, which is $\neg Q \Rightarrow \neg P$, because they are logically equivalent.

In our example, we will need the following statement:

Proposition 6. For every integer $x$, either $x$ is even or $x$ is odd, but not both.

In other words, the statement “$x$ is not odd” and “$x$ is even” are equivalent, as well as “$x$ is not even” and “$x$ is odd”.

It sounds very obvious, but looking at the definition of “even” and “odd”, this statement doesn't obviously follow. Thus we need to prove it. However, proving it requires another statement called the well-ordering theorem which will be explained some time in the future, so for now let's just accept this statement as fact.

Now, the example.

Proposition 7. If $x^2$ is odd, then $x$ is odd.

Proof. The contrapositive of this statement is “If $x$ is not odd, then $x^2$ is not odd.” But note that “$x$ is not odd” is the same as “$x$ is even”. Thus, it is equivalent to “If $x$ is even, then $x^2$ is even”. But this is just Proposition 1! Thus, we have proven the statement.

You can try proving the following as exercise.

Proposition 8. If $x^2$ is even, then $x$ is even.

Proof by contradiction

Another indirect proof method is proof by contradiction. As explained in Chapter 2 of MIT 6.042J, this goes by assuming that the thing you're proving is false, and trying to derive a contradiction. This turns out to be useful because by assuming the statement is false, you're basically increasing the number of assumptions you have.

Here's the prototypical example. Recall that a number is rational if it is a ratio of two integers. A number that is not rational is called an irrational number.

Proposition 9. $\sqrt{2}$ is irrational.

Proof. Suppose, for the purpose of contradiction, that $\sqrt{2}$ is rational. Then $\sqrt{2} = p/q$ for some integers $p$ and $q$. We can choose $p$ and $q$ so that they don't have any common factors.

The equation above is equivalent to $2q^2 = p^2$. This means that $p^2$ is even. Proposition 8 says that $p$ is even. So $p = 2r$ for some integer $r$. Thus, $2q^2 = (2r)^2 = 4r^2$, so $q^2 = 2r^2$. But this means that $q^2$ is even. Again, proposition 8 says that $q$ is even. Now, $p$ and $q$ are both even, which means they share a common factor of $2$. This is a contradiction because we assumed that they don't have common factors! So the claim is true after all.

Here's a generalization of the above which you can try to prove yourself.

Proposition 10. $\sqrt{n}$ is irrational whenever $n$ is not a perfect square.

For the future

Note that (almost) everything we proved so far are very simple. And that's because they're only intended to demonstrate how proofs work. Rest assured, we won't go around trying to prove every tiny statement in math! When we get to the actual stuff, we will just take many familiar facts you know (such as commutativity of addition, etc.) to be true without proof.