Section 3 Theorem 13 A B A and B True True True True False False False True False False False False Mathematical use of not. The statement "not A"is true if and only if A is false.For example,the statement "All primes are odd"is false.Thus the statement "Not all primes are odd"is true.Again,we can summarize the use of not in a chart. A notA True False False True Mathematical use of or. Thus the mathematical usage of and and not corresponds closely with standard English.The use of or,however,does not.In standard English,or often suggests a choice of one option or the other,but not both.Consider the question"Tonight, when we go out for dinner,would you like to have pizza or Chinese food?"The implication is that we'll dine on one or the other,but not both. In contradistinction,the mathematical or allows the possibility of both.The statement"A or B"means that A is true,or B is true,or both A and B are true. For example,consider the following: Suppose x and y are integers with the property that xly and ylx.Thenx =y or=-y. The conclusion of this result says that we may have any one of the following: .x=y but not x =-y (e.g.,takex =3 and y 3). .x=-y but not x y (e.g.,takex=-5 and y 5). .x=y andx =-y,which is possible only whenx =0 and y =0. Here is a chart for or statements. 以 B Aor B True True True True False True False True True False False False What Theorems Are Called The word theorem should Some theorems are more important or more interesting than others.There are not be confused with the alternative nouns that mathematicians use in place of theorem.Each has a slightly word theory.A theorem is different connotation.The word theorem carries the connotation of importance and a specific statement that generality.The Pythagorean Theorem certainly deserves to be called a theorem. can be proved.A theory is The statement "The square of an even integer is also even"is also a theorem,but a broader assembly of ideas on a particular issue. perhaps it doesn't deserve such a profound name.And the statement"6+3 =9" is technically a theorem but does not merit such a prestigious appellation
Mathematical use of not. Mathematical use of or. The word theorem should not be confused with the word theory. A theorem is a specific statement that 1 can be proved. A theory is a broader assembly of ideas on a particular issue. Section 3 Theorem 13 A B A and B True True True True False False False True False False False False The statement "not A" is true if and only if A is false. For example, the statement "All primes are odd" is false. Thus the statement "Not all primes are odd" is true. Again, we can summarize the use of not in a chart. A not A True False False True Thus the mathematical usage of and and not corresponds closely with standard English. The use of or, however, does not. In standard English, or often suggests a choice of one option or the other, but not both. Consider the question "Tonight, when we go out for dinner, would you like to have pizza or Chinese food?" The implication is that we'll dine on one or the other, but not both. In contradistinction, the mathematical or allows the possibility of both. The statement "A orB" means that A is true, orB is true, or both A and B are true. For example, consider the following: Suppose x and y are integers with the property that xI y andy lx. Then .1.:· = y or x = -y. The conclusion of this result says that we may have any one of the following: x = y but not x = -y (e.g., take x = 3 andy = 3). x = -y but not x = y (e.g., take x = -5 andy= 5). x = y and x = -y, which is possible only when x = 0 andy= 0. Here is a chart for or statements. A B A orB True True True True False True False True True False False False What Theorems Are Called Some theorems are more important or more interesting than others. There are alternative nouns that mathematicians use in place of theorem. Each has a slightly different connotation. The word theorem carries the connotation of importance and generality. The Pythagorean Theorem certainly deserves to be called a theorem. The statement "The square of an even integer is also even" is also a theorem, but perhaps it doesn't deserve such a profound name. And the statement "6 + 3 = 9" is technically a theorem but does not merit such a prestigious appellation
14 Chapter 1 Fundamentals Here we list words that are alternatives to theorem and offer a guide to their usage. Result A modest,generic word for a theorem.There is an air of humility in calling your theorem merely a "result."Both important and unimportant theorems can be called results. Fact A very minor theorem.The statement"6+3 =9"is a fact. Proposition A minor theorem.A proposition is more important or more gen- eral than a fact but not as prestigious as a theorem. Lemma A theorem whose main purpose is to help prove another,more im- portant theorem.Some theorems have complicated proofs.Often one can break the job of proving a complicated theorem down into smaller parts. The lemmas are the parts,or tools,used to build the more complicated proof. Corollary A result with a short proof whose main step is the use of another, previously proved theorem. Claim Similar to lemma.A claim is a theorem whose statement usually ap- pears inside the proof of a theorem.The purpose of a claim is to help organize key steps in a proof.Also,the statement of a claim may involve terms that make sense only in the context of the proof. Vacuous Truth What are we to think of an if-then statement in which the hypothesis is impossible? Consider the following: Statement 3.2 (Vacuous)If an integer is both a perfect square and prime,then it is negative. Is this statement true or false? The statement is not nonsense.The terms perfect square (see Exercise 2.6), prime,and negative properly apply to integers. We might be tempted to say that the statement is false because square numbers and prime numbers cannot be negative.However,for a statement of the form"If A,then B"to be declared false,we need to find an instance in which clause A is true and clause B is false.In the case of Statement 3.2,condition A is impossible; there are no numbers that are both a perfect square and prime.So we can never find an integer that renders condition A true and condition B false.Therefore, Statement 3.2 is true! Statements of the form"If A,then B"in which condition A is impossible are called vacuous,and mathematicians consider such statements true because they have no exceptions. Recap This section introduced the notion of a theorem:a declarative statement about mathematics that has a proof.We discussed the absolute nature of the word true in mathematics.We discussed extensively the if-then and if-and-only-if forms of
14 Chapter 1 Fundamentals Here we list words that are alternatives to theorem and qffer a guide to their ~ usage. Result A modest, generic word for a theorem. There is an air of humility in calling your theorem merely a "result." Both important and unimportant theorems can be called results. Fact A very minor theorem. The statement "6 + 3 = 9" is a fact. Proposition A minor theorem. A proposition is more important or more general than a fact but not as prestigious as a theorem. Lemma A theorem whose main purpose is to help prove another, more important theorem. Some theorems have complicated proofs. Often one can break the job of proving a complicated theorem down into smaller parts. The lemmas are the parts, or tools, used to build the more complicated proof. Corollary A result with a short proof whose main step is the use of another, previously proved theorem. Claim Similar to lemma. A claim is a theorem whose statement usually appears inside the proof of a theorem. The purpose of a claim is to help organize key steps in a proof. Also, the statement of a claim may involve terms that make sense only in the context of the proof. Vacuous Truth What are we to think of an if-then statement in which the hypothesis is impossib1l'T Consider the following: Statement 3.2 (Vacuous) If an integer is both a perfect square and prime, then it is negative. Is this statement true or false? The statement is not nonsense. The terms perfect square (see Exercise 2.6), prime, and negative properly apply to integers. We might be tempted to say that the statement is false because square numbers and prime numbers cannot be negative. However, for a statement of the form "If A, then B" to be declared false, we need to find an instance in which clause A is true and clause B is false. In the case of Statement 3.2, condition A is impossible; there are no numbers that are both a perfect square and prime. So we can never find an integer that renders condition A true and condition B false. Therefore, Statement 3.2 is true! Statements of the form "If A, then B" in which condition A is impossible are called vacuous, and mathematicians consider such statements true because they have no exceptions. Recap This section introduced the notion of a theorem: a declarative statement about mathematics that has a proof. We discussed the absolute nature of the word true in mathematics. We discussed extensively the if-then and if-and-only-if forms of
Section 3 Theorem 15 theorems,as well as alternative language to express such results.We clarified the way in which mathematicians use the words and,or,and not.We presented a number of synonyms for theorem and explained their connotations.Finally,we discussed vacuous if-then statements and noted that mathematicians regard such statements as true. 3 Exercises 3.1.Each of the following statements can be recast in the if-then form.Please rewrite each of the following sentences in the form"If A,then B." a.The product of an odd integer and an even integer is even. b.The square of an odd integer is odd. c.The square of a prime number is not prime. d.The product of two negative integers is negative.(This,of course,is false.) The statement"If B,then 3.2.It is a common mistake to confuse the following two statements: A"is called the comverse a.If A,then B. of the statement"If A. b.If B,then A. then B." Find two conditions A and B such that statement (a)is true but statement (b)is false. 3.3.Consider the two statements a.If A,then B. b.(not A)or B. Under what circumstances are these statements true?When are they false? Explain why these statements are,in essence,identical. 3.4.Consider the two statements The statement"If (not B). then (not A)"is called the a.If A,then B. contrapositive of the b.If (not B),then (not A). statement"If A.then B." Under what circumstances are these statements true?When are they false? Explain why these statements are,in essence,identical. 3.5.Consider the two statements a.A iff B. b.(not A)iff (not B). Under what circumstances are these statements true?Under what circum- stances are they false?Explain why these statements are,in essence,identical. 3.6.Consider an equilateral triangle whose side lengths are a =b =c 1. Notice that in this case a2+b2c2.Explain why this is not a violation of the Pythagorean Theorem. A side of a spherical 3.7.Explain how to draw a triangle on the surface of a sphere that has three right triangle is an arc of a great angles.Do the legs and hypotenuse of such a right triangle satisfy the con- circle of the sphere on dition a2+b2=c2?Explain why this is not a violation of the Pythagorean which it is drawn. Theorem. 3.8.Consider the sentence"A line is the shortest distance between two points." Strictly speaking,this sentence is nonsense. Find two errors with this sentence and rewrite it properly 3.9.Consider the following rather grotesque claim:"If you pick a guinea pig up by its tail,then its eyes will pop out."Is this true? 3.10.What are the two plurals of the word lemma?
3 Exercises The statement "If B, then A" is called the converse of the statement "If A, then B.'' The statement "If (not B), then (not A)" is called the contrapositive of the statement "If A. then B." A side of a spherical triangle is an arc of a great circle of the sphere on which it is drawn. Section 3 Theorem 15 theorems, as well as alternative language to express such results. We clarified the way in which mathematicians use the words and, or, and not. We presented a number of synonyms for theorem and explained their connotations. Finally, we discussed vacuous if-then statements and noted that mathematicians regard such statements as true. 3.1. Each of the following statements can be recast in the if-then form. Please rewrite each of the following sentences in the form "If A, then B." a. The product of an odd integer and an even integer is even. b. The square of an odd integer is odd. c. The square of a prime number is not prime. d. The product of two negative integers is negative. (This, of course, is false.) 3.2. It is a common mistake to confuse the following two statements: a. If A, then B. b. If B, then A. Find two conditions A and B such that statement (a) is true but statement (b) is false. 3.3. Consider the two statements a. If A, then B. b. (not A) or B. Under what circumstances are these statements true? When are they false? Explain why these statements are, in essence, identical. 3.4. Consider the two statements a. If A, then B. b. If (not B), then (not A). Under what circumstances are these statements true? When are they false? Explain why these statements are, in essence, identical. 3.5. Consider the two statements a. A iff B. b. (not A) iff (not B). Under what circumstances are these statements true? Under what circumstances are they false? Explain why these statements are, in essence, identical. 3.6. Consider an equilateral triangle whose side lengths are a = b = c = 1. Notice that in this case a2 + b2 =1= c2 . Explain why this is not a violation of the Pythagorean Theorem. 3. 7. Explain how to draw a triangle on the surface of a sphere that has three right angles. Do the legs and hypotenuse of such a right triangle satisfy the condition a2 + b2 = c2? Explain why this is not a violation of the Pythagorean Theorem. 3.8. Consider the sentence "A line is the shortest distance between two points." Strictly speaking, this sentence is nonsense. Find two errors with this sentence and rewrite it properly. 3.9. Consider the following rather grotesque claim: "If you pick a guinea pig up by its tail, then its eyes will pop out." Is this true? 3.10. What are the two plurals of the word lemma?
16 Chapter 1 Fundamentals 4 Proof We create mathematical concepts via definitions.We then posit assertions about mathematical notions,and then we try to prove our ideas are correct. What is a proof? In science,truth is borne out through experimentation.In law,truth is ascer- tained by a trial and decided by a judge and/or jury.In sports,the truth is the ruling of referees to the best of their ability.In mathematics,we have proof. Truth in mathematics is not demonstrated through experimentation.This is not to say that experimentation is irrelevant for mathematics-quite the contrary! Trying out ideas and examples helps us to formulate statements we believe to be true (conjectures);we then try to prove these statements (thereby converting conjectures to theorems). For example,recall the statement "All prime numbers are odd."If we start listing the prime numbers from 3,we find hundreds and thousands of prime num- bers,and they are all odd!Does this mean all prime numbers are odd?Of course not!We simply missed the number 2. Let us consider a far less obvious example Conjecture 4.1 (Goldbach)Every even integer greater than two is the sum of two primes. Let's see that this statement is true for the first few even numbers.We have 4=2+26=3+3 8=3+510=3+7 12=5+714=7+7 16=11+518=11+7. One could write a computer program to verify that the first few billion even numbers Mathspeak! (starting with 4)are each the sum of two primes.Does this imply Goldbach's A proof is often called an Conjecture is true?No!The numerical evidence makes the conjecture believable, argumenr.In standard but it does not prove that it is true.To date,no proof has been found for Goldbach's English.the word Conjecture,so we simply do not know whether it is true or false. argument carries a A proof is an essay that incontrovertibly shows that a statement is true.Math- connotation of ematical proofs are highly structured and are written in a rather stylized manner. disagreement or controversy.No such Certain key phrases and logical constructions appear frequently in proofs.In this negative connotation and subsequent sections,we show how proofs are written. should be associated with a The theorems we prove in this section are all rather simple.Indeed,you won't mathematical argument. learn any facts about numbers you probably didn't already know quite well.The Indeed.mathematicians point in this section is not to learn new information about numbers;the point is to are honored when their proofs are called"beautiful learn how to write proofs.So without further ado,let's start writing proofs! arguments." We prove the following: Proposition 4.2 The sum of two even integers is even. I will write the proof here in full,and then we will discuss how this proof was created.In this proof,I have numbered each sentence so we can examine the proof piece by piece.Normally we would write this short proof out in a single paragraph and not number the sentences
16 Chapter 1 Fundamentals 4 Proof We create mathematical concepts via definitions. We then posit assertions about mathematical notions, and then we try to prove our ideas are correct. What is a proof? In science, truth is borne out through experimentation. In law, truth is ascertained by a trial and decided by a judge and/or jury. In sports, the truth is the ruling of referees to the best of their ability. In mathematics, we have proof. Truth in mathematics is not demonstrated through experimentation. This is not to say that experimentation is irrelevant for mathematics-quite the contrary! Trying out ideas and examples helps us to formulate statements we believe to be true (conjectures); we then try to prove these statements (thereby converting conjectures to theorems). For example, recall the statement "All prime numbers are odd." If we start listing the prime numbers from 3, we find hundreds and thousands of prime numbers, and they are all odd! Does this mean all prime numbers are odd? Of course not! We simply missed the number 2. Let us consider a far less obvious example. Conjecture 4.1 (Goldbach) Every even integer greater than two is the sum of two primes. Mathspeak! A proof o!ten called an arg!mielli< ln ·aandard English. the vmrd argument carries a connotation of disagreement or controversy< 01o such negative connotation should be c1~sociated with a mathematical argument. Indeed. mathematicians are honored when their proofs arc called "beautiful arguments.·· Let's see that this statement is true for the first few even numbers. We have 4=2+2 12 = 5 + 7 6=3+3 14 = 7 + 7 8=3+5 16 = 11 + 5 10 = 3 + 7 18 = 11 + 7. ..... One could write a computer program to verify that the first few billion even numbers (starting with 4) are each the sum of two primes. Does this imply Goldbach's Conjecture is true? No! The numerical evidence makes the conjecture believable, but it does not prove that it is true. To date, no proof has been found for Goldbach's Conjecture, so we simply do not know whether it is true or false. A proof is an essay that incontrovertibly shows that a statement is true. Mathematical proofs are highly structured and are written in a rather stylized manner. Certain key phrases and logical constructions appear frequently in proofs. In this and subsequent sections, we show how proofs are written. The theorems we prove in this section are all rather simple. Indeed, you won't learn any facts about numbers you probably didn't already know quite well. The point in this section is not to learn new information about numbers; the point is to learn how to write proofs. So without further ado, let's start writing proofs! We prove the following: Proposition 4.2 The sum of two even integers is even. I will write the proof here in full, and then we will discuss how this proof was created. In this proof, I have numbered each sentence so we can examine the proof piece by piece. Normally we would write this short proof out in a single paragraph and not number the sentences
Section 4 Proof 17 Proof (of Proposition 4.2) 1.We show that if x and y are even integers,then x +y is an even integer. 2.Let x and y be even integers. 3.Since x is even,we know by Definition 2.I that x is divisible by 2 (i.e..2x). 4.Likewise,since y is even,21y. 5.Since 2x,we know,by Definition 2.2,that there is an integer a such that x=2a. 6.Likewise,since 2ly,there is an integer b such that y =2b 7.Observe that x y 2a +2b 2(a +b). 8.Therefore there is an integer c(namely,a+b)such that x y 2c. 9.Therefore (Definition 2.2)2(x+y). 10. Therefore (Definition 2.1)x +y is even Let us examine exactly how this proof was written. Convert the statement to The first step is to convert the statement of the proposition into the if-then if-then form. form. The statement reads,"The sum of two even integers is even." We convert the statement into if-then form as follows: "If x and y are even integers,then x+y is an even integer." Note that we introduced letters (x and y)to name the two even integers. These letters come in handy in the proof. Observe that the first sentence of the proof spells out the proposition in if-then form. Sentence 1 announces the structure of this proof.The hypothesis(the"if part)tells the reader that we will assume that x and y are even integers.and the conclusion (the"then"part)tells the reader that we are working to prove that x +y is even. Sentence 1 can be regarded as a preamble to the proof.The proof starts in earnest at sentence 2. Write the first and last The next step is to write the very beginning and the very end of the proof. sentences using the The hypothesis of sentence I tells us what to write next.It says."..ifx hypothesis and conclusion and y are even integers...,"so we simply write,"Letx and y be even integers." of the statement. (Sentence 2) Immediately after we write the first sentence,we write the very last sen- tence of the proof.The last sentence of the proof is a rewrite of the conclusion of the if-then form of the statement. "Therefore,x+y is even."(Sentence 10) The basic skeleton of the proof has been constructed.We know where we begin (x and y are even),and we know where we are heading (x +y is even). Unravel definitions. The next step is to unravel definitions.We do this at both ends of the proof. Sentence 2 tells us that x is even.What does this mean?To find out,we check (or we remember)the definition of the word even.(Take a quick look at Definition 2.1 on page 2.)It says that an integer is even provided it is divisible by 2.So we know that x is divisible by 2,and we can also write that as 2x: this gives sentence 3
Convert the statement to if-then form. Write the first and last sentences using the hypothesis and conclusion of the statement. Unravel definitions. Section 4 Proof 17 Proof (of Proposition 4.2) 1. We show that if x and y are even integers, then x + y is an even integer. 2. Let x and y be even integers. 3. Since x is even, we know by Definition 2.1 that x is divisible by 2 (i.e., 21x ). 4. Likewise, since y is even, 2jy. 5. Since 2jx, we know, by Definition 2.2, that there is an integer a such that x = 2a. 6. Likewise, since 2iy, there is an integer b such that y = 2b. 7. Observe that x + y = 2a + 2b = 2(a +b). 8. Therefore there is an integer c (namely, a+ b) such that x + y = 2c. 9. Therefore (Definition 2.2) 2i(x + y). 10. Therefore (Definition 2.1) x + y is even. • Let us examine exactly how this proof was written. The first step is to convert the statement of the proposition into the if-then form. The statement reads, "The sum of two even integers is even." We convert the statement into if-then form as follows: "If x and y are even integers, then x + y is an even integer." Note that we introduced letters (x andy) to name the two even integers. These letters come in handy in the proof. Observe that the first sentence of the proof spells out the proposition in if-then form. Sentence 1 announces the structure of this proof. The hypothesis (the "if" part) tells the reader that we will assume that x andy are even integers, and the conclusion (the "then" part) tells the reader that we are working to prove that x + y is even. Sentence 1 can be regarded as a preamble to the proof. The proof starts in earnest at sentence 2. The next step is to write the very beginning and the very end of the proof. The hypothesis of sentence 1 tells us what to write next. It says, '' ... if x andy are even integers ... ,"so we simply write, "Let x andy be even integers.'' (Sentence 2) Immediately after we write the first sentence, we write the very last sentence of the proof. The last sentence of the proof is a rewrite of the conclusion of the if-then form of the statement. "Therefore, x + y is even." (Sentence I 0) The basic skeleton of the proof has been constructed. We know where we begin (x andy are even), and we know where we are heading (x + y is even). The next step is to unravel definitions. We do this at both ends of the proof. Sentence 2 tells us that x is even. What does this mean? To find out, we check (or we remember) the definition of the word even. (Take a quick look at Definition 2.1 on page 2.) It says that an integer is even provided it is divisible by 2. So we know that x is divisible by 2, and we can also write that as 2ix; this gives sentence 3