Massachusetts Institute of Technology Lecture 1 6.042J/18.062J: Mathematics for Computer Science September 7, 2000 Professors Nancy Lynch and Shlomi Dolev

Proofs

Topics for today:

• Course overview

• What is a proof?

• Propositions

• Logical systems

• Proof examples

Reading: Velleman Chapter 1, Sections 3.1, 3.2. Rosen 1.1, 1.2, 1.4, 1.6, 3.1

1 Course Overview

1.1 Introductions

1.2 Course Goals and Content

This course will cover:

Basic discrete math concepts. Basic data types and structures used in programming and in reasoning about computer systems: Numbers, Booleans, strings; sets, functions, relations; digraph, graphs, trees; state machines. Their properties.

Proofs. How to do them, how to read them, how to recognize correct/incorrect ones. Reasoning about propositions, about predicates (with quantifiers). Common proof strategies: Direct proof, proof by contradiction, by cases.... Induction (very important in this course and elsewhere in CS).

Mathematical foundations for programming. Basic concepts and methods underlying formal specification and verification of software systems. Developing models for programs and their required behavior. Proving that a program model satisfies its correctness requirements.

Analytic Tools. The quantitative part of discrete math. Methods for handling series, sums, recurrences, asymptotic analysis, counting. The kind of math that tends to arise in computer science problems, e.g., analysis of algorithms.

Discrete probability. How to analyze random events. Probability provides good ways of modeling the unpredictability of the real world. Critical in the study of real computer systems.

Overall, we want you to learn how to use mathematics to help you think about concepts in computer science:

2 Lecture 1: Proofs • Define abstract models for computer science objects like programs, computers, networks...

• Think about these models carefully, correctly.

• Use the conclusions to help understand the real-world objects.

1.3 Administrivia

2 What is a proof (and why should we care)?

Rough definition: A way of convincing people that a statement is true. But there are many ways to convince someone that a statement is true, for example:

• Experimental evidence, e.g., physics experiments to validate theories of General Relativity; medical experiments to validate that rats that eat chemicals get cancer.

• Statistical sampling, e.g., Gallup polls to convince people that Bush will be elected President.

• Citing a reputable authority, e.g., “The professor said the answer to the problem was...”.

• Acting confident, talking loudly, e.g., “I’m sure my program works now.”

• Shifting the burden of proof to someone who disagrees with you, e.g., “I don’t see why not.”

These are not proofs, at least, not in the mathematical sense. All of these methods can go wrong, for example:

• Experiments can be contaminated or otherwise messed up.

• Statistics can be misleading, e.g., polled population could be non-representative, or people could lie to the pollsters.

• Authorities can make mistakes, e.g., Intel said the original Pentium chip worked fine.

Mathematics uses a particularly convincing way to argue that something is true:

Definition 2.1 A proof is a formal verification of a proposition by a chain of logical deductions starting from a base set of axioms.

The important pieces of this definition are:

Formal language: Need a precisely defined language for expressing everything. Proposition: Statement in the language, e.g., what you want to prove. Axioms: Statements that you are assuming in your proof. Logical deductions: Getting a new truth from old ones, according to agreed-upon, formal rules

of deduction.

In the rest of this lecture, I’ll explain what these things are, present basic proof methods, and give examples.

The main idea is to specify everything so precisely that everyone is convinced. Advantages: If people agree about assumptions and deduction rules, they must also agree about conclusions. Also, even if we can’t understand the entire argument at once, if we believe each deductive step, we can be comfortable accepting the conclusions.

We will try to teach you how to read and write proofs. For CS students, the main purpose is so that you can use them to reason carefully about ideas that arise in your (and other people’s) computer system designs/implementations.

3 Basic data types

First, we need to agree on some basic language of discourse so we can say things to each other. We’ll be using the standard basic data types used in programming: numbers, Booleans (true/false). (Also later strings, but skip for now.) We’ll also use other basic data types from mathematics, such as sets and functions. These are used in reasoning about programs. This is review for most of you, so I won’t lecture about it. I’ll just list the basic notions: definitions, operations, some properties. You will be expected to read this material carefully on your own, making sure you can do all the study exercises.

