EECS 70 Discrete Mathematics and Probability Theory Fall 2020
1 Proofs
Note 2
In science, evidence is accumulated through experiments to assert the validity of a statement. Mathematics, in contrast, aims for a more absolute level of certainty. A mathematical proof provides a means for guar- anteeing that a statement is true. Proofs are very powerful and are in some ways like computer programs. Indeed, there is a deep historic link between these two concepts that we will touch upon in this course — the invention of computers is intimately tied to the exploration of the idea of a mathematical proof about a century ago.
So what types of “computer science-related” statements might we want to prove? Here are two examples: (1) Does program P halt on every input? (2) Does program P correctly compute the function f (x), i.e. does it output f (x) on input x, for every x? Note that each of these statements refers to the behavior of a program on infinitely many inputs. For such a statement, we can try to provide evidence that it is true by testing that it holds for many values of x. Unfortunately, this does not guarantee that the statement holds for the infinitely many values of x that we did not test! To be certain that the statement is true, we must provide a rigorous proof.
So what is a proof? A proof is a finite sequence of steps, called logical deductions, which establishes the truth of a desired statement. In particular, the power of a proof lies in the fact that using finite means, we can guarantee the truth of a statement with infinitely many cases.
More specifically, a proof is typically structured as follows. Recall that there are certain statements, called axioms or postulates, that we accept without proof (we have to start somewhere). Starting from these axioms, a proof consists of a sequence of logical deductions: Simple steps that apply the rules of logic. This results in a sequence of statements where each successive statement is necessarily true if the previous statements were true. This property is enforced by the rules of logic: Each statement follows from the previous statements. These rules of logic are a formal distillation of laws that were thought to underlie human thinking. They play a central role in the design of computers, starting with digital logic design or the fundamental principles behind the design of digital circuits. At a more advanced level, these rules of logic play an indispensable role in artificial intelligence, one of whose ultimate goals is to emulate human thought on a computer.
Organization of this note. We begin in Section 2 by setting notation and stating basic mathematical facts used throughout this note. We next introduce four different proof techniques: Direct proof (Section 3), proof by contraposition (Section 4), proof by contradiction (Section 5), and proof by cases (Section 6). We then briefly discuss common pitfalls in and stylistic advice for proofs (Sections 7 and 8, respectively). We close with exercises in Section 9.
2 Notation and basic facts
In this note, we use the following notation and basic mathematical facts. Let Z denote the set of integers, i.e. Z = {…,−2,−1,0,1,2,…}, and N the set of natural numbers N = {0,1,2,…}. Recall that the sum or product of two integers is an integer, i.e. the set of integers is closed under addition and multiplication. The
EECS 70, Fall 2020, Note 2 1
set of natural numbers is also closed under addition and multiplication.
Given integers a and b, we say that a divides b (denoted a|b) iff there exists an integer q such that b = aq. For example, 2|10 because there exists an integer q = 5 such that 10 = 5 · 2. We say a natural number p is prime if it is divisible only by 1 and itself.
Finally, we use the notation := to indicate a definition. For example, q := 6 defines variable q as having value 6.
3 Direct Proof
With the language of propositional logic from Note 0 under our belts, we can now discuss proof techniques, and the real fun can begin. Are you ready? If so, here is our first technique, known as a direct proof. Throughout this section, keep in mind that our goal is give clear and concise proofs. Let’s begin with a very simple example.
Theorem 2.1. For any a, b, c ∈ Z, if a|b and a|c, then a|(b + c).
Sanity check! Let P(x, y) denote “x|y”. Convince yourself that the statement above is equivalent to (∀a, b, c ∈
Z) (P(a,b)∧P(a,c)) =⇒ P(a,b+c)).
At a high level, a direct proof proceeds as follows. For each x, the proposition we are trying to prove is of the form P(x) =⇒ Q(x). A direct proof of this starts by assuming P(x) for a generic value of x and eventually concludes Q(x) through a chain of implications:
Direct Proof
Goal: To prove P =⇒ Q. Approach: Assume P
. Therefore Q
Proof of Theorem 2.1. Assume that a|b and a|c, i.e. there exist integers q1 and q2 such that b = q1a and c = q2a. Then, b + c = q1a + q2a = (q1 + q2)a. Since the Z is closed under addition, we conclude that (q1 +q2) ∈ Z, and so a|(b+c), as desired.
Easy as pie, right? But wait, earlier we said Theorem 2.1 was equivalent to (∀a, b, c ∈ Z) (P(a, b) ∧ P(a, c)) =⇒ P(a, b + c)); where in the proof above did we encounter the ∀ quantifier? The key insight is that the proof did not assume any specific values for a, b, and c; indeed, our proof holds for arbitrary a, b, c ∈ Z! Thus, we have indeed proven the desired claim.
Sanity check! Give a direct proof of the following statement: For any a, b, c ∈ Z, if a|b and a|c, then a|(b − c). Let’s try something a little more challenging.
EECS 70, Fall 2020, Note 2 2
Theorem 2.2. Let 0 < n < 1000 be an integer. If the sum of the digits of n is divisible by 9, then n is divisible by 9.
Observe that this statement is equivalent to
(∀n ∈ Z+)(n < 1000) =⇒ (sum of n’s digits divisible by 9 =⇒ n divisible by 9),
where Z+ denotes the set of positive integers, {1,2,...}. Now the proof proceeds similarly — we start by assuming, for a generic value of n, that the sum of n’s digits is divisible by 9. Then we perform a sequence of implications to conclude that n itself is divisible by 9.
ProofofTheorem2.2. Letnindecimalbewrittenasn=abc,i.e.n=100a+10b+c.Assumethatthesum of the digits of n is divisible by 9, i.e.
∃k ∈ Z such that a+b+c = 9k. (1) Adding 99a + 9b to both sides of Equation (1), we have
100a+10b+c = n = 9k+99a+9b = 9(k+11a+b). We conclude that n is divisible by 9.
Is the converse of Theorem 2.2 also true? Recall that the converse of P =⇒ Q is Q =⇒ P. The converse of Theorem 2.2 says that for any integer 0 < n < 1000, if n is divisible by 9, then the sum of the digits of n is divisible by 9.
Theorem 2.3 (Converse of Theorem 2.2). Let 0 < n < 1000 be an integer. If n is divisible by 9, then the sum of the digits of n is divisible by 9.
Proof. Assume that n is divisible by 9. We use the same notation for the digits of n as we used in Theo- rem 2.2’s proof. We proceed as follows.
nisdivisibleby9 =⇒
=⇒ 100a+10b+c=9l
=⇒ 99a+9b+(a+b+c) = 9l
=⇒ a+b+c=9l−99a−9b
=⇒ a+b+c=9(l−11a−b)
=⇒ a+b+c=9k fork=l−11a−b∈Z.
We conclude that a + b + c is divisible by 9.
We now come to the moral of this story. We have shown both Theorem 2.2 and its converse, Theorem 2.3. This means that the sum of the digits of n is divisible by 9 if and only if n is divisible by 9; in other words, these two statements are logically equivalent. So the key lesson is this: Whenever you wish to prove an equivalence P ⇐⇒ Q, always proceed by showing P =⇒ Q and Q =⇒ P separately (as we have done here).
n=9l forl∈Z
EECS 70, Fall 2020, Note 2 3
4 Proof by Contraposition
We now move to our second proof technique. Recall from our discussion on propositional logic that any implication P =⇒ Q is equivalent to its contrapositive ¬Q =⇒ ¬P. Yet, sometimes ¬Q =⇒ ¬P can be much simpler to prove than P =⇒ Q. Thus, a proof by contraposition proceeds by proving ¬Q =⇒ ¬P instead of P=⇒Q.
Proof by Contraposition
Goal: To prove P =⇒ Q. Approach: Assume ¬Q.
.
Therefore ¬P
Conclusion: ¬Q =⇒ ¬P, which is equivalent to P =⇒ Q.
Consider now the following theorem:
Theorem 2.4. Let n be a positive integer and let d divide n. If n is odd then d is odd.
Proving this via the technique of direct proof seems difficult; we would assume n is odd in Step 1, but then
what? An approach via contraposition, on the other hand, turns out to be much easier.
Sanity check! What is the contrapositive of Theorem 2.4? (Answer: If d is even, then n is even.)
Proof of Theorem 2.4. We proceed by contraposition. Assume that d is even. Then, by definition, d = 2k for some k ∈ Z. Because d|n, n = dl, for some l ∈ Z. Combining these two statements, we have n = dl = (2k)l = 2(kl). We conclude that n is even.
Note that this time, the first line of our proof stated our proof technique — this is good practice for any proof, similar to how commenting code is good practice when programming. Stating your proof technique like this is an enormous aid to your reader in understanding where your proof will go next. (Let us not forget that a reader who understands your proof, such a teaching assistant or instructor, is much more likely to give you a good grade for it!)
As another illustration of proof by contraposition, we will prove a famous theorem called the Pigeonhole Principle. Although the statement of the theorem may seem simple, it has surprising consequences.
Theorem 2.5 (Pigeonhole Principle). Let n and k be positive integers. Place n objects into k boxes. If n > k, then at least one box must contain multiple objects.
The name of the theorem comes from imagining that the n objects are pigeons and we are trying to place them in pigeonholes.
Proof of Theorem 2.5. We proceed by contraposition. If all boxes contain at most one object, then the number of objects is at most the number of boxes, i.e., n ≤ k.
EECS 70, Fall 2020, Note 2 4
The utility of the theorem stems from the fact that it holds regardless of the configuration of the objects in the box. In situations where the objects are placed in the boxes in a complicated way, the conclusions of the theorem can be non-trivial.
Here is an example. A quick search on the Internet reveals that the number of hairs on the human head is roughly, on average, 100000. So, we may be reasonably confident that no human has more than 500000 hairs on his or her head. On the other hand, the population of San Francisco (as of 2016) exceeds 800000. If we think of the residents of San Francisco as “pigeons” and the number of hairs on a resident’s head as the “box” into which he or she falls, then the Pigeonhole Principle allows us to conclude the intriguing fact that there are two people in San Francisco with exactly the same number of hairs on their heads!
5 Proof by Contradiction
Of all the proof techniques we discuss in this note, it’s perhaps hardest to resist the appeal of this one; after all, who wouldn’t want to use a technique known as reductio ad absurdum, i.e. reduction to an absurdity? The idea in a proof by contradiction is to assume that the claim you wish to prove is false (yes, this seems backwards, but bear with us). Then, you show that this leads to a conclusion which is utter nonsense: A contradiction. Hence, you conclude that your claim must in fact have been true.
Sanity check! A proof by contradiction relies crucially on the fact that if a proposition is not false, then it must be true. Which law from a previous lecture embodied this black or white interpretation of a statement?
Proof by Contradiction
Goal: To prove P. Approach: Assume ¬P.
.
R
.
¬R
Conclusion: ¬P =⇒ ¬R ∧ R, which is a contradiction. Thus, P.
If you are not convinced by the intuitive explanation thus far as to why proof by contradiction works, here is the formal reasoning: A proof by contradiction shows that ¬P =⇒ ¬R ∧ R ≡ False. The contrapositive of this statement is hence True =⇒ P.
Let us now take this proof technique on a trial run. Note that in doing so, we are continuing a long- standing legacy — the proof of the theorem below dates back more than 2000 years to the ancient Greek mathematician, Euclid of Alexandria!1
Theorem 2.6. There are infinitely many prime numbers.
To appreciate the power of contradiction, let us pause for a moment to ponder how we might try to prove
1It is perhaps worth pausing here to appreciate the true scale of this statement — after all, how many aspects of our human heritage remain relevant after multiple millenia? Music? Fashion? All of these are quickly outdated with time. But mathematics is, in a sense, timeless.
EECS 70, Fall 2020, Note 2 5
Theorem 2.6 via a different proof technique, such as, say, a direct proof. It seems very difficult, right? How would you construct infinitely many prime numbers? The remarkable thing about contradiction, however, is that if we assume the statement is false, i.e. there are only finitely many primes, bad things will happen.
To proceed, we now state a simple lemma which is handy in showing Theorem 2.6. Its proof will be deferred to a future lecture in which we learn about induction.
Lemma 2.1. Every natural number greater than one is either prime or has a prime divisor.
Proof of Theorem 2.6. We proceed by contradiction. Suppose that Theorem 2.6 is false, i.e. that there are
only finitely many primes, say k of them. Then, we can enumerate them: p1, p2, p3,…, pk.
Now,definenumberq:=p1p2p3…pk+1,whichistheproductofallprimesplusone. Weclaimthatq cannot be prime. Why? Because by definition, it is larger than all the primes p1 through pk! By Lemma 2.1, we therefore conclude that q has a prime divisor, p. This will be our statement R.
Next, because p1,p2,p3,…,pk are all the primes, p must be equal to one of them; thus, p divides r := p1p2p3…pk. Hence, p|qand p|r,implying p|(q−r). Butq−r=1,implying p≤1,andhence pisnot prime; this is the statement ¬R. We thus have R ∧ ¬R, which is a contradiction, as desired.
Now that we’re warmed up, let’s tackle another classic proof involving contradictions. Recall that a rational number is a number that can be expressed as the ratio of two integers. For example, 2 , 3 , and 9 are rational
35 16
numbers. Numbers which cannot be expressed as fractions, on the other hand, are called irrational. Now,
√
how about 2? Do you think it’s rational or irrational? The answer is as follows.
√
Theorem 2.7. 2 is irrational.
Before giving the proof, let us ask a crucial question: Why should contradiction be a good candidate proof
technique to try here? Well, consider this: Theorem 2.6 and Theorem 2.7 share something fundamental in
common — in both cases, we wish to show that something doesn’t exist. For example, for Theorem 2.6, we
wished to show that a largest prime doesn’t exist, and for Theorem 2.7, we wish to show that integers a and √
b satisfying 2 = a/b don’t exist. In general, proving that something doesn’t exist seems difficult. But this is actually one setting in which proof by contradiction shines.
To prove Theorem 2.7, we use the following simple lemma. In Section 9, we ask you to prove Lemma 2.2. Lemma 2.2. If a2 is even, then a is even.
√
Proof of Theorem 2.7. We proceed by contradiction. Assume that 2 is rational. By the definition of ratio- √
nal numbers, there are integers a and b with no common factor other than 1, such that 2 = a/b. Let our assertion R state that a and b share no common factors.
Now, for any numbers x and y, we know that x = y =⇒ x2 = y2. Hence 2 = a2/b2. Multiplying both sides by b2, we have a2 = 2b2. Since b is an integer, it follows that b2 is an integer, and thus a2 is even (by the definition of evenness). Plugging in Lemma 2.2, we hence have that a is even. In other words, there exists integer c such that a = 2c.
Combining all our facts thus far, we have that 2b2 = 4c2, or b2 = 2c2. Since c is an integer, c2 is an integer, and hence b2 is even. Thus, again applying Lemma 2.2, we conclude that b is even.
But we have just shown that both a and b are even. In particular, this means they share the common factor 2. This implies ¬R. We conclude that R ∧ ¬R holds; thus, we have a contradiction, as desired.
EECS 70, Fall 2020, Note 2 6
6 Proof by Cases
Here is a proof to tickle your fancy; it relies on another proof technique known as proof by cases, which we will touch on informally in this section. Specifically, the idea behind a proof by cases is as follows: Sometimes when we wish to prove a claim, we don’t know which of a set of possible cases is true, but we know that at least one of the cases is true. What we can do then is to prove the result in both cases; then, clearly the general statement must hold.
Theorem 2.8. There exist irrational numbers x and y such that xy is rational.
Proof. We proceed by cases. Note that the statement of the theorem is quantified by an existential quantifier:
Thus, to prove our claim, it suffices to demonstrate a single x and y such that xy is rational. To do so, let √√
x = 2 and y = 2. Let us divide our proof into two cases, exactly one of which must be true: √ √2
(a) 2 is rational, or
√ √2
(b) 2 is irrational.
√ √2 (Case (a)) Assume first that 2
is rational. But this immediately yields our claim, since x and y are irrational numbers such that xy is rational.
√ √2
(Case (b)) Assume now that 2 is irrational. Our first guess for x and y was not quite right, but now we
√ √2 √ √2 √
have a new irrational number to play with, 2 . So, let’s try setting x = 2 and y = 2. Then,
√√ √2 √√√ √ y2 22 2
x=2 =2=2=2,
where the second equality follows from the axiom (xy)z = xyz. But now we again started with two irrational
numbers x and y and obtained rational xy.
Since one of case (a) or case (b) must hold, we thus conclude that the statement of Theorem 2.8 is true.
Before closing, let us point out a peculiarity of the proof above. What were the actual numbers x and y √ √ √√2 √
satisfyingtheclaimofTheorem2.8?Weretheyx= 2andy= 2?Orx= 2 andy= 2?Well,since we did a case analysis, it’s not clear which of the two choices is actually the correct one. In other words, we have just demonstrated something rather remarkable known as a non-constructive proof: We’ve proven that some object X exists, but without explicitly revealing what X itself is!
7 Common Errors When Writing Proofs
The ability to write clean and concise proofs is a remarkable thing, and is arguably among the highest forms of intellectual enlightenment one can achieve. It requires your mind to critically reflect on its own inner workings (i.e. your thought processes), and reorganize them into a coherent and logical sequence of thoughts. In other words, your mind is improving itself at a very fundamental level, far transcending the boundaries of computer science or any particular area of study. The benefits of this training will touch every aspect of your life as you know it; indeed, it will shape the way you approach life itself.
As with any such fundamental achievement, developing the ability to write rigorous proofs is likely among the most difficult learning challenges you will face in university, so do not despair if it gives you trouble;
EECS 70, Fall 2020, Note 2 7
you are not alone. There is simply no substitute here for lots and lots of practice. To help get you started on your way, we now raise some red flags regarding common pitfalls in composing proofs. Let us begin with a simple, but common error.
Claim: −2 = 2.
Proof? Assume −2 = 2. Squaring both sides, we have (−2)2 = 22, or 4 = 4, which is true. We conclude
that −2 = 2, as desired. ♠
The theorem is obviously false, so what did we do wrong? Our arithmetic is correct, and each step rigorously follows from the previous step. So, the error must lie in the very beginning of the proof, where we made a brazen assumption: That −2 = 2. But wait, wasn’t this the very statement we were trying to prove? Exactly. In other words, to prove the statement P ≡“−2 = 2”, we just proved that P =⇒ True, which is not the same as proving P. Lesson #1: When writing proofs, do not assume the claim you aim to prove!
Lesson #2 is about the number zero: In particular, never forget to consider the case where your variables take on the value 0. Otherwise, this can happen:
Claim: 1 = 2.
Proof? Assume that x = y for integers x, y ∈ Z. Then,
x2−xy = x2−y2 x(x−y) = (x+y)(x−y)
x = x+y x = 2x.
Setting x = y = 1 yields the claim. ♠
(sincex=y)
(divide both sides by x−y)
But, clearly 1 ̸= 2, unless your grade school teachers were lying to you. Where did we go wrong? In deriving the third equality, we divided by (x − y). What is the value of (x − y) in our setting? Zero. Dividing by zero is not well-defined; thus the third equality does not hold.
Lesson #3 says to be careful when mixing negative numbers and inequalities. For example: Claim: 4 ≤ 1.
Proof? We know that −2 ≤ 1; squaring both sides of this inequality yields 4 ≤ 1. ♠
Sanity check! To see why this proof fails, ask yourself this: If a ≤ b, is it necessarily true that |a| ≤ |b|? Can you give a counterexample?
In addition, do not forget that multiplying an inequality by a negative number flips the direction of the inequality! For example, multiplying both sides of −2 < 5 by −1 yields 2 > −5, as you would expect.
8 Style and substance in proofs
We conclude with some general words of advice. First, get in the habit of thinking carefully before you write down the next sentence of your proof. If you cannot explain clearly why the step is justified, you are making a leap and you need to go back and think some more. In theory, each step in a proof must be justified by appealing to a definition or general axiom. In practice the depth to which one must do this is a matter of taste. For example, we could break down the step, “Since a is an integer, (2a2 + 2a) is an integer,” into
EECS 70, Fall 2020, Note 2 8
several more steps. [Exercise: what are they?] A justification can be stated without proof only if you are absolutely confident that (1) it is correct and (2) the reader will automatically agree that it is correct.
Notice that in the proof that √2 is irrational, we used the result, “For any integer n, if n2 is even then n is even,” twice. This suggests that it may be a useful fact in many proofs. A subsidiary result that is useful in a more complex proof is called a lemma. It is often a good idea to break down a long proof into several lemmas. This is similar to the way in which large programming tasks should be divided up into smaller subroutines. Furthermore, make each lemma (like each subroutine) as general as possible so it can be reused elsewhere.
The dividing line between lemmas and theorems is not clear-cut. Usually, when writing a paper, the theorems are those propositions that you want to “export” from the paper to the rest of the world, whereas the lemmas are propositions used locally in the proofs of your theorems. There are, however, some lemmas (for example, the Pumping Lemma and the Lifting Lemma) that are perhaps more famous and important than the theorems they were used to prove.
Finally, you should remember that the point of this lecture was not the specific statements we proved, but the different proof strategies, and their logical structure. Make sure you understand them clearly; you will be using them when you write your own proofs in homework and exams.
9 Exercises
1. Generalize the proof of Theorem 2.2 so that it works for any positive integer n. (HINT: Suppose n has k digits, and write ai for the digits of n, so that n = ∑k−1(ai · 10i).)
i=0
2. Prove Lemma 2.2. (Hint: First try a direct proof. Then, try contraposition. Which proof approach is
better suited to proving this lemma?)
EECS 70, Fall 2020, Note 2 9