8 Chapter 1 Fundamentals 3 Theorem A theorem is a declarative statement about mathematics for which there is a proof. The notion of proof is the subject of the next section-indeed,it is a cen- tral theme of this book.Suffice it to say for now that a proof is an essay that incontrovertibly shows that a statement is true. In this section we focus on the notion of a theorem.Reiterating,a theorem is a declarative statement about mathematics for which there is a proof. What is a declarative statement?In everyday English we utter many types of sentences.Some sentences are questions:Where is the newspaper?Other sentences are commands:Come to a complete stop.And perhaps the most common sort of sentence is a declarative statement-a sentence that expresses an idea about how something is,such as:It's going to rain tomorrow or The Yankees won last night. Practitioners of every discipline make declarative statements about their sub- ject matter.The economist says,"If the supply of a commodity decreases,then its price will increase."The physicist asserts,"When an object is dropped near the surface of the earth,it accelerates at a rate of 9.8 meter/sec2. Mathematicians also make statements that we believe are true about mathe- matics.Such statements fall into three categories: Statements we know to be true because we can prove them-we call these theorems. Statements whose truth we cannot ascertain-we call these conjectures. Statements that are false-we call these mistakes! There is one more category of mathematical statements.Consider the sentence Please he sure to check your owu work【or "The square root of a triangle is a circle."Since the operation of extracting a square nonsensical sentences. root applies to numbers,not to geometric figures,the sentence doesn't make sense. This iype of mistake is all We therefore call such statements nonsense! too common.Think about cvery word and symbol you write.Ask yourself. The Nature of Truth what docs this term mean? Do the expressions on the To say that a statement is true asserts that the statement is correct and can be left and right sides of your trusted.However,the nature of truth is much stricter in mathematics than in any equations represent objects other discipline.For example,consider the following well-known meteorological of the same type? fact:"In July,the weather in Baltimore is hot and humid."Let me assure you,from personal experience,that this statement is true!Does this mean that every day in every July is hot and humid?No,of course not.It is not reasonable to expect such a rigid interpretation of a general statement about the weather. Consider the physicist's statement just presented:"When an object is dropped near the surface of the earth,it accelerates at a rate of 9.8 meter/sec2."This state- ment is also true and is expressed with greater precision than our assertion about the climate in Baltimore.But this physics"law"is not absolutely correct.First,the value 9.8 is an approximation.Second,the term near is vague.From a galactic per- spective,the moon is"near"the earth,but that is not the meaning of near that we in- tend.We can clarify near to mean"within 100 meters of the surface of the earth,"but this leaves us with a problem.Even at an altitude of 100 meters,gravity is slightly
8 Chapter 1 Fundamentals 3 inistake is all Think about this term mean? Do thl· .:xpressions on the left sides of your equar\nn< represent objects of tht: SMile type') Theorem A theorem is a declarative statement about mathematics for which there is a proof. The notion of proof is the subject of the next section-indeed, it is a central theme of this book. Suffice it to say for now that a proof is an essay that incontrovertibly shows that a statement is true. In this section we focus on the notion of a theorem. Reiterating, a theorem is a declarative statement about mathematics for which there is a proof. What is a declarative statement? In everyday English we utter many types of sentences. Some sentences are questions: Where is the newspaper? Other sentences are commands: Come to a complete stop. And perhaps the most common sort of sentence is a declarative statement-a sentence that expresses an idea about how something is, such as: It's going to rain tomorrow or The Yankees won last night. Practitioners of every discipline make declarative statements about their subject matter. The economist says, "If the supply of a commodity decreases, then its price will increase." The physicist asserts, "When an object is dropped near the surface of the earth, it accelerates at a rate of 9. 8 meter I sec2 ." Mathematicians also make statements that we believe are true about mathematics. Such statements fall into three categories: Statements we know to be true because we can prove them-we call these theorems. Statements whose truth we cannot ascertain-we call these conjectures. Statements that are false-we call these mistakes! There is one more category of mathematical statements. Consider the sentence "The square root of a triangle is a circle." Since the operation of extracting a square · root applies to numbers, not to geometric figures, the sentence doesn't make sense. We therefore call such statements nonsense! The Nature of Truth To say that a statement is true asserts that the statement is correct and can be trusted. However, the nature of truth is much stricter in mathematics than in any other discipline. For example, consider the following well-known meteorological fact: "In July, the weather in Baltimore is hot and humid." Let me assure you, from persona] experience, that this statement is true! Does this mean that every day in every July is hot and humid? No, of course not. It is not reasonable to expect such a rigid interpretation of a general statement about the weather. Consider the physicist's statement just presented: "When an object is dropped near the surface of the earth, it accelerates at a rate of 9.8 meterjsec2 ."This statement is also true and is expressed with greater precision than our assertion about the climate in Baltimore. But this physics "law" is not absolutely correct. First, the value 9.8 is an approximation. Second, the term near is vague. From a galactic perspective, the moon is "near" the earth, but that is not the meaning of near that we intend. We can clarify near to mean "within 100 meters of the surface of the earth," but this leaves us with a problem. Even at an altitude of 100 meters, gravity is slightly
Section 3 Theorem less than at the surface.Worse yet,gravity at the surface is not constant;the grav- itational pull at the top of Mount Everest is a bit smaller than the pull at sea level! Despite these various objections and qualifications,the claim that objects dropped near the surface of the earth accelerate at a rate of 9.8 meter/sec2 is true. As climatologists or physicists,we learn the limitations of our notion of truth. Most statements are limited in scope,and we learn that their truth is not meant to be considered absolute and universal. However,in mathematics the word true is meant to be considered absolute, unconditional,and without exception. Let us consider an example.Perhaps the most celebrated theorem in geometry is the following classical result of Pythagoras. Theorem 3.1 (Pythagorean)If a and b are the lengths of the legs of a right triangle and c is the length of the hypotenuse,then a2+b2=c2. The relation a2+b2=c2 holds for the legs and hypotenuse of every right triangle,absolutely and without exception!We know this because we can prove this theorem (more on proofs later). Is the Pythagorean Theorem really absolutely true?We might wonder:If we draw a right triangle on a piece of paper and measure the lengths of the sides down to a billionth of an inch,would we have exactly a2+b2=c2?Probably not, because a drawing of a right triangle is not a right triangle!A drawing is a helpful visual aid for understanding a mathematical concept,but a drawing is just ink on paper.A"real"right triangle exists only in our minds. On the other hand,consider the statement,"Prime numbers are odd."Is this statement true?No.The number 2 is prime but not odd.Therefore,the statement is false.We might like to say it is nearly true since all prime numbers except 2 are odd.Indeed,there are far more exceptions to the rule"July days in Baltimore are hot and humid"(a sentence regarded to be true)than there are to "Prime numbers are odd." Mathematicians have adopted the convention that a statement is called true provided it is absolutely true without exception.A statement that is not absolutely true in this strict way is called false. An engineer,a physicist,and a mathematician are taking a train ride through Scotland.They happen to notice some black sheep on a hillside. “Look,”shouts the engineer.“Sheep in this part of Scotland are black'" "Really,"retorts the physicist."You mustn't jump to conclusions.All we can say is that in this part of Scotland there are some black sheep." "Well,at least on one side,"mutters the mathematician. If-Then Mathematicians use the English language in a slightly different way than ordinary speakers.We give certain words special meanings that are different from that of standard usage.Mathematicians take standard English words and use them as
Theorem 3.1 b Section 3 Theorem 9 less than at the surface. Worse yet, gravity at the surface is not constant; the gravitational pull at the top of Mount Everest is a bit smaller than the pull at sea level! Despite these various objections and qualifications, the claim that objects dropped near the surface of the earth accelerate at a rate of 9. 8 meter I sec2 is true. As climatologists or physicists, we learn the limitations of our notion of truth. Most statements are limited in scope, and we learn that their truth is not meant to be considered absolute and universal. However, in mathematics the word true is meant to be considered absolute, unconditional, and without exception. Let us consider an example. Perhaps the most celebrated theorem in geometry is the following classical result of Pythagoras. (Pythagorean) If a and b are the lengths of the legs of a right triangle and c is the length of the hypotenuse, then The relation a2 + b2 = c2 holds for the legs and hypotenuse of every right triangle, absolutely and without exception! We know this because we can prove this theorem (more on proofs later). Is the Pythagorean Theorem really absolutely true? We might wonder: If we draw a right triangle on a piece of paper and measure the lengths of the sides down to a billionth of an inch, would we have exactly a2 + b2 = c2? Probably not, because a drawing of a right triangle is not a right triangle! A drawing is a helpful visual aid for understanding a mathematical concept, but a drawing is just ink on paper. A "real" right triangle exists only in our minds. On the other hand, consider the statement, "Prime numbers are odd." Is this statement true? No. The number 2 is prime but not odd. Therefore, the statement is false. We might like to say it is nearly true since all prime numbers except 2 are odd. Indeed, there are far more exceptions to the rule "July days in Baltimore are hot and humid" (a sentence regarded to be true) than there are to "Prime numbers are odd." Mathematicians have adopted the convention that a statement is called true provided it is absolutely true without exception. A statement that is not absolutely true in this strict way is called false. An engineer, a physicist, and a mathematician are taking a train ride through Scotland. They happen to notice some black sheep on a hillside. "Look," shouts the engineer. "Sheep in this part of Scotland are black!" "Really," retorts the physicist. "You mustn't jump to conclusions. All we can say is that in this part of Scotland there are some black sheep." "Well, at least on one side," mutters the mathematician. If-Then Mathematicians use the English language in a slightly different way than ordinary speakers. We give certain words special meanings that are different from that of standard usage. Mathematicians take standard English words and use them as
10 Chapter 1 Fundamentals Consider the mathematical technical terms.We give words such as set,group,and graph new meanings.We and the ordinary usage of also invent our own words,such as bijection and poset.(All these'words are defined the word prime.When an later in this book.) economist says that the prime interest rate is now Not only do mathematicians expropriate nouns and adjectives and give them 8.we are not upset that 8 new meanings,we also subtly change the meaning of common words,such as or, is not a prime number! for our own purposes.Although we may be guilty of fracturing standard usage, we are highly consistent in how we do it.I call such altered usage of standard English mathspeak,and the most important example of mathspeak is the if-then construction. In the statement"If A.then The vast majority of theorems can be expressed in the form"If A,then B." B."condition A is called For example,the theorem"The sum of two even integers is even"can be rephrased the加pothesis and "If x and y are even integers,then x+y is also even." condition B is called the In casual conversation,an if-then statement can have various interpretations. conelusion. For example,I might say to my daughter,"If you mow the lawn,then I will pay you $10."If she does the work,she will expect to be paid.She certainly wouldn't object if I gave her $10 when she didn't mow the lawn,but she wouldn't expect it. Only one consequence is promised. On the other hand,if I say to my son,"If you don't finish your lima beans, then you won't get dessert,"he understands that unless he finishes his vegetables, no sweets will follow.But he also understands that if he does finish his lima beans, then he will get dessert.In this case two consequences are promised:one in the event he finishes his lima beans and one in the event he doesn't. The mathematical use of if-then is akin to that of"If you mow the lawn,then I will pay you $10."The statement "If A,then B"means:Every time condition A is true,condition B must be true as well.Consider the sentence "If x and y are even,then x+y is even."All this sentence promises is that when x and y are both even,it must also be the case that x+y is even.(The sentence does not rule out the possibility ofx+y being even despite x or y not being even.Indeed,if x and y are both odd,we know that x +y is also even.) In the statement"If A,then B,"we might have condition A true or false,and we might have condition B true or false.Let us summarize this in a chart.If the statement"If A,then B"is true,we have the following. Condition A Condition B True True Possible True False Impossible False True Possible False False Possible All that is promised is that whenever A is true,B must be true as well.If A is not true,then no claim about B is asserted by "If A,then B." Here is an example.Imagine I am a politician running for office,and I announce in public,"If I am elected,then I will lower taxes."Under what circumstances would you call me a liar? Suppose I am elected and I lower taxes.Certainly you would not call me a liar-I kept my promise
10 Chapter 1 Fundamentals Con~ider the mathematical and the ordinary usage of the word prime. When an economist says that the prime interc~t rate is now 8C!r. we arc not upset that 8 is not a prime number! In the ~tatement "'If A. then B." condition ls called the h\porhe1is and condition B called the condu.IW/1. technical terms. We give words such as set, group, and graph ~ew meanings. We also invent our own words, such as bijection and poset. (All these~ words are defined later in this book.) Not only do mathematicians expropriate nouns and adjectives and give them new meanings, we also subtly change the meaning of common words, such as or, for our own purposes. Although we may be guilty of fracturing standard usage, we are highly consistent in how we do it. I call such altered usage of standard English mathspeak, and the most important example of mathspeak is the if-then construction. The vast majority of theorems can be expressed in the form "If A, then B." For example, the theorem "The sum of two even integers is even" can be rephrased "If x and y are even integers, then x + y is also even." In casual conversation, an if-then statement can have various interpretations. For example, I might say to my daughter, "If you mow the lawn, then I will pay you $1 0." If she does the work, she will expect to be paid. She certainly wouldn't object if I gave her $10 when she didn't mow the lawn, but she wouldn't expect it. Only one consequence is promised. On the other hand, if I say to my son, "If you don't finish your lima beans, then you won't get dessert," he understands that unless he finishes his vegetables, no sweets will follow. But he also understands that if he does finish his lima beans, then he will get dessert. In this case two consequences are promised: one in the event he finishes his lima beans and one in the event he doesn't. The mathematical use of if-then is akin to that of "If you mow the lawn, then I will pay you $1 0." The statement "If A, then B" means: Every time condition A is true, condition B must be true as well. Consider the sentence "If x and y are even, then x + y is even." All this sentence promises is that when x and y are both even, it must also be the case that x + y is even. (The sentence does not rule out , the possibility of x + y being even despite x or y not being even. Indeed, if x and y are both odd, we know that x + y is also even.) In the statement "If A, then B," we might have condition A true or false, and we might have condition B true or false. Let us summarize this in a chart. If the statement "If A, then B" is true, we have the following. Condition A Condition B True True Possible True False Impossible False True Possible False False Possible All that is promised is that whenever A is true, B must be true as well. If A is not true, then no claim about B is asserted by "If A, then B." Here is an example. Imagine I am a politician running for office, and I announce in public, "If I am elected, then I will lower taxes." Under what circumstances would you call me a liar? Suppose I am elected and I lower taxes. Certainly you would not call me a liar-I kept my promise
Section 3 Theorem 11 Suppose I am elected and I do not lower taxes.Now you have every right to call me a liar-I have broken my promise. Suppose I am not elected,but somehow (say,through active lobbying)I man- age to get taxes lowered.You certainly would not call me a liar-I have not broken my promise. Finally,suppose I am not elected and taxes are not lowered.Again,you would not accuse me of lying-I promised to lower taxes only if I were elected. The only circumstance under which "If (A)I am elected,then (B)I will lower taxes"is a lie is when A is true and B is false. In summary,the statement "If A,then B"promises that condition B is true whenever A is true but makes no claim about B when A is false. If-then statements pervade all of mathematics.It would be tiresome to use Alternative wordings for -TfA.then B.” the same phrases over and over in mathematical writing.Consequently,there is an assortment of alternative ways to express "If A,then B."All of the following express exactly the same statement as"If A,then B." ·“A implies B.”This can also be expressed in passive voice:“B is implied by A." ·“Whenever A,we have B."Also:“B,whenever A." ·“A is sufficient for B.”Also:“A is a sufficient condition for B. This is an example of mathspeak.The word sufficient can carry,in standard English,the connotation of being "just enough."No such connotation should be ascribed here.The meaning is "Once A is true,then B must be true as well." ·“In order for B to hold,.it is enough that we have A.” ·“B is necessary for A." This is another example of mathspeak.The way to understand this wording is as follows:In order for A to be true,it is necessarily the case that B is also true. ·“A,only if B" The meaning is that A can happen only if B happens as well. ·“A→B” The special arrow symbol is pronounced "implies." ·“B=A” The arrow-is pronounced"is implied by." If and Only If The vast majority of theorems are-or can readily be expressed-in the if-then form.Some theorems go one step further;they are of the form "If A then B,and if B then A."For example,we know the following is true: If an integer x is even,thenx+1 is odd,and ifx I is odd.thenx is even. This statement is verbose.There are concise ways to express statements of the form"A implies B and B implies A"in which we do not have to write out the conditions A and B twice each.The key phrase is if and only if.The statement
Alternative wordings for "If A. then B." Section 3 Theorem 11 Suppose I am elected and I do not lower taxes. Now you have every right to call me a liar-I have broken my promise. Suppose I am not elected, but somehow (say, through active lobbying) I manage to get taxes lowered. You certainly would not call me a liar-I have not broken my promise. Finally, suppose I am not elected and taxes are not lowered. Again, you would not accuse me of lying-I promised to lower taxes only if I were elected. The only circumstance under which "If (A) I am elected, then (B) I will lower taxes" is a lie is when A is true and B is false. In summary, the statement "If A, then B" promises that condition B is true whenever A is true but makes no claim about B when A is false. If-then statements pervade all of mathematics. It would be tiresome to use the same phrases over and over in mathematical writing. Consequently, there is an assortment of alternative ways to express "If A, then B." All of the following express exactly the same statement as "If A, then B." "A implies B." This can also be expressed in passive voice: "B is implied by A." "Whenever A, we have B." Also: "B, whenever A." "A is sufficient for B." Also: "A is a sufficient condition for B." This is an example of mathspeak. The word sufficient can carry, in standard English, the connotation of being "just enough." No such connotation should be ascribed here. The meaning is "Once A is true, then B must be true as well." "In order forB to hold, it is enough that we have A." "B is necessary for A." This is another example of mathspeak. The way to understand this wording is as follows: In order for A to be true, it is necessarily the case that B is also true. "A, only if B." The meaning is that A can happen only if B happens as well. "A====} B." The special arrow symbol ====} is pronounced "implies." "B-¢:== A". The arrow -¢:== is pronounced "is implied by." If and Only If The vast majority of theorems are-or can readily be expressed-in the if-then form. Some theorems go one step further; they are of the form "If A then B, and if B then A." For example, we know the following is true: If an integer x is even, then x + 1 is odd, and if x + 1 is odd, then x is even. This statement is verbose. There are concise ways to express statements of the form "A implies B and B implies A" in which we do not have to write out the conditions A and B twice each. The key phrase is if and only if. The statement
12 Chapter 1 Fundamentals “If A then B,and if B then A”can be rewritten as“A if and only if B.”The example just given is more comfortably written as follows: An integer x is even if and only ifx+I is odd. What does an if-and-only-if statement mean?Consider the statement"A if and only if B."Conditions A and B may each be either true or false,so there are four possibilities that we can summarize in a chart.If the statement"A if and only if B"is true,we have Condition A Condition B True True Possible True False Impossible False True Impossible False False Possible It is impossible for condition A to be true while B is false,because A=B. Likewise,it is impossible for condition B to be true while A is false,because B=A.Thus the two conditions A and B must be both true or both false. Let's revisit the example statement. An integer x is even if and only ifx+1 is odd. Condition A is"x is even"and condition B is"x I is odd."For some integers (e.g.,x =6),conditions A and B are both true (6 is even and 7 is odd),but for other integers (e.g.,x =9),both conditions A and B are false (9 is not even and 10 is not odd). Just as there are many ways to express an if-then statement,so too are there Alterative wordings for “A if and only if B." several ways to express an if-and-only-if statement. ·“A iff B.” Because the phrase"if and only if"occurs so frequently,the abbreviation"iff" is often used. ·“A is necessary and sufficient for B.” ·“A is equivalent to B”. The reason for the word equivalent is that condition A holds under exactly the same circumstances under which condition B holds. ·“A←→B” The symbol←→is an amalgamation of the symbols←=and→. And,Or,and Not Mathematicians use the words and,or,and not in very precise ways.The mathe- matical usage of and and not is essentially the same as that of standard English. The usage of or is more idiosyncratic. The statement"A and B"means that both statements A and B are true.For Mathematical use of and. example,"Every integer whose ones digit is 0 is divisible by 2 and by 5."This means that a number that ends in a zero,such as 230,is divisible both by 2 and by 5.The use of and can be summarized in the following chart
12 Chapter 1 Fundamentals Alternative wordings for "A if and only if B." Mathematical use of and. "If A then B, and if B then A" can be rewritten as "A if and only if B." The example just given is more comfortably written as follows: V An integer x is even if and only if x + 1 is odd. What does an if-and-only-if statement mean? Consider the statement "A if and only if B." Conditions A and B may each be either true or false, so there are four possibilities that we can summarize in a chart. If the statement "A if and only if B" is true, we have Condition A Condition B True True Possible True False Impossible False True Impossible False False Possible It is impossible for condition A to be true while B is false, because A ===} B. Likewise, it is impossible for condition B to be true while A is false, because B ===} A. Thus the two conditions A and B must be both true or both false. Let's revisit the example statement. An integer x is even if and only if x + 1 is odd. Condition A is "x is even" and condition B is "x + 1 is odd." For some integers (e.g., x = 6), conditions A and B are both true (6 is even and 7 is odd), but for other integers (e.g., x = 9), both conditions A and B are false (9 is not even and 10 is not odd). Just as there are many ways to express an if-then statement, so too are there several ways to express an if-and-only-if statement. "A iff B." Because the phrase "if and only if" occurs so frequently, the abbreviation "iff" is often used. "A is necessary and sufficient for B." "A is equivalent to B". The reason for the word equivalent is that condition A holds under exactly the same circumstances under which condition B holds. "A~B". The symbol ~ is an amalgamation of the symbols {:::= and ===}. And, Or, and Not Mathematicians use the words and, or, and not in very precise ways. The mathematical usage of and and not is essentially the same as that of standard English. The usage of or is more idiosyncratic. The statement "A and B" means that both statements A and B are true. For example, "Every integer whose ones digit is 0 is divisible by 2 and by 5." This means that a number that ends in a zero, such as 230, is divisible both by 2 and by 5. The use of and can be summarized in the following chart