3.1 Booleans

Values: 1 (true), 0 (false). Operations: and (∧), or (∨), not (¬), exclusive-or (⊕). These operations can be explained with tables:

\begin{matrix}x & ¬x \\ 1 & 0 \\ 0 & 1 \end{matrix}

\begin{matrix}x & y & x ∧ y & x ∨ y & x ⊕ y \\ 1 & 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{matrix}

3.2 Numbers

These are just the standard number classes.

Natural numbers N = {0, 1, 2, … }

Most math books actually let N start at 1 rather than 0, but computer scientists like to start counting with 0. We’ll stay consistent with the course texts and start with 0. We’ll write N^{+} for the positive naturals.

Operations: +, − (a partial function), times, integer division (round down), remainder (mod), exponentiation

Prime number: Natural number ≥ 2 that has no divisors except for itself and 1. Example: 7 is prime, 14 is not.

4 Lecture 1: Proofs Integers, denoted by Z: N and its negatives Rationals, denoted by Q

These are all numbers that are expressible as a ratio of two integers \frac{a}{b}, where b ≠ 0. A basic theorem (we might prove it later) says that we can write any rational number in lowest terms.

Reals, denoted by R

3.3 Sets

Values: ∅, universal set U, singleton sets {a}. Relationships: Subset (⊆), proper subset (⊂). Operations are: Union (∪), intersection (∩), complement (overbar). Venn diagrams are useful for reasoning about sets. There are many laws about how the operations behave—see Rosen p. 49. E.g.: A ∪ A = A.

3.4 Functions

A function is a rule that assigns an element of one set (known as the range) to each element of another set (the domain). Operations include function inverse and composition (f ∘g(x) = f(g(x))). We’ll come back to this later.

4 Propositions

Now we consider the kinds of statements that we might want to convince people about.

4.1 What are propositions?

Definition 4.1 A proposition is a statement that has a truth value, true or false.

Examples:

1. 5 is a prime number.

This is a proposition, and it’s true.

2. 8 is a prime number.

This is a false proposition.

3. x is a prime number.

This is not a proposition. It has no truth value, because we don’t know what x is. It’s said to be an unbound variable.

4. There is an least one prime number. This is a true proposition. In math notation, it can be written as ∃x(x is a prime). The quantifier ∃ “binds” x.

Lecture 1: Proofs 5

5. All natural numbers ≥ 2 are primes.

This is a false proposition. It can be written as ∀x ∈ N, x ≥ 2(x is a prime). The quantifier ∀ also binds x. We will revisit the quantifiers soon (they have their own reasoning methods). For now, we are just using them as shorthand notation for the English phrases.

6. All x of the form n^{2} + n + 41, where n ∈ N, are prime.

This is a proposition. Is it true or false? That’s not immediately obvious. Certainly this proposition is true for many natural numbers n:

\begin{matrix}n = 0 → 41 & (prime) \\ n = 1 → 43 & (prime) \\ n = 2 → 47 & (prime) \\ n = 3 → 53 & (prime) \\ … & (more primes) \\ n = 20 → 461 & (prime) \\ … & (still more primes) \\ n = 39 → 1601 & (prime) \end{matrix}

However, if n = 40, then n^{2} + n + 41 = 40^{2} + 40 + 41 = 41 · 41, which is not prime. Since it is not the case that the expression is prime for all n, the proposition is false!

7. “true” and “false” are regarded as propositions, with the obvious truth values.

8. ∀A, B(\overline{A} ∪ \overline{B} = \overline{A ∪ B}).

Propositions can be about other things besides numbers, for instance, sets. This proposition happens to be false.

9. ∀A, B(\overline{A} ∪ \overline{B} = \overline{A ∩ B}).

