Modes of Proof

To fully grasp mathematical arguments one must understand the underlying logic and proof structure. We have already given a fair treatment of the logic underlying mathematics, so we will now explore proofs. There are three varieties of proof: direct proofs, proofs by contradiction and proofs by mathematical induction. When to use each of the three changes from problem to problem, but often proofs by mathematical induction can be easily spotted. In the upcoming subsections I will give an account of each type of proof and give classical examples of each. For those who have taken an analysis class, these should be very familiar (in fact, you can probably guess which I will use).

DIRECT PROOFS

In a direct proof, one attempts to prove a proposition true from the basic assumptions stated within the proposition. An example of such a proof would be as follows. Show that the sum of two even integers is again an even integer*. We will prove this statement momentarily, but first we must first know what it means to say an integer is even. 

Definition: An integer, z, is even iff** it can be written in the form z = 2k for some integer k. (Equivalently, we say that z is divisible by 2.)

Definition: An integer, y, is odd iff it can be written in the form y = 2j + 1 for some integer j. (Equivalently, we can say that y is not even.)

Why do we choose to use this definition for evens and odds? For starters, it is very convenient notation. I will illustrate the definitions with examples. 2 = 2*1, 0 = 2*0, 4 = 2*2, and so on. The definition seems to make sense. How about the definition for the odds? 1 = 2*0 + 1, -1 = -1*2 + 1, 3 = 2*1 + 1, and so on. This definition seems to be consistent and logical as well. With this in mind, we can prove the aforementioned statement.

Example: Show the sum of two even integers is again even.

Proof: Let x and y be even integers. If x and y are even integers they can be written in the form x = 2j and y = 2k for some integers j and k. We wish to look at the sum of x and y, i.e.: x + y.

x + y = 2j + 2k = 2*(j + k). Because j and k are integers, their sum is again an integer*, call it m. Then, x + y = 2*m. Because m is an integer, 2*m is an even integer (by definition!), and therefore x + y is an even integer.

Q.E.D. (quod erat demonstrandum - Latin for "which was to be shown"). Q.E.D. has historically been used to signify the completion of proofs and I will adopt this convention as well. However, you can use whatever you wish to signify the end of your own proof.

In the realm of proofs this is among the simplest, but it is an instructive example. As you can see, we only used properties we already knew and what was given to arrive at the conclusion. In the next section we will see that the execution of a proof by contradiction is very different in setup.

PROOF BY CONTRADICTION

Proof by contradiction is a very powerful tool. The methodology outlining a proof by contradiction is as follows. Suppose you believe a proposition to be true, but a direct proof proved (hah!) fruitless. A possible avenue to explore would be a proof by contradiction. What you wish to do is assume that what you believe to be true is actually false and follow the steps of a direct proof. If at some point you reach a contradiction that logically followed from assuming your proposition was indeed false, then the only possible alternative is that what you actually set out to disprove is actually true (as you hoped!). 

The reason behind why a proof by contradiction is a valid mode of proof stems from the definition of a proposition. It can only be true or false and not both. If we arrive at a contradiction at some point in the proof (i.e. a proposition is true and false, like 2 is even and odd - obviously we know it is even), then we should be forced to reject that what we initially said was false (since it led to mathematical impossibilities) and accept that it was actually true.

A classic example if the proof that the square root of two is irrational. Before we delve into the proof, we must first understand what it means for a number to be irrational, and to understand this requires that we know what it means for a number to be rational.

Definition: A number is said to be rational iff it can be expressed as [; \frac{a}{b} ;], where a and b are integers (with b not being zero of course!). Examples would be [; \frac{1}{2} ;], [; \frac{-2}{3} ;], [; \frac{1}{1} ;], and so on. A follow-up question to this is: are all integers rational numbers? (I will leave this to you to consider.)

