Proof

What are all the different types of proof?

Direct proof, proof by contraposition, proof by contradiction, non-constructive proof, constructive proof, proof by cases/exhaustion

What is direct proof?

Start with your assumptions and directly deduce your conclusions. e.g.

Theorem 2.1.

If m and n are odd integrers, then mn is also odd.

Proof:

Since m and n are odd integers, there are integers j and k such that m = 2j + 1 and n = 2k+1 . But then mn = (2j +1)(2k+1) = 2(2jk+j +k)+1 . Since (2jk+j +k) is an integer, we see that mn is odd.

What is proof by contraposition?

The statement ‘if P, then Q ’ is equivalent to the statement ‘if not Q, then not P.’ It is sometimes easier to prove the contrapositive.

Theorem 2.2.

Let n be an integer. If n² is even, then n is even.

Proof.

Suppose that n is not even. Then n is odd. Letting n = m in Theorem 2.1, we see that nm = n² is odd. Hence if n is not even, n² is not even. Thus if n² is even, n is even.

What is proof by contradiction?

We assume some statement to be true and then show that this implies a contradiction or absurdity, which implies that the statement must be false.

Theorem 2.3.

The square root of 2 is irrational.

Proof.

Suppose that √2 is rational. Then there are integers p and q such that √2 = p/q. By cancelling common factors, we may assume that p and q have no common factors. Since q√2 = p , we see that p² = 2q² is even. By Theorem 2.2, it follows that p is even

and there is some integer r such that p = 2r . But then 2q² = p² = (2r)² = 4r², so that q² = 2r² is even. However, if p and q are both even, then they have a common factor of 2. This contradicts the fact that they have no common factor. Hence, √2 is not rational.

What is a non-constructive proof?

In a non-constructive proof, we conclude that something must be true by showing that a particular thing must exist, without being able to give an explicit instance of that thing. The most famous (and controversial) example is Cantor’s proof that the real numbers are uncountably infinite. Here we present an example due to Dov Jarden from the 1950s.

Theorem 2.4.

An irrational number to an irrational power can be rational.

Proof.

By Theorem 2.3, √2 is irrational. If √2^√2 is rational then we are done. If √2^√2 is irrational, then (√2^√2)^√2 = √2^√2√2 = √2² = 2 is rational.

Notice that in this proof we do not know whether the example of an irrational power of an irrational being rational is √2^√2 or (√2^√2)^√2.

What is a constructive proof?

In a constructive proof, we explicitly come up with instance showing that something is true. For example, e and log 2 are both irrational and by definition e^log2 = 2 , which proves Theorem 2.4. However, proving that e is irrational is non-trivial. Here is an alternative constructive proof. First we need a lemma.

Lemma 2.5.

The number log₂ 9 is irrational.

Proof.

Suppose that log₂ 9 is rational, so that there are non-zero integers p and q such that log₂ 9 = p/q . By the definition of log₂, 2^p/q = 2^{log₂ 9} = 9 . This implies that 2^p = 9^q. However, a similar proof to that of Theorem 2.1 shows that 9^q is odd, where as 2^p

is even. This contradiction implies that log₂ 9 must be irrational.

We now have a constructive proof of Theorem 2.4:

Proof.

From the above, √2 and log₂9 are both irrational, but √2^{log₂ 9} = √2

log2⁽⁹⁾ = √2^{2 log₂ 3}2^{log₂ 3} = 3

What is proof by cases/exhaustion?

Work through every case