∀A, B(\overline{A} ∩ \overline{B} = \overline{A ∪ B}). These are called De Morgan’s laws and are true.

10. The original Pentium chip always divided correctly.

Intel’s “proofs” by authority and by sampling turned out to be invalid. The proposition is false.

11. White can always win at chess.

A proposition whose truth value nobody knows.

12. Every even integer greater than 2 is the sum of two prime numbers. No one knows whether this proposition is true or false. This is the Goldbach Conjecture, which dates back to 1742. It was described in The Boston Globe as “one of the great unsolved mysteries.” Unfortunately, the “example” they gave was 20 = 9 + 11!

13. There is no x, y, z ∈ N^{+}, n ≥ 3 such that x^{n} + y^{n} = z^{n}.

This is Fermat’s last theorem, which he stated in the 1640s. Although he claimed it, he never proved it. Only recently have we learned for sure that it’s true. Andrew Wiles, in 1994, gave a 130-page proof. After months of work, other mathematicians found bugs. Wiles needed hundreds of more pages to fix them. But even while we didn’t know if it was true or false, it was still a proposition.

14. a^{4} + b^{4} + c^{4} = d^{4} has no positive integer solutions.

This statement was conjectured by Euler (1769). The first counterexample was found by Elkies, 218 years later. The smallest one: 95800^{4} + 217519^{4} + 414560^{4} = 422481^{4}.

15. Every map can be colored with four colors, in such a way that no two adjacent regions have the same color (Four-Color Theorem).

This proposition was first “proved” in 1879. The “proof” stood for 10 years before a flaw was found. Recently, the theorem was proved with computer aid. People still debate whether this is a valid proof. After all, nobody has proved that the computer is working correctly!

Not all sentences are propositions:

• x = y. (Truth depends on knowing what x and y are.)

• What time is it?

• This sentence is false.

4.2 Compound propositions and truth tables

Logical connectives are used to combine simple propositions into compound propositions. And (∧), or (∨), exclusive-or (⊕), and not (¬), which we already mentioned for Booleans, are also used for propositions. Other connectives used for propositions include implication (if-then, ⟹ ) and double implication (equivalence, ⇔). These are very important in logical reasoning. The truth values of compound propositions are obtained from the truth values of the simpler propositions according to the truth tables:

\begin{matrix}P & ¬P \\ T & F \\ F & T \end{matrix}

If a proposition P is true, then its negation is false, and vice versa.

P Q P ∧ Q P ∨ Q P ⊕ Q
T T  T  T  F
T F  F  T  T
F T  F  T  T
F F  F  F  F

Important: ∨ means inclusive or. It is true if either or both of the two statements are true. Sometimes in English or is used to mean exclusive or: “Lynch or Dolev will teach today” is saying one but not both.

P Q P ⇒ Q P ⇔ Q
T T  T  T
T F  F  F
F T  T  F
F F  T  T

The nice thing about these truth tables is that it doesn’t matter what the specific propositions are; we know how to get compound truth value from basic truth values.

The only slightly mysterious column here is the implication column. We say that P ⇒ Q is false only if the hypothesis P is true and the conclusion Q is false. Some thought shows this aligns with our intuition. Consider the statement “if you do your homework, then I will give you an A”. Under what circumstances would you accuse me of lying? Well, I am clearly lying if you do your homework but then you don’t get an A. But if you skip your homework and I give you an A anyway, you won’t say I’m lying. Also, if you skip your homework the statement promises nothing, so it is true regardless of what I do.

One way to determine truth values for compound propositions is by adding new columns to the basic truth table(s). Consider for example

R = (P ⇒ Q) ⇔ (¬Q ⇒ ¬P)

To decide the truth value of this messy proposition, we can evaluate its sub-propositions in a truth table and then combine their evaluations to evaluate the whole. This yields a column containing all T values. That is, the expression is always true, regardless of the truth values of P and Q.

