Example: dental hygienist

Introduction to mathematical arguments

Introduction to mathematical arguments (background handout for courses requiring proofs)by Michael HutchingsA mathematicalproofis an argument which convinces other people thatsomething is true. Math isn t a court of law, so a preponderance of theevidence or beyond any reasonable doubt isn t good enough. In principlewe try to prove things beyond any doubt at all although in real life peoplemake mistakes, and total rigor can be impractical for large projects. (Thereare also some subtleties in the foundations of mathematics, such as G odel stheorem, but never mind.)Anyway, there is a certain vocabulary and grammar that underlies allmathematical proofs. The vocabulary includes logical words such as or , if , etc. These words have very precise meanings in mathematics which candiffer slightly from everyday usage. By grammar , I mean that there arecertain common-sense principles of logic, or proof techniques, which you canuse to start with statements which you know and deduce statements whichyou didn t know notes give a very basic Introduction to the above.

prove any type of statement. This chart does not include uniqueness proofs and proof by induction, which are explained in §3.3 and §4. Apendix A reviews some terminology from set theory which we will use and gives some more (not terribly interesting) examples of proofs. 1

Tags:

  Proof

Information

Domain:

Source:

Link to this page:

Please notify us if you found a problem with this document:

Other abuse

Transcription of Introduction to mathematical arguments

1 Introduction to mathematical arguments (background handout for courses requiring proofs)by Michael HutchingsA mathematicalproofis an argument which convinces other people thatsomething is true. Math isn t a court of law, so a preponderance of theevidence or beyond any reasonable doubt isn t good enough. In principlewe try to prove things beyond any doubt at all although in real life peoplemake mistakes, and total rigor can be impractical for large projects. (Thereare also some subtleties in the foundations of mathematics, such as G odel stheorem, but never mind.)Anyway, there is a certain vocabulary and grammar that underlies allmathematical proofs. The vocabulary includes logical words such as or , if , etc. These words have very precise meanings in mathematics which candiffer slightly from everyday usage. By grammar , I mean that there arecertain common-sense principles of logic, or proof techniques, which you canuse to start with statements which you know and deduce statements whichyou didn t know notes give a very basic Introduction to the above.

2 One could easilywrite a whole book on this topic; see for exampleHow to read and do proofs:an Introduction to mathematical thought processby D. Solow). There aremany more beautiful examples of proofs that I would like to show you; butthis might then turn into an Introduction to all the math I know. So I havetried to keep this Introduction brief and I hope it will be a useful 1 we introduce the basic vocabulary for mathematical 2 and 3 we introduce the basic principles for proving statements. Weprovide a handy chart which summarizes the meaning and basic ways toprove any type of statement. This chart does not include uniqueness proofsand proof by induction, which are explained in and 4. Apendix Areviews some terminology from set theory which we will use and gives somemore (not terribly interesting) examples of following was selected and cobbled together from piles of old notes,so it is a bit uneven; and the figures are missing, sorry. If you find anymistakes or have any suggestions for improvement please let me Statements and logical operationsIn mathematics, we studystatements, sentences that are either true or falsebut not both.

3 For example,6 is an even integerand4 is an odd integerare statements. (The first one is true, and the second is false.) We will useletters such as p and q to denote Logical operationsIn arithmetic, we can combine or modify numbers with operations such as + , , etc. Likewise, in logic, we have certain operations for combiningor modifying statements; some of these operations are and , or , not , and if.. then . In mathematics, these words have precise meanings, which aregiven below. In some cases, the mathematical meanings of these words differslightly from, or are more precise than, common English simplest logical operation is not . Ifpis a statement, then notp is defined to be true, whenpis false; false, whenpis statement notp is called two statements, then the statement pandq is definedto be true, whenpandqare both true; false, whenpis false orqis false or bothpandqare two statements, then the statement porq is defined tobe true, whenpis true orqis true or bothpandqare true; false, when bothpandqare English, sometimes porq means thatpis true orqis true, but notboth.

4 However, this isneverthe case in mathematics. We always allow forthe possibility that bothpandqare true, unless we explicitly say .. statements, then the statement ifpthenq isdefined to be true, whenpandqare both true orpis false; false, whenpis true andqis sometimes abbreviate the statement ifpthenq by pimpliesq , or p q . Ifpis false, then we say thatp qisvacuously and only statements, then the statement pif and onlyifq is defined to be true, whenpandqare both true or both false; false, when one ofp, qis true and the other is symbol for if and only if is . Whenp qis true, we QuantifiersConsider the sentencexis is not what we have been calling a statement; we can t say whether itis true or false, because we don t know are three basic ways to turn this sentence into a statement. Thefirst is to say exactly whatxis:3 Whenx= 6,xis following are two more interesting ways of turning the sentence into astatement:For every integerx,xis exists an integerxsuch thatxis phrases for every and there exists are an example of the use of quantifiers, we can give precise definitions ofthe terms even and odd.

5 Integerxisevenif there exists an integerysuch thatx= 2y.(The if in this definition is really an if and only if . Mathematicalliterature tends to misuse the word if this way when making definitions,and we will do this too.) integerxisoddif there exists an integerysuch thatx= 2y+ for will call a sentence such as xis even that depends on the value ofxa statement aboutx . We can denote thesentence xis even by P(x) ; thenP(5) is the statement 5 is even ,P(72)is the statement 72 is even , and so a set andP(x) is a statement aboutx, then the notation( x S)P(x)means thatP(x) is true for everyxin the setS. (See Appendix A for adiscussion of sets.) The notation( x S)P(x)means that there exists at least one elementxofSfor whichP(x) is denote the set of integers by Z . Using the above notation, thedefinition of xis even given previously becomes( y Z)x= course, this is still a statement aboutx. We can turn this into a statementby using a quantifier to say whatxis.

