Topic 3 - Lecture notes CHAPTER 3 PDF

Preview

Summary

MATH1081 Discrete Mathematics F and D / D Topic 3 Proof, Induction and Symbolic Logic 3 Proofs The subject matter of this section is mathematical proof itself, and not the particular results proved in the lecture notes or tutorial problems. (Some may be useful elsewhere, but that is not the point.) ...

Description

MATH1081 Discrete Mathematics

F.Kuo and D.Angell / D.Trenerry

Topic 3 Proof, Induction and Symbolic Logic 3.1 Proofs The subject matter of this section is mathematical proof itself, and not the particular results proved in the lecture notes or tutorial problems. (Some may be useful elsewhere, but that is not the point.) The defining characteristic of modern mathematics is proof . In ancient times, mathematics consisted of a collection of rules for calculation which seemed to work; it appears that the cultures of Egypt, Babylon and others did not demand any more than this. But, since the time of the Ancient Greeks, mathematicians have become more picky! We now want to be sure, as far as possible, that our techniques work; we also want to understand why they work and to know how they are related to each other, how they fit into the broader picture. It is suggested that you also look at the book by Franklin and Daoud. In today’s world there are various concepts of proof: Mathematical proof consists of logical deduction on the basis of agreed premises. Apart from human error the results are certain. Scientific proof is achieved by induction (not mathematical induction). The results, in principle, can never be certain, although some scientific conclusions have so much confirmation that they can be regarded as virtually certain. Statistical inference says that on the basis of certain observations, some conclusion is likely, and can also give an estimate of how likely. Legal proof relies on the concept of beyond reasonable doubt You learn the techniques and strategies of proof by practice, practice, practice!!! We look at many useful techniques, but there are no foolproof recipes!

1