P Q P ⇒ Q ¬Q ¬P ¬Q ⇒ ¬P R
T T  T  F F  T  T
T F  F  T F  F  T
F T  T  F T  T  T
F F  T  T T  T  T

An expression (like this one) whose column contains all T is called a tautology.

5 Logical Systems

Now we can say what proofs are. A proof takes axioms and definitions and uses deduction rules, step by step, to get a desired conclusion.

5.1 Axioms

Definition An axiom is a proposition that is assumed to be true.

Axioms aren’t proved—just accepted as reasonable assumptions. “Axiom” is Greek for “to think worthy,” not “to be true”. Here are some examples:

Axiom 1 (Arithmetic) If a = b and b = c, then a = c.

This seems very reasonable! But sometimes the right choice of axiom is not clear.

Axiom 2 (Euclidean geometry) Given a line l and a point p not on l, there is exactly one line through p parallel to l.

Axiom 3 (Spherical geometry) Given a line l and a point p not on l, there is no line through p parallel to l.

Axiom 4 (Hyperbolic geometry) Given a line l and a point p not on l, there are infinitely many lines through p parallel to l.

None of the three preceding axioms is better than the others; all yield equally good proofs. Of course, a different choice of axioms makes different propositions true. In fact, the axioms above are mutually contradictory—they can’t all be true.

Mathematicians still argue about which axioms are “right,” e.g., there is a lot of debate about the Axiom of Choice (whose assertion and denial are equally consistent with other commonly agreed upon axioms).

Axioms provide us with a place to start in building proofs. Every argument has assumptions. To be rigorous, it is important to state those assumptions explicitly as axioms.

5.2 Definitions

Definitions are used to agree on what something means.

• A natural number ≥ 2 is prime if it has no divisors other than itself and 1.

• A divisor of an integer z is a nonzero integer d for which there exists some integer k such that n = kd.

• A triangle is a polygon with 3 sides.

Definitions are axiomatic: we can define terms to mean whatever we want, so long as we do so unambiguously. Definitions can be built from prior definitions.

5.3 Deduction Rules

These are also called inference rules. They are rules for combining axioms and true propositions to construct more true propositions. The most fundamental inference rule is called modus ponens.

1. Modus ponens:

Given that P and P ⇒ Q are both true Conclude: Q

2. Modus tolens (proof by contradiction): Given: P ⇒ Q, ¬Q Conclude: ¬P

3. Syllogism:

Given: P ⇒ Q, Q ⇒ R Conclude: P ⇒ R

4. Given: ¬P ⇒ false Conclude: P

5. Given: P, ¬P:

Conclude: false 6. (Cases):

Given: Q ⇒ P, ¬Q ⇒ P Conclude: P

These deduction rules rely only on the truth values of the statements P, Q, R, and not on what the particular statements are. So we can apply them in many situations.

Truth tables provide a source of deduction rules, all of which are accepted in mathematics. Namely, if R ⇒ S is a tautology, then Given: R Conclude: S is an allowable inference rule.

Examples:

1. [P ∧ (P ⇒ Q)] ⇒ Q is a tautology (check in truth table), which leads to (Modus Ponens): Given: P ∧ (P ⇒ Q) Conclude: Q

2. (P ∧ ¬P) ⇒ false is a tautology, which leads to:

Given: P, ¬P: Conclude: false

3. [(P ∨ Q) ∧ ¬P] ⟹ Q is a tautology, which leads to (Disjunctive Syllogism): Given: P ∨ Q, ¬P Conclude: Q

Another way of getting acceptable deduction rules from a truth table, exemplified using Modus Ponens again: In the truth table, look at the rows where P and P ⇒ Q are both true. P is true in rows 1, 2 . Q is true in rows 1, 3, 4 . So, both are true exactly in row 1. But in that row, Q is also true.

5.4 Formal proofs

In a complete, formal proof of a theorem, each step follows from previous steps using formal deduction rules. Such a process is ideally so systematic that it could be checked mechanically by a program. Theorem proving programs can do this.