6 For instance, the statement( x Z) ( y Z)x= 2ysays that all integers are even. (This is false.) The statement( x Z) ( y Z)x= 2ysays that there exists at least one even integer. (This is true.)The sentence( y Z)x= 2y+ 1means thatxis odd. The statement( x Z)(( y Z)x= 2y)or(( y Z)x= 2y+ 1)says that every integer is even or quantifiers is very important; changing the order of thequantifiers in a statement will often change the meaning of a statement. Forexample, the statement( x Z) ( y Z)x < yis true. However the statement( y Z) ( x Z)x < yis How to negate often need to find the negations of complicated statements. How doyoudenythat something is true? The rules for doing this are given in theright-hand column of Table example, suppose we want to negate the statement( x Z)(( y Z)x= 3y+ 1) (( y Z)x2= 3y+ 1).First, we put a not in front of it:not ( x Z)(( y Z)x= 3y+ 1) (( y Z)x2= 3y+ 1).5 Using the rule for negating a for every statement, we get( x Z) not((( y Z)x= 3y+ 1) (( y Z)x2= 3y+ 1)).

7 Using the rule for negating an if.. then statement, we get( x Z)(( y Z)x= 3y+ 1)and not ( y Z)x2= 3y+ the rule for negating a there exists statement, we get( x Z)(( y Z)x= 3y+ 1)and ( y Z)x26= 3y+ How to prove thingsLet us start with a silly example. Consider the following conversation be-tween mathematicians Alpha and :I ve just discovered a new mathematical truth!Beta:Oh really? What s that?Alpha:For every integerx, ifxis even, thenx2is :Hmm.. are you sure that this is true?Alpha:Well, isn t it obvious?Beta:No, not to :OK, I ll tell you what. You give me any integerx, and I ll show you thatthe sentence ifxis even, thenx2is even is (eyes narrowing to slits): All right, how aboutx= :That s easy. 17 is not even, so the statement if 17 is even, then 172iseven is vacuously true. Give me a harder :OK, tryx= :Since 62 is even, I guess I have to show you that 622is :That s (counting on her fingers furiously): According to my calculations, 622=3844, and 3844 is clearly even.

8 Beta:Hold on. It s not so clear to me that 3844 is even. The definition saysthat 3844 is even if there exists an integerysuch that 3844 = 2y. If youwant to go around saying that 3844 is even, you have toproducean integerythat :How abouty= :Yes, you have a point there. So you ve shown that the sentence ifxiseven, thenx2is even is true whenx= 17 and whenx= 62. But there arebillionsof integers thatxcould be. How do you know you can do this forevery one?Alpha:Letxbe any :Which integer?Alpha:Any integer at all. It doesn t matter which one. I m going to show you,using only the fact thatxis an integer and nothing else, that ifxis eventhenx2is :All right.. go :So supposexis :But what if it isn t?Alpha:Ifxisn t even, then the statement ifxis even, thenx2is even isvacuously true. The only time I have anything to worry about is :OK, so what do you do whenxis even?Alpha:By the definition of even , we know that there exists at least one integerysuch thatx= :Only one, :I think so.

9 Anyway, letybe an integer such thatx= 2y. Squaring bothsides of this equation, we getx2= 4y2. Now to prove thatx2is even, I haveto exhibit an integer, twice which :Doesn t 2y2work?7 Alpha:Yes, it does. So we re :And since you haven t said anything about whatxis, except that it s aninteger, you know that this will work for any integer at :OK, I understand :So here s another mathematical truth. For every integerx, ifxis odd,thenx2is..This dialogue illustrates several important points. First, aproofis anexplanation which convinces other mathematicians that a statement is good proof also helps themunderstandwhy it is true. The dialogue alsoillustrates several of the basic techniques for proving that statements 1 summarizes just about everything you need to know about lists the basic ways to prove, use, and negate every type of statement. Inboxes with multiple items, the first item listed is the one most commonlyused. Don t worry if some of the entries in the table appear cryptic at first;they will make sense after you have seen some our first example, we will illustrate how to prove for every statementsand if.

10 Then statements, and how to use there exists statements. Theseideas have already been introduced in the a proof that for every integerx, ifxis odd, thenx+ 1 is a for every statement, so the first thing we do is writeLetxbe any have to show, using only the fact thatxis an integer, that ifxis oddthenx+ 1 is even. So we writeSupposexis must somehow use this assumption to deduce thatx+ 1 is even. Recallthat the statement xis odd means that there exists an integerysuch thatx= 2y+ 1. Also, we can give this integeryany name we like; so to avoidconfusion below, we are going to call it w . So to use the assumption thatxis odd, we write8 StatementWays to Prove itWays to Use itHow to Negate it Prove thatpis true. pis Assumepis false, and Ifpis false, you havenotpderive a Provep, and pis true.(notp) or (notq)then proveq. qis true. Assumepis false, and Ifp randq rdeduce thatqis Assumeqis false, and Ifpis false, then(notp) and (notq)deduce thatpis true. Prove thatpis true.


Related search queries