Some examples of proof problems: Proving a simple statement p p √ √ √ e.g. Prove that 2 + 2 + 2 − 2 < 2 2. √ e.g. Prove that 2 is irrational. Proving a universal statement e.g. Prove that x3 + 2x is divisible by 3 for all integers x. n+1) e.g. Prove that 12 + 22 + 32 + · · · + n2 = n(n+1)(2 for all n ∈ Z+ . 6

Proving an “if... then...” statement or “if and only if” statement

e.g. Prove that if n is an even integer then n2 is an even integer. e.g. Prove that an integer is even if and only if its square is even. Proving an existential statement e.g. Prove that a2 + b2 = c2 has nonzero integer solutions. e.g. Prove that ex = 4 sin( πx ) has a solution ξ satisfying 0 < ξ < 1. 2 Disproving a universal statement e.g. Prove that the statement “All prime numbers are odd” is false. Notation: A statement (or more formally a proposition) is a sentence or clause that is unambiguously true or false . We will use symbols like p and q to stand for statements or propositions. If a sentence or clause includes a variable and becomes a proposition when the variable takes a value, then we will call it a predicate and denote it like P (x) or P (x, y) for two variables, etc. Example. “Canberra is the capital of Australia” is a proposition which is true. “1 is a prime number” is a proposition which is false. “2 + 2 = 4” is a proposition which is true. “x + y = 4” is not a proposition, because it can be either true or false depending on the values of x and y . It is actually a predicate in two variables.

2

Exercise. Is the sentence “This sentence is false” a proposition?

Overview of proof techniques: Direct proof We start with the given facts and assume only obvious truths or previously proved results, to eventually arrive at the desired result. To prove that “if p is true, then q is true”, or “p implies q”, we start with p and eventually arrive at q. Proof by exhaustion of cases (for proving some universal statements) Proof by contrapositive (for proving a conditional statement) To prove that “if p is true, then q is true”, we prove its contrapositive “if q is false, then p is false”, that is, we start with “q is false” and eventually arrive at “p is false”. ... continued Proof by counterexample (for disproving a universal statement) Proof by contradiction We assume that the desired result is false and eventually end up with a contradiction, thus concluding that the desired result must be true. To prove that “if p is true, then q is true”, we start with p and assume that q is false, and eventually end up with a contradiction. Proof by mathematical induction

3

A proof should be written in complete sentences, with correct spelling and grammar (and punctuation). It should include a suitable introduction and conclusion, reason for all statements made, correct logical flow, and any algebraic details. It is a good exercise to start your proof with the word “Proof:”, and end it with something like “This completes the proof.”, or “Q.E.D.” (latin for “which was to be demonstrated”), or the symbol ✷. There are a variety of common mistakes that should be avoided: Vague or ambiguous premises. “Begging the question”: this means starting a proof by assuming what you are trying to prove. “Jumping to conclusions”: this means skipping necessary parts of the proof. “Converse error”: Proving “if q is true, then p is true” when you really want to prove “if p is true, then q is true”. “Inverse error”: Proving “if p is false , then q is false” when you really want “if p is true, then q is true”. Proving a simple statement by a direct proof Example. Prove that

1 1 1 − < . 1000 1001 10002

Proof. We have

1 1 1001 − 1000 1 − = = . 1000 1001 1000 × 1001 1001000 Since 1001000 > 1000000, and both numbers are positive, we have 1 1 < . 1001000 1000000 Hence we conclude that This completes the proof.

1 1 1 . − < 10002 1000 1001 ✷

4

In this proof, we began from the left-hand side of the inequality and worked toward the right-hand side. Why didn’t we just put the numbers on a calculator? : 1 1 = 0.001 − 0.0009990010 = 0.00000990 < 0.000001 = − 1001 1000

1 . 10002

Reasons for using calculators: They are quick and easy to use, especially for one-off applications. They are generally accurate if you only want a few decimal places. (We could use Maple if we wanted lots of decimal places.) Reasons for not using calculators: They suppress understanding. They suppress generality. For example, from above, what can you say about 1 1 1 1 1 or more generally n1 − n+1 or 1000000 − 1000001 − 2001 ? 2000 They are hardly ever absolutely correct. This is especially a problem if we wish to determine whether two expressions are or are not equal.

For Example (see the Maple PDF): Re-do the above calculation with a 2 digit calculator. (Maple: set Digits:=2) Is 1020 equal to 1020 + 1 (on a calulator)? √ √ Are 8 + 31 15 and 20 41 equal? Are

q

3+

√

p

√ √ 13 + 4 3 and 1 + 3 equal?

√ Are 5 + 22 + 2 q 5 and p p √ √ √ 11 + 2 29 + 16 − 2 29 + 2 55 − 10 29 equal? Is eπ

√ 163

p

an integer?

5

Example. √ √ Prove that 8 8! < 9 9! . Discovery (not the proof): √ 8

√ 9

9! √ 9 ( 8!)72 < ( 9!)72 (8!)9 < (9!)8 (1 × 2 × · · · × 8)9 < (1 × 2 × · · · × 9)8 (1 × 2 × · · · × 8)8 × (1 × 2 × · · · × 8) < (1 × 2 × · · · × 8)8 × 98 1 × 2 × · · · × 8 < 98 √ 8

8! <

You cannot prove something is true by assuming it is true. We worked backwards to find a suitable starting point for the proof. Now we write out the proof correctly.

Proof. Clearly 1 < 9, 2 < 9, . . . , 8 < 9, and so 1 × 2 × · · · × 8 < |9 × 9 ×{z· · · × 9} = 98 . 8 times

Multiplying both sides by the positive number (1 × 2 × · · · × 8)8 , we obtain (1 × 2 × · · · × 8)9 < (1 × 2 × · · · × 8 × 9)8 , which is equivalent to (8!)9 < (9!)8 . Now everything is positive, so taking the 72nd root of both sides, we get √ √ 8 9 8! < 9! . This completes the proof.

✷

6

A proof is often discovered by working backwards, but it must be written forwards. Explain logical and technical steps in words with punctuation. Do not just write down a string of formulae. Using a Direct Proof: If p is known to be true and we want to deduce that q is true, then a direct proof takes the form Since p is true, .. . Hence q is true. To prove “if p then q” by a direct proof, we follow the outline Suppose p is true. .. . Hence q is true. Exercise. (Harder) Prove that

1 p

2−

√

2

− p

1 √ >√ . 2 2+ 2 1

7

Generalisation The results we have proved above are of very little interest in themselves as they refer only to specific numbers. However, once we have proved 1 1 1 − < 1000 1001 10002 it is clear that the same method will enable us to prove the general result: Example. Prove that for all n ∈ Z+,

1 1 1 − < 2. n n+1 n

Proof. Let n ∈ Z+ . Then we have 1 1 1 − = . n n+1 n(n + 1) But n(n + 1) > n2 , and both numbers are positive, so we have 1 1 < 2. n(n + 1) n 8

Hence we conclude that

1 n

−

1 1 < n2 . n+1

This completes the proof.

✷

Similarly we can generalise the result Exercise. Prove that for all n ∈ Z+,

√ n

n! <

√ 8

8! <

p

n+1

√ 9

9! :

(n + 1)!.

9

Universal statement or ALL statement : A statement of the form “ for all x ∈ A, ......” is called a universal statement . We write this as

“ ∀x ∈ A, ......”

If it is known what the universe for x is, we can also write

“ ∀x, ......”

Proving a universal statement: “∀x ∈ A, Q(x) is true” or “∀x ∈ A, if P (x) is true, then Q(x) is true” A proof generally takes the form (respectively) Suppose x is in A. .. . Hence Q(x) is true.

or

Suppose x is in A. If P (x) is true, then .. . Hence Q(x) is true.

A universal statement cannot be proved by giving examples (unless it is possible to cover all cases, see “proof by exhaustion of cases” below). Universal statements can take many forms, such as For each x ∈ A, property B holds For all x ∈ A, P (x) is true P (x) is true for all x ∈ A For an abritary x ∈ A, x ∈ B For every x ∈ A, P (x) is true Given any x ∈ A, P (x) is true Suppose x ∈ A, then P (x) is true Let x be in A, then P (x) is true Every C is a D No C is not a D If p is true, then q is true. etc Many results in mathematics are universal statements. Example. “If n is an even integer, then n2 is even” can be written as “∀n ∈ Z, if n is even, then n2 is even”. 10

Example. Prove that the function f : R → R defined by f(x) = 2x3 − x is an odd function. Recall: A function f is an odd function means “f(−x) = −f(x) for all x ∈ R”. A function f is an even function means “f(−x) = f(x) for all x ∈ R”. Note that most functions are neither odd nor even. Also a function can actually be both (when?). Proof. For all x ∈ R, we have f (−x) = 2(−x)3 − (−x) = −2x3 + x = −(2x3 − x) = −f (x). Thus f is an odd function.

✷

Example. Prove that for all positive integers m and n we have m! n! < (m + n)!. Proof. Let m and n be positive integers. Since 1 < m + 1, 2 < m + 2, . . ., and n < m + n, we have m! n! = (1 × 2 × · · · × m) × (1 × 2 × · · · × n) < (1 × 2 × · · · × m) × ((m + 1) × (m + 2) × · · · × (m + n)) = (m + n)! This completes the proof.

✷

11

Exercise. Prove that for all integers a, b and c, if a2 |b and b3 |c then a4 b5 |c3 .

Exercise. Prove that 11n2 + 32n is a prime number for exactly two integer values of n.

12

Proving a universal statement by exhaustion of cases Suppose that it is the case that: at least one of each of a finite list {p1 , p2 , . . . pn } of statements is true and, that each of these statements implies that some statement q is true, then it follows that the statement q is true. Example. Prove that x3 + 2x is divisible by 3 for all integers x. Proof. This is the same as proving that x3 + 2x ≡ 0 (mod 3) for all x ∈ Z. We have three cases to consider: If x ≡ 0 (mod 3) then x3 + 2x ≡ 03 + 2 × 0 ≡ 0 (mod 3). If x ≡ 1 (mod 3) then x3 + 2x ≡ 13 + 2 × 1 ≡ 3 ≡ 0 (mod 3).

If x ≡ 2 (mod 3) then x3 + 2x ≡ 23 + 2 × 2 ≡ 12 ≡ 0 (mod 3). In all three cases we have x3 + 2x ≡ 0 (mod 3). Thus x3 + 2x is divisible by 3 for all x ∈ Z.

✷

Alternatively, we can argue that any integer x is in one of three forms: 3k , 3k + 1, or 3k + 2, for some integer k, and then show that in all three cases the number x3 + 2x can be written as 3 times an integer.

Note that the above example can be somewhat simplified if we had used the same approach as in the following. Example. Show that for all n ∈ Z, we have n3 ≡ n (mod 6). Proof. Let n ∈ Z. There are 6 possible cases n ≡ 0, 1, 2, 3, 4, 5

(mod 6).

In these cases we have, respectively n3 ≡ 0, 1, 8, 27, 64, 125

(mod 6).

Simplifying modulo 6 gives n3 ≡ 0, 1, 2, 3, 4, 5 respectively. Clearly in every case n3 ≡ n (mod 6).

(mod 6), ✷

13

Exercise. Prove that the square of any odd integer has the form 8m + 1 for some integer m. An obvious way forward is to assume that n = 2k + 1 for some integer k. But then we obtain n2 = (2k + 1)2 = 4k 2 + 4k + 1. This is not helpful (unless you notice that it equals 4k(k + 1) + 1 and that one of k or k + 1 are even).

Exercise. Prove that 6|x| + 4|x − 2| ≤ 3x2 − 4x + 11 for all real numbers x. Recall: The absolute value function is defined for all real numbers x by ( x if x ≥ 0, |x| = −x if x < 0.

14

Writing Proofs - some comments Proving a given statement can be said to involve two stages: discovering the reasons why the statement is true, then presenting these reasons as a coherent, carefully written argument. The first part may well be “mathematically” more difficult; however, the second is not easy either and will require a good deal of practice. In constructing a mathematical proof, always take the point of view that you are writing it for someone else to read! If you “know what you mean” that’s good, but it’s only half the job. You should explain in words what you are doing, and give reasons for your conclusions: an unconnected string of equations is not adequate because it does not explain why a certain step is taken, why a particular claim is true. As a general rule, a proof with no words is a very poor proof !

15

A typical question on writing proofs in MATH1081 is: “ In the following exercise you are given a theorem, together with the basic ideas needed to prove it. Write up a detailed proof of the theorem. Your answer must be written in complete sentences, with correct spelling and grammar. It must include a suitable introduction and conclusion; reasons for all statements made; correct logical flow; and any necessary algebraic details. Theorem. Let n be an integer. If n is even then n2 is even. Basic ideas: n = 2k, so n2 = 4k 2 . ”

Here is the answer to the question: Theorem. Let n be an integer. If n is even then n2 is even. Proof. Let n be an integer. Suppose that n is even. Then by definition n = 2k for some integer k . Squaring both sides gives n2 = (2k)2 = 4k 2 = 2(2k 2 ) = 2m. But k is an integer, so m = 2k 2 is also an integer. Hence n2 is even.

✷

16

Things to learn from this proof. Clarity of expression. A proof must be written in complete sentences, with correct spelling and grammar! Among other things, each sentence must begin with a capital letter and end with a full stop. A sentence should begin with a word! It is usually regarded as poor style to begin a sentence with mathematical notation, as in, for example: “n = 2k because n is even.” This can be avoided by inserting some introductory words: “We can write n = 2k because n is even.” or by reordering the sentence: “Because n is even we have n = 2k .” In text, writing mathematical clauses consecutively with no words between them can make the proof unclear. Instead of “Let n = 2k, k ∈ Z” write “Let n = 2k, where k ∈ Z”. Structure of a proof. Begin with a clear statement of the result you are proving. In a test or exam this will probably only mean copying out the question – all the same, its important! Write the word “Proof”; then begin your argument. Any notation you use, any variables, must be introduced properly. If n is to be an integer you should say so: don’t just start straight in with “n = 2k”. It is vital that the logic of the proof be clear. In this case we are to show that “if n is even then n2 is even”; as we have seen earlier a possible proof pattern for this is “Suppose that n is even. . . therefore n2 is even.” Both of these sentences appear in our proof. Include a conclusion which clearly indicates the end of the proof.

17

Helping the reader. Give reasons for all your conclusions. If the reason is brief it is often good to give it before the conclusion: in the preceding proof “by definition” and “since k is an integer” are examples of this. It is also helpful to explain technical and algebraic steps (“squaring both sides”). Remember, you know what you are about to do – your readers don’t! You should do all you can to help them. Often in this kind of exercise the ideas we give you will require amplification: with “n = 2k” you need to make the comment that k is an integer. (If it isn’t, then n isn’t even!) We shall also expect you to fill in algebraic steps where necessary. Try to get the level of argument right. This is not easy! Here, for example, it would not be good to say “n2 is even because even times even is even”, as this is more or less what you are asked to prove. The proof of any statement must be based upon simpler statements. Nevertheless, as a general rule in MATH1081 you may take as known anything you have done in school (or MATH1131/1141/1151): this could include basic arithmetic, algebra, calculus, geometry and trigonometry. Note: In MATH1081, proper presentation is regarded as essential for all proofs, not only those specifically tagged as proof-writing exercises! (However, we will mark the proof-writing problems more strictly than the rest of the problems.)

18

Some notation Instead of “p is true” we will sometimes simply write “ p ”, and for “p is false” we sometimes write “ ∼ p ”, read as “not p”. Negation The negation of “p is true” (p) is “p is false” (∼ p). The negation of “p is false” (∼ p) is “p is true” (p). Negation of “and” and “or” “it is false that ‘p is true and q is true’ ” (∼ (p and q)) is logically the same as “p is false or q is false” (∼ p or ∼ q).

“it is false that ‘p is true or q is true’ ” (∼ (p or q ) )is logically the same as “both p and q are false” (∼ p and ∼ q).

“and” and “or” with ”∼” satisfy De Morgan’s Laws – more on this later. NOTE that in Mathematics and logic, “or” means the “inclusive or ” meaning “one or the other or both” and “and” means “both”.

Example. The negation of the statement “it is hot and sunny” (which means “it is hot and it is sunny”) is “it is not hot or it is not sunny”. NOTE that the English sentence “it is neither hot nor sunny” means something different, namely “it is not hot and it is not sunny”, and this is the negation of “it is hot or it is sunny”. (In MATH1081 we will try to avoid unclear English statements, but you should think about them – we will come back to this later.) The statement “0 < x < 1” means “0 < x and x < 1”. It’s negation is “0 6< x or x 6< 1”, which is the same as “0 ≥ x or x ≥ 1”. This is usually written as “x ≤ 0 or x ≥ 1” The negation of “If it is raining, then it is cloudy” is “It is raining and it is not cloudy”, which is often written “it is raining, but is not cloudy”. The negation of “if n is a prime then n is odd” is “n is prime and n is not odd”.

19

Contrapositive of a statment For a conditional statement of the form “if p is true, then q is true”, its contrapositive is...