Definition: A number is said to be irrational iff it is not rational. Examples of irrational numbers you probably know are π, e (Euler's number), and φ (the golden ratio).

Before we show that the square root of two is irrational, we must establish an important fact: if a^2 is divisible by two (for some integer a) then a is divisible by two. This can be done by contradiction, in fact.

Proof: Take a^2 to be divisible by two to be true (i.e., a^2 is even). Assume that a is not divisible by two. If a is not divisible by two, then a = 2k + 1 for some integer k. a^2 then becomes 4k^2 + 4k + 1. Then, a^2 = 2(2k^2 + 2k) + 1. 2k^2 + 2k is an integer, call it y. Then, a^2 = 2y + 1, yet we said that odd integers were by definition of this form! This conflicts with our initial assumption that a^2 is even, so we conclude that if a^2 is even, a must be even.

Now we can begin our proof. We will assume that the square root of two is not irrational (i.e., it is rational). If the square root of two is rational, it can be written as the ratio of two integers a and b (again, b cannot be 0). Without loss of any generality, we will assume that a and b have no common divisors - and if they do, we will divide them out ahead of time.

[; \sqrt{2} = \frac{a}{b} ;]. Because it is impractical to work with square roots, we will square both sides of the equation to end up with:

[; 2 = \frac{a^2}{b^2} ;]. Again, this is not quite a practical form to work with, so we will multiply both sides by b^2 to obtain:

[; a^2 = 2b^2 ;]. We see that a^2 is an even integer, but from what we just proved, a must then be an even integer, so we will write a = 2a', for some integer a'. Substituting this expression for a into our previous expression yields

[; 4(a')^2 = 2b^2 ;] which yields [; b^2 = 2(a')^2 ;]. This says that b^2 is an even integer, therefore b must be an even integer as well, so we can write b = 2b' for some integer b'. At this point something weird seems to be going on. Both a and b were even integers, and therefore had a mutual divisor of 2, but we assumed that both a and b had no mutual divisors. At this point we have reached a contradiction: a and b have common divisors and they do not. From this and the previous reasoning, we conclude that our assumption that the square root of two is rational is false, and is therefore irrational (by definition).

We have been able to prove two statements about numbers with a direct proof and a proof by contradiction, however these two are not always efficient for proving a proposition is true, enter proof by mathematical induction. Problems provable with mathematical induction are very noticeable many times, as we shall see in the next section.

PROOF BY MATHEMATICAL INDUCTION

Mathematical induction can be used to prove formulas like

[; \sum_{i=1}^{n}i = \frac{n(n+1)}{2} ;] or [; \sum_{i=1}^{n}ar^i = \frac{a(1-r^{n+1})}{1-r} ;]

(if r does not equal 1). Even places where one might not guess it can be used it shows up, such as in the part of the proof of the Fundamental Theorem of Arithmetic (we will touch upon this later).

The first equation can be proved in multiple ways, but mathematical induction is the technique that will be employed here. (For those interested, a topic called finite calculus is of interest.)

Definition: The principle of mathematical induction: Let P(n) be a proposition for n in the positive integers. If P(1) is true and the truth of P(k) implies the truth of P(k+1), then P(n) is true for all positive integers n.

This definition seems odd and impossible to work with, but in fact is very useful as we shall observe in the following example.

Example: Show that [; \sum_{i=1}^n i = \frac{n(n+1)}{2} ;].

Proof by mathematical induction: Let P(n) be the proposition that [; \sum_{i=1}^n i = \frac{n(n+1)}{2} ;]. First we should check that it is a proposition. Either P(n) is true or it is false - the left- and right-hand sides cannot be "kind of" equal; either the left- and right-hand sides are equal or are not. There is no gray area. So it is a proposition.

We must check that P(1) is true. P(1) says [; \sum_{i=1}^1 i = \frac{1(1+1)}{2} ;], but we should check that this is the case.

The left-hand side (LHS, for short) is [; \sum_{i=1}^1 i = 1 ;]. The right-hand side (RHS, for short) is [; \frac{1(1+1)}{2} = 1 ;]. So indeed, the LHS = RHS and we conclude that P(1) is true.

Now we may continue onto the next step of a proof by induction: stating the inductive hypothesis. We will assume that P(k) is true (where k is a positive integer). P(k) says [; \sum_{i=1}^k i = \frac{k(k+1)}{2} ;]; this is called the inductive hypothesis. Now we will check whether P(k+1) is true or not (hint: the statement P(k) is necessary when showing P(k+1) is true! Otherwise, why would we bring it up in the first place?).

P(k+1) states that [; \sum_{i=1}^{k+1} i = \frac{(k+1)(k+2)}{2} ;], however we must check that this is true.

[; \sum_{i=1}^{k+1} i = \sum_{i=1}^k i + (k+1) ;].

From the inductive hypothesis, [; \sum_{i=1}^k i = \frac{k(k+1)}{2} ;], so we can rewrite the previous formula as:

[; \sum_{i=1}^{k+1} i = \frac{k(k+1)}{2} + (k+1) ;]. Combining both terms gives [; \sum_{i=1}^{k+1} i = \frac{(k+1)(k+2)}{2} ;], just as we predicted!

What happened was we assumed P(k) to be true and ended up with P(k+1) being true! We found that P(1) was true and the truth of P(k) implied the truth of P(k+1), therefore by the principle of mathematical induction, P(n) is true for all n in the positive integers. Q.E.D.

To further illustrate the idea behind mathematical induction, we will tackle another example. We will show that the sum of the consecutive (positive) integers is a perfect square.

Proof: Show [; \sum_{i=1}^n (2i - 1) = n^2 ;].

Let P(n) be the proposition [; \sum_{i=1}^n (2i - 1) = n^2 ;] for n in the positive integers. To begin we must check that P(1) is true.

P(1) states that [; \sum_{i=1}^1 (2i - 1) = 1^2 ;]. The LHS is [; \sum_{i=1}^1 (2i - 1) = 2\times 1 - 1 = 1 ;]. The RHS is [; 1^2 = 1 ;]. Indeed, the LHS = RHS and conclude that P(1) is true.

Now we make the inductive hypothesis. We will assume that P(k) is true and check the truth of P(k+1).

P(k) states [; \sum_{i=1}^k (2i - 1) = k^2 ;]. Now, P(k+1) states that [; \sum_{i=1}^{k+1} (2i - 1) = (k+1)^2 ;], but of course this needs to be shown.

Like before we will work with the sum on the LHS of P(k+1): [; \sum_{i=1}^{k+1} (2i - 1) = \sum_{i=1}^k (2i-1) + (2(k+1) - 1) ;]. We will make use of the inductive hypothesis and rewrite the RHS: [; \sum_{i=1}^{k+1} (2i - 1) = k^2 + 2k + 2 - 1 ;]. We can easily see that this is just (k+1)^2 in disguise. Since P(k+1) is also true, we conclude (by mathematical induction) that P(n) is true for all n in the positive integers. Q.E.D.

To get a feel of the underpinnings of the proof, one can write out the first several P(n)s:

[; 1 = 1 = 1^2 ;]

[; 1 + 3 = 4 = 2^2 ;]

[; 1 + 3 + 5 = 9 = 3^2 ;]

[; 1 + 3 + 5 + 7 = 16 = 4^2 ;] and so on.

The astute observer will note that we could have easily proven this based upon the result of the previous proof, but I felt as though this proof would have helped familiarize one with the structure and execution of a proof by induction.

Being able to do a proof by induction does not necessarily mean one understands the logic underlying the proof. The reason we state that our P(n) is true for all n (given certain conditions) based on P(1) being true and the truth of P(k) implying the truth of P(k+1) can be seen as follows:

If P(1) is true and the truth of P(k) implies the truth of P(k+1), then P(1) has to imply P(2) (just let k = 1!). And if P(2) is true (which we just showed it was!), then P(3) must be true since P(k) implies P(k+1), and if P(3) is true, then P(4) must be true, ad infinitum. So the two statements that P(1) is true and P(k) -> P(k+1) are enough to show that P(n) is true for all positive integers n.

Rick makes an excellent point in the comments below. The principle of mathematical induction can be extended to start at any integer and is called the Second Principle of Mathematical Induction (we have so far used the first). There is a stronger version of mathematical induction called the Complete Principle of Mathematical Induction, but we will encounter this later when proving part of the Fundamental Theorem of Arithmetic.

There is one final thing to note about proof: often it is easiest to disprove a proposition than it is to prove it. In mathematics we take the convention that if a proposition is false for any reason at all (even if it is only false in one case!) then it is completely false. There is no such thing as "kind of" false. This statement receives no partial credit (the horrors!). If you are able to find one case where the proposition breaks down and is false (or leads to a contradiction), then you have successfully disproven the proposition.

The next post will be a change of pace from tools of mathematics into our first real topic: set theory. Set theory is all over mathematics and there are many surprising and counter-intuitive results that arise from it. Sets will be separated into multiple posts as there is much to cover. The first post will cover introductory set theory (what sets are, how we combine them, and so on), the following post(s) will likely cover infinite sets and will reference some of Gregory Cantor's work.

* The integers are the numbers ... -3, -2, -1, 0 , 1, 2, 3, ... continuing on indefinitely in both directions.

** Iff is shorthand for "if and only if" (for those in-the-know, this is a biconditional statement).