Chapter 1 What is a Proof? 1.1 Mathematical Proofs A proof is a method of establishing truth. What constitutes a proof differs among fields. • Legal truth is decided by a jury based on allowable evidence presented at trial. • Authoritative truth is specified by a trusted person or organization. • Scientific truth1 is confirmed by experiment. • Probable truth is established by statistical analysis of sample data. • Philosophical proof involves careful exposition and persuasion typically based on a series of small, plausible arguments. The best example begins with “Cogito ergo sum,” a Latin sentence that translates as “I think, therefore I am.” It comes from the beginning of a 17th century essay by the mathemati-cian/philospher, Ren´e Descartes, and it is one of the most famous quotes in the world: do a web search on the phrase and you will be flooded with hits. Deducing your existence from the fact that you’re thinking about your exis-tence is a pretty cool and persuasive-sounding first axiom. However, with just a few more lines of argument in this vein, Descartes goes on to conclude that there is an infinitely beneficent God. Whether or not you believe in a beneficent God, you’ll probably agree that any very short proof of God’s ex-istence is bound to be far-fetched. So even in masterful hands, this approach is not reliable. 1Actually, only scientific falsehood can be demonstrated by an experiment —when the experiment fails to behave as predicted. But no amount of experiment can confirm that the next experiment won’t fail. For this reason, scientists rarely speak of truth, but rather of theories that accurately predict past, and anticipated future, experiments. 13� 14 CHAPTER 1. WHAT IS A PROOF? Mathematics also has a specific notion of “proof.” Definition. A formal proof of a proposition is a chain of logical deductions leading to the proposition from a base set of axioms. The three key ideas in this definition are highlighted: proposition, logical de-duction, and axiom. In the next sections, we’ll discuss these three ideas along with some basic ways of organizing proofs. 1.1.1 Problems Class Problems Problem 1.1. Identify exactly where the bugs are in each of the following bogus proofs.2 (a) Bogus Claim: 1/8 > 1/4. Bogus proof. 3 > 2 3 log10(1/2) > 2 log10(1/2) log10(1/2)3 > log10(1/2)2 (1/2)3 > (1/2)2 , and the claim now follows by the rules for multiplying fractions. � (b) Bogus proof : 1¢ = $0.01 = ($0.1)2 = (10¢)2 = 100¢ = $1. � (c) Bogus Claim: If a and b are two equal real numbers, then a = 0. Bogus proof. a = b a 2 = ab a 2 − b2 = ab − b2 (a − b)(a + b) = (a − b)b a + b = b a = 0. 2From Stueben, Michael and Diane Sandford. Twenty Years Before the Blackboard, Mathematical Asso-ciation of America, ©1998.1.2. PROPOSITIONS 15 Problem 1.2. It’s a fact that the Arithmetic Mean is at least as large the Geometric Mean, namely, a + b √ab2 ≥ for all nonnegative real numbers a and b. But there’s something objectionable about the following proof of this fact. What’s the objection, and how would you fix it? Bogus proof. a + b ? √ab, so2 ≥ ? a + b ≥ 2√ab, so ? a 2 + 2ab + b2 ≥ 4ab, so ? a 2 − 2ab + b2 ≥ 0, so (a − b)2 ≥ 0 which we know is true. The last statement is true because a −b is a real number, and the square of a real number is never negative. This proves the claim. � Problem 1.3. Albert announces that he plans a surprise 6.042 quiz next week. His students won-der if the quiz could be next Friday. The students realize that it obviously cannot, because if it hadn’t been given before Friday, everyone would know that there was only Friday left on which to give it, so it wouldn’t be a surprise any more. So the students ask whether Albert could give the surprise quiz Thursday? They observe that if the quiz wasn’t given before Thursday, it would have to be given on the Thursday, since they already know it can’t be given on Friday. But having figured that out, it wouldn’t be a surprise if the quiz was on Thursday either. Similarly, the students reason that the quiz can’t be on Wednesday, Tuesday, or Monday. Namely, it’s impossible for Albert to give a surprise quiz next week. All the students now relax, having concluded that Albert must have been bluffing. And since no one expects the quiz, that’s why, when Albert gives it on Tuesday next week, it really is a surprise! What do you think is wrong with the students’ reasoning? 1.2 Propositions Definition. A proposition is a statement that is either true or false.16 CHAPTER 1. WHAT IS A PROOF? This definition sounds very general, but it does exclude sentences such as, “Wherefore art thou Romeo?” and “Give me an A!”. But not all propositions are mathematical. For example, “Albert’s wife’s name is ‘Irene’ ” happens to be true, and could be proved with legal documents and testimony of their children, but it’s not a mathematical statement. Mathematically meaningful propositions must be about well-defined mathe-matical objects like numbers, sets, functions, relations, etc., and they must be stated using mathematically precise language. We can illustrate this with a few examples. Proposition 1.2.1. 2 + 3 = 5. This proposition is true. A prime is an integer greater than one that is not divisible by any integer greater than 1 besides itself, for example, 2, 3, 5, 7, 11, . . . . Proposition 1.2.2. For every nonnegative integer, n, the value of n2 + n + 41 is prime. Let’s try some numerical experimentation to check this proposition. Let 3 p(n) ::= n 2 + n + 41. (1.1) We begin with p(0) = 41 which is prime. p(1) = 43 which is prime. p(2) = 47 which is prime. p(3) = 53 which is prime. . . . p(20) = 461 which is prime. Hmmm, starts to look like a plausible claim. In fact we can keep checking through n = 39 and confirm that p(39) = 1601 is prime. But p(40) = 402 + 40 + 41 = 41 41, which is not prime. So it’s not true that the · expression is prime for all nonnegative integers. In fact, it’s not hard to show that no nonconstant polynomial with integer coefficients can map all natural numbers into prime numbers. The point is 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.
View Full Document
Unlocking...