MATHEMATICS FOR COMPUTER SCIENCE
, F. , & . Meyer
Google and Massachusetts Institute of Technology
Mathematics for Computer Science (Lehman, Leighton, and Meyer)
This text is disseminated via the Open Education Resource (OER) LibreTexts Project (https://LibreTexts.org) and like the hundreds of other texts available within this powerful platform, it freely available for reading, printing and “consuming.” Most, but not all, pages in the library have licenses that may allow individuals to make changes, save, and print this book. Carefully consult the applicable license(s) before pursuing such effects.
Instructors can adopt existing LibreTexts texts or Remix them to quickly build course-specific resources to meet the needs of their students. Unlike traditional textbooks, LibreTexts’ web based origins allow powerful integration of advanced features and new technologies to support learning.
The LibreTexts mission is to unite students, faculty and scholars in a cooperative effort to develop an easy-to-use online platform for the construction, customization, and dissemination of OER content to reduce the burdens of unreasonable textbook costs to our students and society. The LibreTexts project is a multi-institutional collaborative venture to develop the next generation of open-access texts to improve postsecondary education at all levels of higher learning by developing an Open Access Resource environment. The project currently consists of 13 independently operating and interconnected libraries that are constantly being optimized by students, faculty, and outside experts to supplant conventional paper-based books. These free textbook alternatives are organized within a central environment that is both vertically (from advance to basic level) and horizontally (across different fields) integrated.
The LibreTexts libraries are Powered by MindTouch® and are supported by the Department of Education Open Textbook Pilot Project, the UC Davis Office of the Provost, the UC Davis Library, the California State University Affordable Learning Solutions Program, and Merlot. This material is based upon work supported by the National Science Foundation under . 1246120, 1525057, and 1413739. Unless otherwise noted, LibreTexts content is licensed by CC BY-NC-SA 3.0.
Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation nor the US Department of Education.
Have questions or comments? For information about adoptions or adaptions contact More information on our activities can be found via Facebook (https://facebook.com/Libretexts), Twitter (https://twitter.com/libretexts), or our blog (http://Blog.Libretexts.org).
This text was compiled on 06/30/2021
TABLE OF CONTENTS
This text serves as an introduction to discrete mathematics, probability, and mathematical thinking for computer scientists with an interactive introduction to discrete mathematics oriented toward computer science and engineering. The subject coverage divides roughly into thirds: (1) Fundamental concepts of mathematics including definitions, proofs, sets, functions, relations. (2) Discrete structures: graphs, state machines, modular arithmetic, counting and (3) Discrete probability theory.
1: PROOFS
1: INTRO TO PROOFS
1.1: PROPOSITIONS
1.2: PREDICATES
1.3: THE AXIOMATIC METHOD
1.4: OUR AXIOMS
1.5: PROVING AN IMPLICATION 1.6: PROVING AN “IF AND ONLY IF” 1.7: PROOF BY CASES
1.8: PROOF BY CONTRADICTION 1.9: GOOD PROOFS IN PRACTICE 2: WELL ORDERING PRINCIPLE
2.1: WELL ORDERING PROOFS
2.2: TEMPLATE FOR WELL ORDERING PROOFS 2.3: FACTORING INTO PRIMES
3: LOGICAL FORMULAS
3.1: PROPOSITIONS FROM PROPOSITIONS
3.2: PROPOSITIONAL LOGIC IN COMPUTER PROGRAMS 3.3: EQUIVALENCE AND VALIDITY
3.4: THE ALGEBRA OF PROPOSITIONS
3.5: THE SAT PROBLEM
3.6: PREDICATE FORMULAS
4: MATHEMATICAL DATA TYPES
4.1: SETS
4.2: SEQUENCES
4.3: FUNCTIONS
4.4: BINARY RELATIONS 4.5: FINITE CARDINALITY 5: INDUCTION
5.1: ORDINARY INDUCTION
5.2: STRONG INDUCTION
5.3: STRONG INDUCTION VS. INDUCTION VS. WELL ORDERING 5.4: STATE MACHINES
6: RECURSIVE DATA TYPES
6.1: RECURSIVE DEFINITIONS AND STRUCTURAL INDUCTION 6.2: STRINGS OF MATCHED BRACKETS
6.3: RECURSIVE FUNCTIONS ON NONNEGATIVE INTEGERS 6.4: ARITHMETIC EXPRESSIONS
6.5: INDUCTION IN COMPUTER SCIENCE 6.6: PROBLEMS FOR CHAPTER 6
7: INFINITE SETS
7.1: INFINITE CARDINALITY
7.2: THE HALTING PROBLEM
7.3: THE LOGIC OF SETS
7.4: DOES ALL THIS REALLY WORK? 7.5: PROBLEMS FOR CHAPTER 7
1 6/29/2021
2: STRUCTURES 8: NUMBER THEORY
8.1: DIVISIBILITY
8.2: THE GREATEST COMMON DIVISOR
8.3: PRIME MYSTERIES
8.4: THE FUNDAMENTAL THEOREM OF ARITHMETIC 8.5: ALAN TURING
8.6: MODULAR ARITHMETIC
8.7: REMAINDER ARITHMETIC
8.8: TURING’S CODE (VERSION 2.0)
8.9: MULTIPLICATIVE INVERSES AND CANCELLING 8.10: EULER’S THEOREM
8.11: RSA PUBLIC KEY ENCRYPTION
8.12: WHAT HAS SAT GOT TO DO WITH IT?
9: DIRECTED GRAPHS AND PARTIAL ORDERS
9.1: VERTEX DEGREES
9.2: WALKS AND PATHS
9.3: ADJACENCY MATRICES
9.4: WALK RELATIONS
9.5: DIRECTED ACYCLIC GRAPHS AND SCHEDULING
9.6: PARTIAL ORDERS
9.7: REPRESENTING PARTIAL ORDERS BY SET CONTAINMENT 9.8: LINEAR ORDERS
9.9: PRODUCT ORDERS
9.10: EQUIVALENCE RELATIONS
9.11: SUMMARY OF RELATIONAL PROPERTIES
10: COMMUNICATION NETWORKS
10.1: COMPLETE BINARY TREE 10.2: ROUTING PROBLEMS 10.3: NETWORK DIAMETER 10.4: SWITCH COUNT
10.5: NETWORK LATENCY 10.6: CONGESTION
10.7: 2-D ARRAY
10.8: BUTTERFLY
10.9: BENEŠ NETWORK 11: SIMPLE GRAPHS
11.1: VERTEX ADJACENCY AND DEGREES 11.2: SEXUAL DEMOGRAPHICS IN AMERICA 11.3: SOME COMMON GRAPHS
11.4: ISOMORPHISM
11.5: BIPARTITE GRAPHS AND MATCHINGS 11.6: THE STABLE MARRIAGE PROBLEM 11.7: COLORING
11.8: SIMPLE WALKS
11.9: CONNECTIVITY
11.10: FORESTS AND TREES 12: PLANAR GRAPHS
12.1: DRAWING GRAPHS IN THE PLANE
12.2: DEFINITIONS OF PLANAR GRAPHS
12.3: EULER’S FORMULA
12.4: BOUNDING THE NUMBER OF EDGES IN A PLANAR GRAPH 12.5: RETURNING TO K5 AND K3,3
12.6: COLORING PLANAR GRAPHS
12.7: CLASSIFYING POLYHEDRA
12.8: ANOTHER CHARACTERIZATION FOR PLANAR GRAPHS
3: COUNTING
2 6/29/2021
13: SUMS AND ASYMPTOTICS
13.1: THE VALUE OF AN ANNUITY 13.2: SUMS OF POWERS
13.3: APPROXIMATING SUMS
13.4: HANGING OUT OVER THE EDGE 13.5: PRODUCTS
13.6: DOUBLE TROUBLE
13.7: ASYMPTOTIC NOTATION 14: CARDINALITY RULES
14.1: COUNTING ONE THING BY COUNTING ANOTHER 14.2: COUNTING SEQUENCES
14.3: THE GENERALIZED PRODUCT RULE
14.4: THE DIVISION RULE
14.5: COUNTING SUBSETS
14.6: SEQUENCES WITH REPETITIONS
14.7: COUNTING PRACTICE – POKER HANDS 14.8: THE PIGEONHOLE PRINCIPLE
14.9: INCLUSION-EXCLUSION
14.10: COMBINATORIAL PROOFS
15: GENERATING FUNCTIONS
15.1: INFINITE SERIES
15.2: COUNTING WITH GENERATING FUNCTIONS 15.3: PARTIAL FRACTIONS
15.4: SOLVING LINEAR RECURRENCES
15.5: FORMAL POWER SERIES
4: PROBABILITY
16: EVENTS AND PROBABILITY SPACES
16.1: LET’S MAKE A DEAL
16.2: THE FOUR STEP METHOD
16.3: STRANGE DICE
16.4: THE BIRTHDAY PRINCIPLE
16.5: SET THEORY AND PROBABILITY 17: CONDITIONAL PROBABILITY
17.1: MONTY HALL CONFUSION
17.2: DEFINITION AND NOTATION
17.3: THE FOUR-STEP METHOD FOR CONDITIONAL PROBABILITY 17.4: WHY TREE DIAGRAMS WORK
17.5: THE LAW OF TOTAL PROBABILITY
17.6: SIMPSON’S PARADOX
17.7: INDEPENDENCE
17.8: MUTUAL INDEPENDENCE
18: RANDOM VARIABLES
18.1: RANDOM VARIABLE EXAMPLES 18.2: INDEPENDENCE
18.3: DISTRIBUTION FUNCTIONS 18.4: GREAT EXPECTATIONS
18.5: LINEARITY OF EXPECTATION 19: DEVIATION FROM THE MEAN
19.1: MARKOV’S THEOREM
19.2: CHEBYSHEV’S THEOREM
19.3: PROPERTIES OF VARIANCE
19.4: ESTIMATION BY RANDOM SAMPLING 19.5: CONFIDENCE VERSUS PROBABILITY 19.6: SUMS OF RANDOM VARIABLES
19.7: REALLY GREAT EXPECTATIONS
20: RANDOM WALKS
3 6/29/2021
20.1: GAMBLER’S RUIN
20.2: RANDOM WALKS ON GRAPHS
5: RECURRENCES 21: RECURRENCES
21.1: THE TOWERS OF HANOI
21.2: MERGE SORT
21.3: LINEAR RECURRENCES
21.4: DIVIDE-AND-CONQUER RECURRENCES 21.5: A FEEL FOR RECURRENCES
BACK MATTER
INDEX GLOSSARY
4 6/29/2021
SECTION OVERVIEW
1: PROOFS
1: INTRO TO PROOFS
1.1: PROPOSITIONS
1.2: PREDICATES
1.3: THE AXIOMATIC METHOD
1.4: OUR AXIOMS
1.5: PROVING AN IMPLICATION 1.6: PROVING AN “IF AND ONLY IF” 1.7: PROOF BY CASES
1.8: PROOF BY CONTRADICTION 1.9: GOOD PROOFS IN PRACTICE
2: WELL ORDERING PRINCIPLE
2.1: WELL ORDERING PROOFS
2.2: TEMPLATE FOR WELL ORDERING PROOFS 2.3: FACTORING INTO PRIMES
3: LOGICAL FORMULAS
3.1: PROPOSITIONS FROM PROPOSITIONS
3.2: PROPOSITIONAL LOGIC IN COMPUTER PROGRAMS 3.3: EQUIVALENCE AND VALIDITY
3.4: THE ALGEBRA OF PROPOSITIONS
3.5: THE SAT PROBLEM
3.6: PREDICATE FORMULAS
4: MATHEMATICAL DATA TYPES
4.1: SETS
4.2: SEQUENCES
4.3: FUNCTIONS
4.4: BINARY RELATIONS 4.5: FINITE CARDINALITY
5: INDUCTION
Induction is a powerful method for showing a property is true for all nonnegative integers. Induction plays a central role in discrete mathematics and computer science. In fact, its use is a defining characteristic of discrete—as opposed to continuous—mathematics. This chapter introduces two versions of induction, Ordinary and Strong, and explains why they work and how to use them in proofs.
5.1: ORDINARY INDUCTION
5.2: STRONG INDUCTION
5.3: STRONG INDUCTION VS. INDUCTION VS. WELL ORDERING 5.4: STATE MACHINES
6: RECURSIVE DATA TYPES
6.1: RECURSIVE DEFINITIONS AND STRUCTURAL INDUCTION 6.2: STRINGS OF MATCHED BRACKETS
6.3: RECURSIVE FUNCTIONS ON NONNEGATIVE INTEGERS 6.4: ARITHMETIC EXPRESSIONS
6.5: INDUCTION IN COMPUTER SCIENCE 6.6: PROBLEMS FOR CHAPTER 6
7: INFINITE SETS
1 6/29/2021
7.1: INFINITE CARDINALITY
7.2: THE HALTING PROBLEM
7.3: THE LOGIC OF SETS
7.4: DOES ALL THIS REALLY WORK? 7.5: PROBLEMS FOR CHAPTER 7
2 6/29/2021
CHAPTER OVERVIEW
1: INTRO TO PROOFS
1.1: PROPOSITIONS
1.2: PREDICATES
1.3: THE AXIOMATIC METHOD
1.4: OUR AXIOMS
1.5: PROVING AN IMPLICATION 1.6: PROVING AN “IF AND ONLY IF” 1.7: PROOF BY CASES
1.8: PROOF BY CONTRADICTION 1.9: GOOD PROOFS IN PRACTICE
1 6/29/2021
1.1: Propositions
For example, both of the following statements are propositions. The first is true, and the second is false.
Proposition 1.1.1. 2 + 3 = 5.
Proposition 1.1.2. 1 + 1 = 3.
Being true or false doesn’t sound like much of a limitation, but it does exclude statements such as “Wherefore art thou Romeo?” and “Give me an A!” It also excludes statements whose truth varies with circumstance such as, “It’s five o’clock,” or “the stock market will rise tomorrow.”
Unfortunately it is not always easy to decide if a proposition is true or false: Proposition 1.1.3. For every nonnegative integer, , the value of is prime.
(A prime is an integer greater than 1 that is not divisible by any other integer greater than 1. For example, 2, 3, 5, 7, 11, are the first five primes.) Let’s try some numerical experimentation to check this proposition. Let
We begin with , which is prime; then
are each prime. Hmmm, starts to look like a plausible claim. In fact we can keep checking through and confirm that is prime.
Definition
A proposition is a statement (communication) that is either true or false.
But
integers. In fact, it’s not hard to show that no polynomial with integer coefficients can map all nonnegative numbers into prime numbers, unless it’s a constant (see Problem 1.17). But the real point of this example is to show that in general, you can’t check a claim about an infinite set by checking a finite set of its elements, no matter how large the finite set.
By the way, propositions like this about all numbers or all items of some kind are so common that there is a special notation for them. With this notation, Proposition 1.1.3 would be
Here the symbol is read “for all.” The symbol stands for the set of nonnegative integers: (ask your instructor for the complete list). The symbol “ ” is read as “is a member of,” or “belongs to,” or simply as “is in.” The period after the
is just a separator between phrases.
Here are two even more extreme examples:
Proposition 1.1.4. [Euler’s Conjecture] The equation has no solution when are positive integers.
Euler (pronounced “oiler”) conjectured this in 1769. But the proposition was proved false 218 years later by at a liberal arts school up Mass Ave. The solution he found was .
In logical notation, Euler’s Conjecture could be written,
Here, is a symbol for the positive integers. Strings of ‘s like this are usually abbreviated for easier reading:
, which is not prime. So it’s not true that the expression is prime for all nonnegative
, F. , & . Meyer 6/29/2021 1.1.1 CC-BY-NC-SA
)2.1.1(
.emirp si )n(p ,N ∈ n∀
)1.1.1(
93=n
∀ +Z . 4 d ≠ 4c + 4b + 4a . +Z ∈ d∀ +Z ∈ c∀ +Z ∈ b∀ +Z ∈ a∀
184224 = d ,065414 = c ,915712 = b ,00859 = a
4 d = 4c + 4b + 4a
N∈
…,3,2,1,0 N ∀
164=)02(p,…,35=)3(p,74=)2(p,34=)1(p 1.14 + n + 2n =:: )n(p
14 = )0(p
14+n+2n n
d,c,b,a
14 ⋅ 14 = 14 + 04 + 204 = )04(p 1061 = )93(p
Proposition 1.1.5. has no solution when
This proposition is also false, but the smallest counterexample has more than 1000 digits!
It’s worth mentioning a couple of further famous propositions whose proofs were sought for centuries before finally being discovered:
Proposition 1.1.6 (Four Color Theorem). Every map can be colored with 4 colors so that adjacent2 regions have different colors.
Several incorrect proofs of this theorem have been published, including one that stood for 10 years in the late 19th century before its mistake was found. A laborious proof was finally found in 1976 by mathematicians Appel and Haken, who used a complex computer program to categorize the four-colorable maps. The program left a few thousand maps uncategorized, which were checked by hand by Haken and his assistants—among them his 15-year-old daughter.
There was reason to doubt whether this was a legitimate proof: the proof was too big to be checked without a computer. No one could guarantee that the computer calculated correctly, nor was anyone enthusiastic about exerting the effort to recheck the four-colorings of thousands of maps that were done by hand. Two decades later a mostly intelligible proof of the Four Color Theorem was found, though a computer is still needed to check four-colorability of several hundred special maps.3
Proposition 1.1.7 (Fermat’s Last Theorem). There are no positive integers and such that for some integer .
In a book he was reading around 1630, Fermat claimed to have a proof for this proposition, but not enough space in the margin to write it down. Over the years, the Theorem was proved to hold for all up to 4,000,000, but we’ve seen that this shouldn’t necessarily inspire confidence that it holds for all . There is, after all, a clear resemblance between Fermat’s Last Theorem and Euler’s false Conjecture. Finally, in 1994, British mathematician gave a proof, after seven years of working in secrecy and isolation in his attic. His proof did not fit in any margin.4
Finally, let’s mention another simply stated proposition whose truth remains unknown.
Proposition 1.1.8 (Goldbach’s Conjecture). Every even integer greater than 2 is the sum of two primes.
Goldbach’s Conjecture dates back to 1742. It is known to hold for all numbers up to but to this day, no one knows
whether it’s true or false.
For a computer scientist, some of the most important things to prove are the correctness of programs and systems—whether a program or system does what it’s supposed to. Programs are notoriously buggy, and there’s a growing community of researchers and practitioners trying to find ways to prove program correctness. These efforts have been successful enough in the case of CPU chips that they are now routinely used by leading chip manufacturers to prove chip correctness and avoid mistakes like the notorious Intel division bug in the 1990’s. Developing mathematical methods to verify programs and systems remains an active research area. We’ll illustrate some of these methods in Chapter 5.
1The symbol ::= means “equal by definition.” It’s always ok simply to write “=” instead of ::=, but reminding the reader that an equality holds by definition can be helpful.
2Two regions are adjacent only when they share a boundary segment of positive length. They are not considered to be adjacent if their boundaries meet only at a few points.
3The story of the proof of the Four Color Theorem is told in a well-reviewed popular (nontechnical) book: “Four Colors Suffice. How the Map Problem was Solved.” . Princeton Univ. Press, 2003, 276pp. ISBN 0-691-11533-8.
4In fact, Wiles’ original proof was wrong, but he and several collaborators used his ideas to arrive at a correct proof a year later. This story is the subject of the popular book, Fermat’s Enigma by , Walker & Company, November, 1997.
, F. , & . Meyer 6/29/2021 1.1.2 CC-BY-NC-SA
8101
n
n z = n y + nx z ,y,x
n
.+Z∈z,y,x 3z=)3y+3x(313 .4d≠ 4c+4b+4a.+Z∈d,c,b,a∀
2>n
1.2: Predicates
A predicate can be understood as a proposition whose truth depends on the value of one or more variables. So “ is a perfect square” describes a predicate, since you can’t say if it’s true or false until you know what the value of the variable happens to be. Once you know, for example, that equals 4, the predicate becomes the true proposition “4 is a perfect square”. Remember, nothing says that the proposition has to be true: if the value of were 5, you would get the false proposition “5 is a perfect square.”
Like other propositions, predicates are often named with a letter. Furthermore, a function-like notation is used to denote a predicate supplied with specific variable values. For example, we might use the name “ ” for predicate above:
and repeat the remarks above by asserting that is true, and is false.
This notation for predicates is confusingly similar to ordinary function notation. If is a predicate, then is either true or false, depending on the value of . On the other hand, if is an ordinary function, like , then is a numerical quantity. Don’t confuse these two!
, F. , & . Meyer 6/29/2021 1.2.1 CC-BY-NC-SA
n
n
)n(p 1+2n p n )n(P P
P
)5( P )4( P ,”erauqs tcefrep a si n“ =:: )n( P
n
n
1.3: The Axiomatic Method
The standard procedure for establishing truth in mathematics was invented by Euclid, a mathematician working in Alexandria, Egypt around 300 BC. His idea was to begin with five assumptions about geometry, which seemed undeniable based on direct experience. (For example, “There is a straight line segment between every pair of points”.) Propositions like these that are simply accepted as true are called axioms.
Starting from these axioms, Euclid established the truth of many additional propositions by providing “proofs.” A proof is a sequence of logical deductions from axioms and previously proved statements that concludes with the proposition in question. You probably wrote many proofs in high school geometry class, and you’ll see a lot more in this text.
There are several common terms for a proposition that has been proved. The different terms hint at the role of the proposition within a larger body of work.
Important true propositions are called theorems.
A lemma is a preliminary proposition useful for proving later propositions.
A corollary is a proposition that follows in just a few logical steps from a theorem.
These definitions are not precise. In fact, sometimes a good lemma turns out to be far more important than the theorem it was originally used to prove.
Euclid’s axiom-and-proof approach, now called the axiomatic method, remains the foundation for mathematics today. In fact, just a handful of axioms, called the Zermelo-Fraenkel with Choice axioms(ZFC), together with a few logical deduction rules, appear to be sufficient to derive essentially all of mathematics. We’ll examine these in Chapter 7.
, F. , & . Meyer 6/29/2021 1.3.1 CC-BY-NC-SA
1.4: Our Axioms
The ZFC axioms are important in studying and justifying the foundations of mathematics, but for practical purposes, they are much too primitive. Proving theorems in ZFC is a little like writing programs in byte code instead of a full-fledged programming language—by one reckoning, a formal proof in ZFC that requires more than 20,000 steps! So instead of starting with ZFC, we’re going to take a huge set of axioms as our foundation: we’ll accept all familiar facts from high school math.
This will give us a quick launch, but you may find this imprecise specification of the axioms troubling at times. For example, in the midst of a proof, you may start to wonder, “Must I prove this little fact or can I take it as an axiom?” There really is no absolute answer, since what’s reasonable to assume and what requires proof depends on the circumstances and the audience. A good general guideline is simply to be up front about what you’re assuming.
Logical Deductions
Logical deductions, or inference rules, are used to prove new propositions using previously proved ones. A fundamental inference rule is modus ponens. This rule says that a proof of P together with a proof that
proof of .
Inference rules are sometimes written in a funny notation. For example, modus ponens is written: Rule.
is a
When the statements above the line, called the antecedents, are proved, then we can consider the statement below the line, called the conclusion or consequent, to also be proved.
A key requirement of an inference rule is that it must be sound: an assignment of truth values to the letters, , that makes all the antecedents true must also make the consequent true. So if we start off with true axioms and apply sound inference rules, everything we prove will also be true.
There are many other natural, sound inference rules, for example:
Rule.
Rule.
On the other hand,
Non-Rule.
is not sound: if is assigned T and is assigned F, then the antecedent is true and the consequent is not.
As with axioms, we will not be too formal about the set of legal inference rules. Each step in a proof should be clear and
“logical”; in particular, you should state what previously proved facts are used to derive each new conclusion.
Patterns of Proof
In principle, a proof can be any sequence of logical deductions from axioms and previously proved statements that concludes with the proposition in question. This freedom in constructing a proof can seem overwhelming at first. How do you even start a proof?
, F. , & . Meyer 6/29/2021 1.4.1 CC-BY-NC-SA
…,Q,P
Q SEILPMI P
Q SEILPMI P )Q(TON SEILPMI ) P(TON
P SEILPMI Q )Q(TON SEILPMI ) P(TON
R SEILPMI Q
,Q SEILPMI P
4= 2+2
R SEILPMI P
Q QSEILPMIP ,P
QP
Q
Here’s the good news: many proofs follow one of a handful of standard templates. Each proof has it own details, of course, but these templates at least provide you with an outline to fill in. We’ll go through several of these standard patterns, pointing out the basic idea and common pitfalls and giving some examples. Many of these templates fit together; one may give you a top- level outline while others help you at the next level of detail. And we’ll show you other, more sophisticated proof techniques later on.
The recipes below are very specific at times, telling you exactly which words to write down on your piece of paper. You’re certainly free to say things your own way instead; we’re just giving you something you could say so that you’re never at a complete loss.
, F. , & . Meyer 6/29/2021 1.4.2 CC-BY-NC-SA
1.5: Proving an Implication
Propositions of the form “If , then ” are called implications. This implication is often rephrased as “ .” Here are some examples:
(Quadratic Formula) If and , then
(Goldbach’s Conjecture 1.1.8 rephrased) If is an even integer greater than 2, then is a sum of two primes. If , then .
There are a couple of standard methods for proving an implication.
Method #1
In order to prove that : 1. Write, “Assume .”
2. Show that logically follows. Example
Before we write a proof of this theorem, we have to do some scratchwork to figure out why it is true.
The inequality certainly holds for ; then the left side is equal to 1 and . As grows, the initially seems to have greater magnitude than (which is negative). For example, when
only. In fact, it looks like doesn’t begin to dominate until . So it seems the nonnegative for all between 0 and 2, which would imply that is positive.
term (which is positive) , we have , but
part should be
Theorem
If , then .
So far, so good. But we still have to replace all those “seems like” phrases with solid, logical arguments. We can get a better handle on the critical part by factoring it, which is not too hard:
Aha! For between 0 and 2, all of the terms on the right side are nonnegative. And a product of nonnegative terms is also nonnegative. Let’s organize this blizzard of observations into a clean proof.
Proof. Assume . Then and are all nonnegative. Therefore, the product of these terms is also nonnegative. Adding 1 to this product gives a positive number, so:
Multiplying out on the left side proves that
as claimed.
There are a couple points here that apply to all proofs:
You’ll often need to do some scratchwork while you’re trying to figure out the logical steps of a proof. Your scratchwork can be as disorganized as you like—full of dead-ends, strange diagrams, obscene words, whatever. But keep your scratchwork separate from your final proof, which should be clear and concise.
Proofs typically begin with the word “Proof” and end with some sort of delimiter like or “QED.” The only purpose for these conventions is to clarify where proofs begin and end.
, F. , & . Meyer 6/29/2021 1.5.1 CC-BY-NC-SA
4 = x4
2 > x x4 x0>1
3x−
Q SEILPMI P
x4 + 3x−
1 = x
3x− 0=x
1− = 3x−
□
0 > 1 + x4 + 3x−
0 > 1 + )x + 2()x − 2(x
nn . a 2 / ) c − a − 4 − − − − 2− b − √ ± b − ( = x
x + 2
,x − 2 ,x
2 ≤ x ≤ 0
)x + 2()x − 2(x = x4 + 3x−
1+x4+3x− x
0 ≠ a
0 = c + xb + 2xa Q P
x4+3x−
0 > 1 + x4 + 3x−
2 ≤ x ≤ 0 1.5.1
Q SEILPMI P
0 > 1 + x4 + 3x−
2 ≤ x ≤ 0
Q P
■
x
Method #2 – Prove the Contrapositive
An implication (“ ”) is logically equivalent to its contrapositive
Proving one is as good as proving the other, and proving the contrapositive is sometimes easier than proving the original
statement. If so, then you can proceed as follows:
1. Write, “We prove the contrapositive:” and then state the contrapositive. 2. Proceed as in Method #1.
Example
A number is rational when it equals a quotient of integers — that is, if it equals for some integers and . If it’s not rational, then it’s called irrational. So we must show that if is not a ratio of integers, then is also not a ratio of integers. That’s pretty convoluted! We can eliminate both not’s and simplify the proof by using the contrapositive instead.
Proof. We prove the contrapositive: if is rational, then is rational. Assume that is rational. Then there exist integers and such that:
Squaring both sides gives:
Since and are integers, r is also rational.
Theorem
If is irrational, then is also irrational.
, F. , & . Meyer 6/29/2021 1.5.2 CC-BY-NC-SA
r√ r nm n/m
■ 2n 2m 2n =r√
2m
n =r√
m
nm r√
.) P(TON SEILPMI )Q(TON
r r√
r√ r 2.5.1
Q SEILPMI P
1.6: Proving an “If and Only If”
Many mathematical theorems assert that two statements are logically equivalent; that is, one holds if and only if the other does. Here is an example that has been known for several thousand years:
Two triangles have the same side lengths if and only if two side lengths and the angle between those sides are the same. The phrase “if and only if” comes up so often that it is often abbreviated “iff.”
Method #1: Prove Each Statement Implies the Other
The statement “P IFF Q” is equivalent to the two statements “P IMPLIES Q” and “Q IMPLIES P.” So you can prove an “iff” by proving two implications:
1. Write, “We prove P implies Q and vice-versa.”
2. Write, “First, we show P implies Q.” Do this by one of the methods in Section 1.5.
3. Write, “Now, we show Q implies P.” Again, do this by one of the methods in Section 1.5.
Method #2: Construct a Chain of Iffs
In order to prove that P is true iff Q is true:
1. Write, “We construct a chain of if-and-only-if implications.”
2. Prove P is equivalent to a second statement which is equivalent to a third statement and so forth until you reach Q.
This method sometimes requires more ingenuity than the first, but the result can be a short, elegant proof.
Example
The standard deviation of a sequence of values x1, x2, … , xn is defined to be:
where is the average or mean of the values:
(1.3)
Theorem 1.6.1.
The standard deviation of a sequence of values x1, x2, … , xn is zero iff all the values are equal to the mean.
For example, the standard deviation of test scores is zero if and only if everyone scored exactly the class average. Proof. We construct a chain of “iff” implications, starting with the statement that the standard deviation (1.3) is zero:
Now since zero is the only number whose square root is zero, equation (1.4) holds iff
(1.4)
(1.5)
Squares of real numbers are always nonnegative, so every term on the left hand side of equation (1.5) is nonnegative. This means that (1.5) holds iff
Every term on the left hand side of (1.5) is zero.
, F. , & . Meyer 6/29/2021 1.6.1 CC-BY-NC-SA
0 = 2)μ− nx(+ ⋯+ 2)μ− 2x(+ 2)μ− 1x(
0=n√ − − 2 − ) − μ − − − − n − x ( − − + − − −⋯ − + − 2 − ) − μ − − − − 2 − x ( − − + − 2 − ) − μ − − − 1 − x − ( −
n =::μ nx+⋯+2x+1x
n
2)μ−nx(+⋯+2)μ−2x(+2)μ−1x(√ −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
μ
But a term is zero iff , so (1.6) is true iff
Every equals the mean.
(1.6)
, F. , & . Meyer 6/29/2021 1.6.2 CC-BY-NC-SA
■
ix
μ = ix 2)μ − ix(
1.7: Proof by Cases
Breaking a complicated proof into cases and proving each case separately is a common, useful proof strategy. Here’s an amusing example.
Let’s agree that given any two people, either they have met or not. If every pair of people in a group has met, we’ll call the group a club. If every pair of people in a group has not met, we’ll call it a group of strangers.
Proof. The proof is by case analysis5. Let x denote one of the six people. There are two cases: 1. Among 5 other people besides x, at least 3 have met x.
2. Among the 5 other people, at least 3 have not met x.
Now, we have to be sure that at least one of these two cases must hold,6 but that’s easy: we’ve split the 5 people into two groups, those who have shaken hands with x and those who have not, so one of the groups must have at least half the people.
Case 1: Suppose that at least 3 people did meet x. This case splits into two subcases:
Case 1.1: No pair among those people met each other. Then these people are a group of at least 3 strangers. The theorem holds in this subcase.
Case 1.2: Some pair among those people have met each other. Then that pair, together with x, form a club of 3 people. So the theorem holds in this subcase.
This implies that the theorem holds in Case 1.
Case 2: Suppose that at least 3 people did not meet x. This case also splits into two subcases:
Case 2.1: Every pair among those people met each other. Then these people are a club of at least 3 people. So the theorem holds in this subcase.
Case 2.2: Some pair among those people have not met each other. Then that pair, together with x, form a group of at least 3 strangers. So the theorem holds in this subcase.
This implies that the theorem also holds in Case 2, and therefore holds in all cases.
5Describing your approach at the outset helps orient the reader.
6Part of a case analysis argument is showing that you’ve covered all the cases. This is often obvious, because the two cases are of the form “P” and “not P.” However, the situation above is not stated quite so simply.
Theorem
Every collection of 6 people includes a club of 3 people or a group of 3 strangers.
, F. , & . Meyer 6/29/2021 1.7.1 CC-BY-NC-SA
■
1.8: Proof by Contradiction
In a proof by contradiction, or indirect proof, you show that if a proposition were false, then some false fact would be true. Since a false fact by definition can’t be true, the proposition must be true.
Proof by contradiction is always a viable approach. However, as the name suggests, indirect proofs can be a little convoluted, so direct proofs are generally preferable when they are available.
Method: In order to prove a proposition P by contradiction:
1. Write, “We use proof by contradiction.”
2. Write, “Suppose P is false.”
3. Deduce something known to be false (a logical contradiction). 4. Write, “This is a contradiction. Therefore, P must be true.”
Example
We’ll prove by contradiction that is irrational. Remember that a number is rational if it is equal to a ratio of integers —for example, 3.5 = 7/2 and 0.1111 = 1/9 are rational numbers.
Proof. We use proof by contradiction. Suppose the claim is false, and is rational. Then we can write as a fraction in lowest terms.
Squaring both sides gives 2 = and so . This implies that n is a multiple of 2 (see Problems 1.10 and 1.11). Therefore must be a multiple of 4. But since , we know is a multiple of 4 and so is a multiple of 2. This implies that d is a multiple of 2.
So, the numerator and denominator have 2 as a common factor, which contradicts the fact that is in lowest terms. Thus, must be irrational.
Theorem 1.8.1
is irrational.
, F. , & . Meyer 6/29/2021 1.8.1 CC-BY-NC-SA
■
2–√
2–√
d/n 2d
2–√
2d2 2n = 2d2
2n = 2d2
2d/2n
2n
⋯ 2–√
d/n
2–√
1.9: Good Proofs in Practice
One purpose of a proof is to establish the truth of an assertion with absolute certainty, and mechanically checkable proofs of enormous length or complexity can accomplish this. But humanly intelligible proofs are the only ones that help someone understand the subject. Mathematicians generally agree that important mathematical results can’t be fully understood until their proofs are understood. That is why proofs are an important part of the curriculum.
To be understandable and helpful, more is required of a proof than just logical correctness: a good proof must also be clear. Correctness and clarity usually go together; a well-written proof is more likely to be a correct proof, since mistakes are harder to hide.
In practice, the notion of proof is a moving target. Proofs in a professional research journal are generally unintelligible to all but a few experts who know all the terminology and prior results used in the proof. Conversely, proofs in the first weeks of a beginning course like 6.042 would be regarded as tediously long-winded by a professional mathematician. In fact, what we accept as a good proof later in the term will be different from what we consider good proofs in the first couple of weeks of 6.042. But even so, we can offer some general tips on writing good proofs:
State your game plan. A good proof begins by explaining the general line of reasoning, for example, “We use case analysis” or “We argue by contradiction.”
Keep a linear flow. Sometimes proofs are written like mathematical mosaics, with juicy tidbits of independent reasoning sprinkled throughout. This is not good. The steps of an argument should follow one another in an intelligible order.
A proof is an essay, not a calculation. Many students initially write proofs the way they compute integrals. The result is a long sequence of expressions without explanation, making it very hard to follow. This is bad. A good proof usually looks like an essay with some equations thrown in. Use complete sentences.
Avoid excessive symbolism. Your reader is probably good at understanding words, but much less skilled at reading arcane mathematical symbols. Use words where you reasonably can.
Revise and simplify. Your readers will be grateful.
Introduce notation thoughtfully. Sometimes an argument can be greatly simplified by introducing a variable, devising a special notation, or defining a new term. But do this sparingly, since you’re requiring the reader to remember all that new stuff. And remember to actually define the meanings of new variables, terms, or notations; don’t just start using them!
Structure long proofs. Long programs are usually broken into a hierarchy of smaller procedures. Long proofs are much the same. When your proof needed facts that are easily stated, but not readily proved, those fact are best pulled out as preliminary lemmas. Also, if you are repeating essentially the same argument over and over, try to capture that argument in a general lemma, which you can cite repeatedly instead.
Be wary of the “obvious.” When familiar or truly obvious facts are needed in a proof, it’s OK to label them as such and to not prove them. But remember that what’s obvious to you may not be—and typically is not—obvious to your reader.
Most especially, don’t use phrases like “clearly” or “obviously” in an attempt to bully the reader into accepting something you’re having trouble proving. Also, go on the alert whenever you see one of these phrases in someone else’s proof.
Finish. At some point in a proof, you’ll have established all the essential facts you need. Resist the temptation to quit and leave the reader to draw the “obvious” conclusion. Instead, tie everything together yourself and explain why the original claim follows.
Creating a good proof is a lot like creating a beautiful work of art. In fact, mathematicians often refer to really good proofs as being “elegant” or “beautiful.” It takes a practice and experience to write proofs that merit such praises, but to get you started in the right direction, we will provide templates for the most useful proof techniques.
Throughout the text there are also examples of bogus proofs—arguments that look like proofs but aren’t. Sometimes a bogus proof can reach false conclusions because of missteps or mistaken assumptions. More subtle bogus proofs reach correct conclusions, but do so in improper ways such as circular reasoning, leaping to unjustified conclusions, or saying that the hard
, F. , & . Meyer 6/29/2021 1.9.1 CC-BY-NC-SA
part of the proof is “left to the reader.” Learning to spot the flaws in improper proofs will hone your skills at seeing how each proof step follows logically from prior steps. It will also enable you to spot flaws in your own proofs.
The analogy between good proofs and good programs extends beyond structure. The same rigorous thinking needed for proofs is essential in the design of critical computer systems. When algorithms and protocols only “mostly work” due to reliance on hand-waving arguments, the results can range from problematic to catastrophic. An early example was the Therac 25, a machine that provided radiation therapy to cancer victims, but occasionally killed them with massive overdoses due to a software race condition. A more recent (August 2004) example involved a single faulty command to a computer system used by United and American Airlines that grounded the entire fleet of both companies—and all their passengers! It is a certainty that we’ll all one day be at the mercy of critical computer systems designed by you and your classmates. So we really hope that you’ll develop the ability to formulate rock-solid logical arguments that a system actually does what you think it does!
, F. , & . Meyer 6/29/2021 1.9.2 CC-BY-NC-SA
CHAPTER OVERVIEW
2: WELL ORDERING PRINCIPLE
Every nonempty set of nonnegative integers has a smallest element.
This statement is known as The Well Ordering Principle. Do you believe it? Seems sort of obvious, right? But notice how tight it is: it requires a nonempty set—it’s false for the empty set which has no smallest element because it has no elements at all. And it requires a set of nonnegative integers—it’s false for the set of negative integers and also false for some sets of nonnegative rationals—for example, the set of positive rationals. So, the Well Ordering Principle captures something special about the nonnegative integers.
While the Well Ordering Principle may seem obvious, it’s hard to see offhand why it is useful. But in fact, it provides one of the most important proof rules in discrete mathematics. In this chapter, we’ll illustrate the power of this proof method with a few simple examples.
2.1: WELL ORDERING PROOFS
2.2: TEMPLATE FOR WELL ORDERING PROOFS 2.3: FACTORING INTO PRIMES
1 6/29/2021
2.1: Well Ordering Proofs
We actually have already taken the Well Ordering Principle for granted in proving that is irrational. That proof assumed that for any positive integers and , the fraction can be written in lowest terms, that is, in the form where and are positive integers with no common prime factors. How do we know this is always possible?
Suppose to the contrary that there are positive integers and such that the fraction cannot be written in lowest terms. Now let be the set of positive integers that are numerators of such fractions. Then , so is nonempty. Therefore, by
Well Ordering, there must be a smallest integer, . So by definition of , there is an integer the fraction cannot be written in lowest terms.
This means that and must have a common prime factor, . But
so any way of expressing the left hand fraction in lowest terms would also work for , which implies the fraction cannot be in written in lowest terms either.
So by definition of , the numerator, , is in . But , which contradicts the fact that element of .
such that
Since the assumption that is nonempty leads to a contradiction, it follows that must be empty. That is, that there are no numerators of fractions that can’t be written in lowest terms, and hence there are no such fractions at all.
We’ve been using the Well Ordering Principle on the sly from early on!
is the smallest
, F. , & . Meyer 6/29/2021 2.1.1 CC-BY-NC-SA
′m ′n/′m
n/m n m
′n
0m
0m < p/0m C p/0m p/0n
C
0n/0m
CC
, 0n = p/0n 0m p/0m
C ∈ ′m n/m nm
2–√
1>p
0n 0m
0 > 0n C
CC∈m C
0n/0m
p/0m
C
2.2: Template for Well Ordering Proofs
More generally, there is a standard way to use Well Ordering to prove that some property, holds for every nonnegative integer, . Here is a standard way to organize such a well ordering proof:
To prove that “ Define the set,
(The notation
is true for all ” using the Well Ordering Principle: , of counterexamples to being true. Specifically, define
means “the set of all elements for which is true.” See Section 4.1.4.)
Assume for proof by contradiction that is nonempty.
By the Well Ordering Principle, there will be a smallest element, , in .
Reach a contradiction somehow—often by showing that is actually true or by showing that there is another member of that is smaller than . This is the open-ended part of the proof task.
Conclude that must be empty, that is, no counterexamples exist.
Summing the Integers
Let’s use this template to prove
First, we’d better address a couple of ambiguous special cases before they trip us up:
Theorem 2.2.1.
for all nonnegative integers, n.
(2.1)
If , then there is only one term in the summation, and so appearance of 2 and 3 or by the suggestion that 1 and n are distinct terms!
is just the term 1. Don’t be misled by the If (n = 0\), then there are no terms at all in the summation. By convention, the sum in this case is 0.
So, while the three dots notation, which is called an ellipsis, is convenient, you have to watch out for these special cases where the notation is misleading. In fact, whenever you see an ellipsis, you should be on the lookout to be sure you understand the pattern, watching out for the beginning and the end.
We could have eliminated the need for guessing by rewriting the left side of (2.1) with summation notation: or
Both of these expressions denote the sum of all values taken by the expression to the right of the sigma as the variable, , ranges from 1 to . Both expressions make it clear what (2.1) means when . The second expression makes it clear that when , there are no terms in the sum, though you still have to know the convention that a sum of no numbers equals 0 (the product of no numbers is 1, by the way).
OK, back to the proof:
Proof. By contradiction. Assume that Theorem 2.2.1 is false. Then, some nonnegative integers serve as counterexamples to it. Let’s collect them in a set:
Assuming there are counterexamples, is a nonempty set of nonnegative integers. So, by the Well Ordering Principle, has a minimum element, which we’ll call . That is, among the nonnegative integers, is the smallest counterexample to equation (2.1).
, F. , & . Meyer 6/29/2021 2.2.1 CC-BY-NC-SA
i
1=n n .i n≤i≤1∑ i 1=i∑
■
cc CC
)n( P
.}
2 ≠n+⋯+3+2+1|N∈n{=:: C )1+n(n
)n( P Cn
)n(Q n
.}eurt si ))n( P(TON|N ∈ n{ =:: C
})n(Q|n{
n
n+⋯+3+2+1 1=n
2/)1+n(n=n+⋯+3+2+1
C
PC N∈n )n(P
C nC
0=n
n
Since is the smallest counterexample, we know that (2.1) is false for but true for all nonnegative integers . But (2.1) is true for , so . This means is a nonnegative integer, and since it is less than , equation (2.1) is true for . That is,
But then, adding c to both sides, we get
which means that (2.1) does hold for c, after all! This is a contradiction, and we are done.
, F. , & . Meyer 6/29/2021 2.2.2 CC-BY-NC-SA
■
.
2 )1+c(c
=
2 = c + 2 = )1 − c( + ⋯ + 3 + 2 + 1 c2+c− 2c c)1−c(
. 2 =)1−c(+⋯+3+2+1 c)1−c(
1−c c
2.3: Factoring into Primes
We’ve previously taken for granted the Prime Factorization Theorem, also known as the Unique Factorization Theorem and the Fundamental Theorem of Arithmetic, which states that every integer greater than one has a unique1 expression as a product of prime numbers. This is another of those familiar mathematical facts which are taken for granted but are not really obvious on closer inspection. We’ll prove the uniqueness of prime factorization in a later chapter, but well ordering gives an easy proof that every integer greater than one can be expressed as some product of primes.
Proof. The proof is by well ordering.
Let be the set of all integers greater than one that cannot be factored as a product of primes. We assume is not empty and
derive a contradiction.
If is not empty, there is a least element, , by well ordering. The can’t be prime, because a prime by itself is considered a (length one) product of primes and no such products are in .
Theorem 2.3.1.
Every positive integer greater than one can be factored as a product of primes.
So must be a product of two integers we know that . In other words,
and where . Since and are smaller than the smallest element in , can be written as a product of primes and as a product of primes can be written as a product of primes, contradicting the claim that . Our
. Therefore,
assumption that is not empty must therefore be false.
1. . . unique up to the order in which the prime factors appear
, F. , & . Meyer 6/29/2021 2.3.1 CC-BY-NC-SA
■
C
n nC∈nC
C∈n
C lq⋯1qkp⋯1p=n lq⋯1q
b
kp ⋯ 2p1p
a C ∉ b ,a b a n