What about using a computer to produce proofs of true theorems automatically? Hilbert posed (as one is his 23 famous problems) the problem of finding a method that could generate all proofs of true theorems. One of the great accomplishments of 20th century math is the proof that no such method exists (Gödel). So we will always rely on human intuition to find the proofs, although computers can be used to check that they are right.

Mathematicians don’t actually write proofs that formally and completely: they leave a lot of gaps that they expect a “knowledgeable reader” can fill in.

6 Proof examples

This section contains some examples of proofs using the deduction rules described above. They are presented at about the level of detail commonly used by mathematicians. The examples illustrate basic methods: direct proof, proof by contradiction, and proof by cases.

These proofs are written in a stylized way, using statements and reasons (as in high school geometry proofs). In math books, proofs are usually presented in prose, with the logical structure left implicit. Caution: The proof writer is expecting the reader to figure out the logical structure. To understand the proofs, you really have to do this.

6.1 Direct proof

To prove that a proposition of the form P ⇒ Q is true, it is enough to assume P and show Q. Written in a structured style, the pattern of such a proof is:

Prove: P ⇒ Q

1. Assume P.

2. Q

3. QED Implication

QED stands for Quod Erat Demonstrandum, Latin for “which was to be proved”. Here, it’s a shorthand for writing the goal out again as the final step.

Example 6.1 Let’s prove that the sum of the first 100 numbers, 1+...+100, is 5050. We’ll rewrite this as an implication and use the direct proof rule above.

Prove: S = 1 + ... + 100 ⇒ S = 5050.

1. Assume S = 1 + ... + 100.

2. S = 5050 ???

3. QED (That is, S = 1 + ... + 100 ⇒ S = 5050.) Implication

Of course, the interesting part is to fill in the ???. This needs some calculations:

Prove: S = 1 + ... + 100 ⇒ S = 5050.

1. Assume S = 1 + ... + 100.

2. S = 5050 1. S = 100 + 99 + ... + 1 Commutativity of addition 2. 2S = 101 + 101 + ... + 101 (100 terms) Add term-by-term

3. 2S = 10, 100 Add the terms up

4. QED (That is, S = 5050.) Divide by 2

3. QED (S = 1 + ... + 100 ⇒ S = 5050.) Implication

Example 6.2 The following argument shows a property of basic set theory. It says that, if an element x is in the complements of sets A and B, then it is in the complement of their union. Like the previous proof, this one involves a direct, step-by-step calculation.

Prove: x ∈ \overline{A} ∩ \overline{B} ⇒ x ∈ \overline{A ∪ B}

1. Assume x ∈ \overline{A} ∩ \overline{B}

2. x ∈ \overline{A}, x ∈ \overline{B} Definition of intersection

3. x ∉ A, x ∉ B Definition of complement

4. x ∉ A ∪ B Definition of union

5. x ∈ \overline{A ∪ B} Definition of complement

6. QED (x ∈ \overline{A} ∩ \overline{B} ⇒ x ∈ \overline{A ∪ B}) Implication

6.2 Proof by contradiction

To prove that a proposition P is true, it is enough to prove that ¬P ⇒ false. The pattern is:

Prove: P

1. ¬P ⇒ false

2. QED Contradiction

Some variants of this:

Prove: P

1. ¬P ⇒ (Q ∧ ¬Q)

2. QED Contradiction

Prove: P

1. ¬P ⇒ Q

2. ¬Q

3. QED Contradiction

Example 6.3

Assume: If Richard gets at least four hours of sleep then he passes his 6042 final. Richard fails his 6042 final. Prove: Richard gets less than four hours of sleep.

Here, let P = “Richard gets less than four hours sleep.”. Q = “Richard passes.”. So the proof steps for proving P are:

Prove: Richard gets less than four hours of sleep.

1. If Richard gets at least four hours of sleep then he passes. (¬P ⇒ Q).

Assumed

