Section 3.1: Direct Proof and Counterexample 1

1 Section : Direct Proof and Counterexample 1In this chapter, we introduce the notion of Proof in mathematics. Amathematical Proof is valid logical argument in mathematics whichshows that a given conclusion is true under the assumption that thepremisses are true. All major mathematical results you haveconsideredsince you first started studying mathematics have all been derived inthis way Pythagoras Theorem, Fundamental Theorem of Calculus,Fundamental Theorem of Algebra. Most of these proofs are long andcomplicated and will be considered in further mathematics this course, we shall consider more elementary proofs, mainly innumber theory, to start and strengthen our Proof writing stated at the beginning of the course, one of the most importantparts of mathematical Proof is knowing and understanding the defini-tions of what you are trying to prove things about. In this classandall future classesif you do not learn and understand the definitionsyou will notbe able to prove things.

2 Again, just for emphasis,defini-tions are one of the most important parts of a mathematicalproof. For a comparison, you wouldn t write an essay using wordswhich you don t know what they mean, so why would you try to writea mathematical Proof about things you don t understand?As remarked above, in this chapter, we shall be considering anumberof different proofs in number theory, so we start by writing formaldefinitions. Note that none of the definitions we are going to writedown are new to us, but the formal definition probably (Odd and Even Integers) An integernis even if andonly ifn= 2kfor some integerk. An integer is odd, if and only ifn= 2k+ 1 for some integerk. Symbolically: n Z, nis even k Z, n= 2k n Z, nis odd k Z, n= 2k+ 1 Definition (Prime Numbers) An integernis prime if and onlyifn >1 and for all positive integersrands, ifr s=n, thenr= 1ors= 1. An integernis composite if and only ifn >1 andn=r sfor some positive integersrandswithr6= 1 ands6= 1. In formalnotation:n is prime r Z+, s Z+, n=r s (s= 1 r= 1)12n is composite r Z+, s Z+,(n=r s) ((s6= 1) (r6= 1))Notice that definitions are statements quantified bicondi-tional statements.

3 We consider some examples of how to use the definitions we have given to answer the follow-ing:(i) Is 5 odd?5 is odd if 5 can be written in the form 2k+ 1 for someintegerk. Letk= 2. Then 5 = 2 2+1, and thus by definition5 is odd.(ii) Isnm mcomposite forn >2 andm > mis composite ifnm m=r sfor some integersr, s >1. However,nm m=m(n 1), so if we chooser=mands=n 1, thennm m=r swherer, s >1, so bydefinition,nm mis composite.(iii) Is 2r 6 + 10seven?2r 6+10sis even if 2r 6+10s2 kfor some integerk > we choosek= (r 2 + 5s)>0, thenr 2 + 5s >1 ands=n 1, thennm m=r swherer, s >1, so by definition,nm mis and Disproving Existential StatementsArguably, the easiest statements to prove are existential statements of the form x D, Q(x)or there existsxsuch thatQ(x) is true . In order to prove suchstatements, we need to exhibit an explicit example ofx DwithpropertyQ(or such thatQ(x) is true), or describe a set of directions inorder to find such anx. These methods of Proof are called constructiveproofs , as opposed to non constructive proofs where the existence ofan element is guaranteed by an axiom, or previous Proof , or isprovedby contradiction (by assuming such anxdoes not exist).

4 We illustratewith some that there exists two prime numbersnandmsuch thatn+m= 7 andm= 11, thenn+m= 11 + 7 = thatkis an even integer andk >2. Showthat there exists two prime numbersnandmsuch thatn+m=k.(Goldbachs conjecture!!!!)3 example that there exists real numbersaandbsuch that a+b= a+ 0 andb= 1. Then 0 + 1 = 1 = 0 + 1To disprove an existential statement, we need to prove its negation disprove an existential statement, we need to prove the universalstatement which is the negation of the existential statement. Since weshall be considering universal statements until later, we shall return tothis problem a Result by CounterexampleTo disprove a statement means to show it is false. One typicalway todisprove a universal statement is to present a Counterexample to whatis being posed. Formally:Result (Disproof by Counterexample ) To disprove the universalstatement x, P(x) Q(x)means to find anxsuch thatP(x) is true, butQ(x) is false. In notation, x, P(x) Q(x).We call such anxa the statement for all real numbersx, ifx2is rational , thenxis rational .

5 Disprove this statement by giving acounter the numberx= 2. Clearly 22= 2 is rational . However, 2 is not rational (we shall see why later in the course). Thus we haveexhibited a real numberxsuch thatx2is rational butxis not rational ,and thus the universal statement is not Universal StatementsSome of the most difficult statements to try to prove (and usually themost interesting and useful statements to try to prove) are universalconditional statements statements of the form x D, P(x) Q(x).The first obvious way to attempt to prove such a statement is thefollowing:Result (Method of Exhaustion) When the domainDofxis finite,to prove the universal statement x D, P(x) Q(x)4we can simply check for every element inDthat ifP(x) is true, thenso isQ(x).It seems that the method of exhaustion is the best way to proveuniver-sal conditionals. However, it has one huge obstacle - it onlyworks forfinite sets! (and in math, we are nearly always considering statementsabout infinite sized sets).

