# Proof Must Have

• Published on
20-Jan-2016

• View
45

0

Embed Size (px)

DESCRIPTION

Proof Must Have. Statement of what is to be proven. "Proof:" to indicate where the proof starts Clear indication of flow Clear indication of reason for each step Careful notation, completeness and order Clear indication of the conclusion I suggest pencil and good erasure when needed. - PowerPoint PPT Presentation

Transcript

• Proof Must HaveStatement of what is to be proven."Proof:" to indicate where the proof startsClear indication of flowClear indication of reason for each stepCareful notation, completeness and orderClear indication of the conclusionI suggest pencil and good erasure when needed

• Number Theory - Ch 3 DefinitionsZ --- integers Q - rational numbers (quotients of integers)rQ a,bZ, (r = a/b) ^ (b 0)Irrational = not rationalR --- real numberssuperscript of + --- positive portion onlysuperscript of - --- negative portion onlyother superscripts: Zeven, Zodd , Q>5

"closure" of these sets for an operationZ closed under what operations?

• Integer Definitionseven integer n Zeven k Z, n = 2k odd integer n Zodd k Z, n = 2k+1 prime integer (Z>1) n Zprime r,sZ+, (n=r*s) (r=1)v(s=1)composite integer (Z>1) n Zcomposite r,sZ+, n=r*s ^(r1)^(s1)

• Constructive Proof of ExistenceIf we want to prove:nZeven, p,q, r,sZprime n = p+q ^ n = r+s^pr^ ps^ qr^ qslet n=10 n Zeven by definition of even Let p = 5 and the q = 5p,q Zprime by definition of prime 10 = 5+5Let r = 3 and s = 7r,s Zprime by definition of prime 10 = 3+7and all of the inequalities hold

• Methods of Proving Universally Quantified StatementsMethod of Exhaustionprove for each and every member of the domainrZ+ where 23
• Examples of Generalizing from the "Generic Particular"The product of any two odd integers is also odd.m,n Z, [(m Zodd n Zodd ) m*n Zodd ]

The product of any two rationals is also rational.m,nQ, m*n Q

• Disproof by Counter Example rZ, r2Z+ rZ+Counter Example: r2= 9 ^ r = -3 r2Z+ since 9 Z+ so the antecedent is truebut rZ+ since -3Z+ so the consequent is falsethis means the implication is false for r = -3 so this is a valid counter exampleWhen a counter example is given you must always justify that it is a valid counter example by showing the algebra (or other interpretation needed) to support your claim

• Division definitionsd | n kZ, n = d*kn is divisible by dn is a multiple of dd is a divisor of nd divides nstandard factored formn = p1e1 * p2e2 * p3e3 * * pkek

• Proof using the ContrapositiveFor all positive integers, if n does not divide a number to which d is a factor, then n can not divide d.

• Proof using the ContrapositiveFor all positive integers, if n does not divide a number to which d is a factor, then n can not divide d.

n,d,cZ+, ndc nd

• Proof using the ContrapositiveFor all positive integers, if n does not divide a number to which d is a factor, then n can not divide d.

n,d,cZ+, ndc nd n,d,cZ+, n|d n|dcproof:

• more integer definitionsdiv and mod operatorsn div d --- integer quotient forn mod d --- integer remainder for(n div d = q) ^ (n mod d = r) n = d*q+r where n Z0, d Z+, r Z, q Z, 0 r
• Quotient Remainder TheoremnZ dZ+ q,rZ (n=dq+r) ^ (0 r < d)Proving definition of equiv in a mod by using the quotient remainder theoremThis means prove that if [m d n], then [d|(n-m)]where m,nZ and dZ+

• Proofs using this definitionmZ+ a,bZ a m b k Z a=b+km

mZ+ a,b,c,dZ a m b ^ c m d a+c m b+d

• Proof by Division into CasesnZ 3n n2 3 1

• Floor and Ceiling Definitionsn is the floor of x where xR ^ n Z x = n n x < n+1n is the ceiling of x where xR ^ n Z x = n n-1 < x n

• Floor/Ceiling Proofsx,yR x+y = x + y

xR yZ x+y = x +y

• Proof by Division into Cases (again)

The floor of (n/2) is eithera) n/2 when n is even or b) (n-1)/2 when n is odd

• Prime Factored Formn = p1e1 * p2e2 * p3e3 * * pkek Unique Factorization Theorem (Theorem 3.3.3)given any integer n>1kZ, p1,p2,pkZprime, e1,e2,ekZ+, where the ps are distinct and any other expression of n is identical to this except maybe in the order of the factorsStandard Factored Formpi < pi+1mZ,8*7*6*5*4*3*2*m=17*16*15*14*13*12*11*10Does 17|m ??

• Steps Toward Proving the Unique Factorization TheoremEvery integer greater than or equal to 2 has at least one prime that divides it

For all integers greater than 1, if a|b, then a (b+1)

There are an infinite number of primes

• Using the Unique Prime Factorization TheoremProve that aZ+ 3 | a2 3 | aProve that the

Prove: aZ+qZprime q|a2 q |a

• Summary of Proof MethodsConstructive Proof of Existence

Proof by ExhaustionProof by Generalizing from the Generic ParticularProof by ContrapositionProof by ContradictionProof by Division into Cases

• Errors in ProofsArguing from example for universal proof.Misuse of VariablesJumping to the Conclusion (missing steps)Begging the QuestionUsing "if" about something that is known