2. Richard fails (¬Q). Assumed

3. QED (Richard gets less than four hours of sleep.) Contradiction

Example 6.4 A more interesting proof by contradiction.

Prove: \sqrt{2} is irrational.

1. \sqrt{2} rational ⇒ false

2. QED Contradiction.

Assume it’s rational, play with the definitions, and try to get a contradiction.

Prove: \sqrt{2} is irrational.

1. \sqrt{2} rational ⇒ false 1. Assume \sqrt{2} rational.

2. false 1. Choose a, b ∈ N^{+}, \sqrt{2} = \frac{a}{b}, lowest terms. Basic property of rationals.

2. 2b^{2} = a^{2} Algebra

3. a^{2} is even. Definition of “even”

4. a is even.

5. Choose c ∈ N, a = 2c.

6. 4c^{2} = a^{2} = 2b^{2} Algebra

7. 2c^{2} = b^{2} Algebra

8. b^{2} is even. Definition of “even”

9. b is even.

10. a and b aren’t in lowest terms. 1.2.4, 1.2.9

11. QED (false) 1.2.1, 1.2.10, propositional logic 3. QED (\sqrt{2} rational ⇒ false) Implication

2. QED (\sqrt{2} is irrational) Contradiction

Some steps aren’t justified here:

• Showing that a and b are even, because we know their squares are even.

• Some other points involving quantifier logic.

We may revisit this next week to fill in the gaps.

6.3 Proof by cases

To prove that a proposition P is true, it is enough to prove that Q and ¬Q both imply P, where Q is any other proposition. This shows P is true in either case, so it’s always true.

Prove: P

1. Q ⇒ P

2. ¬Q ⇒ P

3. QED Cases

This generalizes to any number of predicates, provided that together they cover all possibilities. If Q_{1} ∨ Q_{2} ∨ … ∨ Q_{k} is always true, and you can show each Q_{i} implies P, then you can infer P.

Example 6.5

Assume: d = Susan’s birth date (day of month, 1-31). Prove: d^{2} + d is even.

1. d = 1 ⇒ d^{2} + d = 2 is even.

2. d = 2 ⇒ d^{2} + d = 6 is even. 3….

31. d = 31 ⇒ d^{2} + d = 992 is even.

32. QED (d^{2} + d is even.) Cases More clever proofs than this one might consider fewer cases. For example, can we just consider whether d is even or odd?

Example 6.6 This example combines an argument by contradiction and an argument by cases.

Prove: There are infinitely many prime numbers.

1. Assume there are only finitely many prime numbers.

2. false 1. Choose P to be the finite set of all prime numbers, and define m to be 1 + Π_{p∈P} p.

2. m isn’t in P. It’s larger than all the elements of P.

3. m isn’t divisible by anything in P. Remainder is 1 for any such division.

4. There is some prime that isn’t in P.

1. If m is prime then there is some prime that isn’t in P. m is an example.

2. If m is not prime then there is some prime that isn’t in P. 1. Assume m is not prime.

2. m has a prime divisor. Number theory fact

3. Choose q to be a prime divisor of m.

4. q isn’t in P m is divisible by q, but not by any p ∈ P.

5. There is some prime that isn’t in P.

6. QED Implication

3. QED (There is some prime that isn’t in P.)

Cases

3. QED (false)

3. QED (Infinitely many primes) Contradiction

We may prove the missing number theory fact later in the course. Again, some arguments about quantifiers are made informally, so we may want to return to these after we study quantifier logic.

7 Good proofs

Some features of good proofs:

• They must be correct.

• They should be clear and understandable.

• They should have nice structure: They should be broken up into pieces that prove key intermediate properties (lemmas). (This makes them easier to understand, and possibly reusable.)

• They should be written fairly generally and abstractly, so they apply to many cases.

• Don’t leave gaps, saying something is obvious when it isn’t.

• Elegant, economical,...

Notice that many of these are also features that we look for in good programs.