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).

Propositional Logic

All mathematical arguments boil down to "if p, then q" statements, such as if x is even, then x is divisible by two. It is therefore imperative that one understands propositional logic (the branch of mathematics that studies statements like "if p, then q") in order to fully comprehend mathematical arguments and proofs. Before we begin to study the elementary operations, such as ∧ (logical conjunction - also known as "and"), ∨ (logical disjunction - also known as "or"), and ¬ (negation), we must first describe propositions.


PROPOSITIONS


Definition: A proposition is a declarative statement that is either true or false, but not both.


An example of a proposition is: "Propositional logic is fundamental to mathematics." An example of a statement that is not a proposition is: "It may rain in New York City tomorrow." Why? The answer lies in the fact that it is not declarative; it is merely stated that it might rain in New York City tomorrow, but does not state definitively one way or the other.


Why must we include "but not both" in the definition of a proposition? The inclusion of this sentence fragment would lead one to think that there are statements that can be both true and false. An incredibly popular example of a statement that is both true and false is the statement "This statement is false."


Let's try to assign a truth value to this statement. If it is to be a proposition, then it is either true or false. Let's start by assigning a truth value of true to the statement. If the statement is true, then it must be false (because it said so!). So on one hand, the statement is true and yet it is false. Strange, but let's check if it is false. If it is false, it agrees with what we said, but if it agrees with it then it must be true!


It seems like there is no way to win with this statement! What we have invented is a self-contradicting statement. If it is true, then it must be false and if it is false, it must be true. We cannot assign a truth value to the statement; it can neither be true nor false. In order to perform meaningful logical arguments, we must avoid statements like these at all costs, else we will get nowhere. Hence the inclusion of "but not both" in the definition of a proposition.


Paradoxes are very interesting in and of themselves, but for now I will continue with propositions and logic. Another example of a proposition is: "The sum of the first n nonnegative integers is n(n+2)/2" (this statement is actually false). Again, this is a definitive statement and can only be true or false - either the formula holds or it does not. It is conceivable that the statement does hold true for some value of n, but if this statement is not true for all values of n, then it is false. So, in mathematics, we take the stance that a statement is only true if it is always true.


Now that we have an understanding of propositions, we can begin to formulate logical combinations of propositions using the elementary logical operations mentioned earlier.


LOGICAL OPERATIONS


We can combine propositions in different ways, such as: "It is Sunday and it is sunny outside", or "It is Saturday or Sunday", or "It is Saturday or Sunday but not Monday." Each of these three statements can be written using logical operations. Take, for example, "It is Sunday and it is sunny outside." We will represent the proposition "it is Sunday" by the symbol p and we will represent the proposition "it is sunny outside" by q. We would then write the compound proposition as p ∧ q.

NEGATION

The negation of a proposition means to take the truth value and reverse it. To be more clear, if your proposition is true, then the negation of the proposition is false; if the proposition is false, then the negation is true.

Take for example the proposition 1 = 2. 1 = 2 is false. The negation reads 1 ≠ 2 (the equality symbol with a slash through it represents not equal to). We know for a fact that 1 ≠ 2, so it is true. And this agrees with our statement that the negation swaps the truth value of the statement.

LOGICAL CONJUNCTION


The statement p ∧ q (read p and q) is defined to be true if and only if both p and q are true, otherwise it is false. This can be summarized in what is called a truth table, as seen below:

The first line reads, if p is true (T) and q is true (T), then p and q is true (T). Similarly, the second line reads if p is true and q is false, then the compound proposition p and q is false.


An example will help to illustrate the idea: Let p be the proposition that 1 = 1 and q be the proposition that 1 = 2. p and q says 1 = 1 and 1 = 2. Obviously this compound proposition is false. While 1 does indeed equal 1, 1 does not equal 2; by definition, the conjunction of two proposition is only true if both statements are true.


Another example is: Today is Friday and today is Sunday. Obviously, it cannot both be Friday and Sunday so we conclude that the proposition is false.


Another fundamental logical operation is disjunction, as we shall see in the next section.


LOGICAL DISJUNCTION


The proposition p ∨ q (read p or q) is defined to be true if at least one of the proposition is true. Alternatively, the proposition is only false if both are false. The truth table representing the logical disjunction is shown below:

As you can see, if either p or q is true, the truth value of p or q is true. The utility of truth tables becomes very apparent as they graphically represent the truth values of compound propositions. For simple compound propositions like p and q or p or q the utility isn't so apparent, however for complicated expressions, they are very useful (as we shall see later).

An example will help illustrate the idea behind the logical disjunction of two statements. Take our proposition to be 1 = 1 or 1 = 2. 1 = 1 is true, whereas 1 = 2 is not, yet because at least one is true, we say that the compound proposition is true.

With these three tools under our belt, we can finally discuss the most important logical operation: implication.

IMPLICATION

The statement p→q is a little odd at first and trips many students up the first time they encounter it and for good reason. While I defined the previous three logical operations before giving examples, I will present this with an example and then give the general statement. Take as our example the proposition: "If it is Sunday, I will go to the park." 

This is obviously a proposition, so it must (based upon the truth values of the propositional variables - the p and q) either be true or false. We will determine when the proposition is false and otherwise it must be true.

The only time this statement is false is if it is Sunday but I am not going to go to the park. The question to ask is: When can you call me a liar? (Meaning, when does the output not match the input?) You can only call me a liar if I do not go to the park on Sunday. In this case, the overall statement is false, but any other combination cannot be said to be false. Therefore all other cases must be true.

The truth table for implication then looks as follows:

TAUTOLOGIES

With this in mind, we will explore an important logical construct called a tautology.

Definition: A proposition is said to be a tautology if it is always true regardless of the truth values of its propositional variables. An important example is the statement p ∨ ¬p is a tautology. Unlike before, we only have two possible scenarios to check since ¬p is a function of p.

p has only two possible truth values, true or false. We will check both cases. If p is true, then ¬p is false. The disjunction of T and F is T. If p is false, then ¬p is true and the disjunction of these two again yields a truth value of T. So we conclude that regardless of the truth value of p, this statement is always true and is therefore a tautology.

There are many other tautologies to observe, but I do not wish to spend too much time on them, as there are many other topics left to cover.

LOGICAL EQUIVALENCE AND DE MORGAN'S LAWS

Two compound propositions are said to be logically equivalent if they have the same truth values for the same truth values of their propositional variables. Logical equivalence is denoted by p ≡ q.

An example are the compound propositions ¬(p ∨ q) and ¬p ∧ ¬q, as can be seen in the following truth tables:

This is actually an example of what is known as one of De Morgan's Laws. The other is of very similar form:  ¬(p ∧ q) and ¬p ∨ ¬q.  These are widely used in introductory electronics classes when breadboarding and are very helpful for reducing what could be considered messy Boolean algebra statements into very clean and concise ones.

For those interested, Boolean algebra is very interesting and can be used to implement basic circuitry. You can use logic to make cool programs!

This is the conclusion of propositional logic. The next blog post will be an introduction to set theory and proof. There are three main kinds of proof: direct, inductive and contradiction. Each has their own merits and drawbacks. Often times only one can be used to prove a statement and determining which to use can be tricky, but I will attempt to make recognizing which proof to start with easier. Many similarities between sets and propositional logic will arise, namely a similar formulation for De Morgan's Laws will be realized. This is part of a much deeper theorem concerning propositional logic and set theory and will be discussed later.