6 Therefore, in general, we would try a methodmore like the following:Result (Method of Direct Proof ) Suppose you are trying to provea universal conditional statement. Then we do the following:(i) Express the expression in logical form identify the hypoth-esis and conclusion of the statement and the domain.(ii) Start the Proof by supposing thatxis a particular, but arbi-trary chosen element ofDfor whichP(x) is true.(iii) Show that the conclusionQ(x) is true by using definitions, pre-viously established results, and the rules of logical last two steps are sometimes called The method of generalizingfrom the generic particular .We illustrate these Proof techniques with a couple of each integernwith 16n65,n2 n+11 is there are only finitely many integers with 16n65, we can usethe method of exhaustion. Specifically, we have12 1+11 = 11,22 2+11 = 13,32 3+11 = 17,42 4+11 = 23,52 5+11 = each case, the resulting number is prime, so the statementis remarked before, proving universal statements with infinite domainsis much more difficult.

7 The following three steps will usuallyhelp withsuch problems:(i) (Formal Restatement) Always try to write a formal restate-ment of the theorem you are trying to prove transform thestatement from informal language to logic.(ii) (Starting Point) Write down the things you are allowed toassume given the statement of the theorem to prove astatement x, P(x) Q(x), you need to supposexis an arbi-trary object which makesP(x) true, and then show thatQ(x)is true. For example , in the last problem we considered, thestarting point was the assumption thatxwas odd.(iii) (The Conclusion) Always keep in mind what the conclusionis going to be. Sometimes, it may even be useful to have itwritten somewhere on the page so you have a roadmap ofwhere you want to that for any integern, ifnis odd, thenn2is this case, we cannot use the method of exhaustion since there areinfinitely many different odd integers. Therefore, we must use themethod of generalizing from the generic particular.

8 Specifically, as-suming thatxis an odd integer, we need to show that without anyfurther assumptions thatx2is odd. We shall follow the steps above.(i) (Formal Restatement) x Z, xis odd x2is odd(ii) (Starting Point) Our only assumption is thatxis some oddinteger. This means thatx= 2k+ 1 for some integerk.(iii) (Body) Sincex= 2k+1, we havex2= (2k+1)2= 4k2+4k+1(using standard rules of algebra). Therefore, ifm= 2k2+k,thenx2= 2m+ 1.(iv) (Conclusion) Thereforex2is an odd Proof Techniques and Common MistakesA large portion of this class will be dedicated to learning how to writemathematical proofs of statements (we usually call such statements Theorems ). There is a widely accepted structure to such communi-cation, so we shall briefly outline how you should present your addition, there are some useful general steps and techniques whichshould always be taken when writing a Proof , and also some commonpitfalls which people fall into when writing proofs. First,when tryingto prove a theorem, the general structure should be as follows:(i) Write the word Theorem and then the statement you aretrying to prove after it.

9 (ii) On the next line write the word Proof - it is from this pointonward you shall start to write your Proof . Note that this sep-arates the statement of the theorem from the Proof , so shouldhelp avoid any confusion.(iii) Clearly mark the end of your Proof with QED , or some othersuch symbol (this is especially important if you are provingthree or four addition to the general structure given above, a good (andcorrect!) Proof will exhibit the following:(i) A Proof should always be self-contained, meaning all variableswhich are used in the Proof should be clearly defined(ii) You should write a Proof in complete sentences. This doesn tmean you should not use symbols or abbreviations in a Proof ,but rather they should be incorporated into your sentences(iii) Provide a reason for each assertion you make in you Proof oreach step you take - if you don t back up the steps you take,you could end up assuming something that isn t (iv) Use typical buzzwords between statements to make the ar-gument in your Proof more clear.)

10 For example , if one state-ment is a consequence of the previous, we could use the word therefore , or it follows that with a brief reason why thesecond statement follows from the first at the end of the sen-tence. When introducing new variables, we use the word let ( letxbe an even integer).As usual, there are certain mistakes which beginners (and indeed ex-perts) make when writing proofs. Some of the more common onesyoushould watch out for are the following:(i) Trying to prove a universal statement through examples: re-member, just because a statement holds for a small number ofexamples, does not mean it holds for all examples!(ii) Using the same variable to represent more than one thing(iii) Jumping to a conclusion asserting the truth of a statementwithout giving a reason(iv) Begging the question assuming what you are trying toprove(v) Misuse of the word if if can sometimes be used insteadof the word because , so a statement which is meant to be anassertion can turn out to be conditions because the word if is used instead of illustrate with a formal the statement The difference of any two oddintegers is even Theorem difference of any two odd integers is even or x Z, y Z, xis odd yis odd x yis (arbitrary but particular) odd there exists an integerksuch thatx= 2k+ 1 and an integermsuch thaty= 2m+ 1.