“mcs”-2018/6/6一13：43一page5-#13 What is a Proof? 1.1 Propositions Definition.A proposition is a statement (communication)that is either true or false. For example,both of the following statements are propositions.The first is true, and the second is false. Proposition 1.1.1.2+3 =5. Proposition 1.1.2./+3. Being true or false doesn't sound like much of a limitation,but it does exclude statements such as "Wherefore art thou Romeo?"and "Give me an A!"It also ex- cludes statements whose truth varies with circumstance such as,"It's five o'clock," or“the stock market will rise tomorrow.” Unfortunately it is not always easy to decide if a claimed proposition is true or false: Claim 1.1.3.For every nonnegative integer n the value of n2 +n+41 is prime. (A prime is an integer greater than 1 that is not divisible by any other integer greater than 1.For example,2,3,5,7,11,are the first five primes.)Let's try some numerical experimentation to check this proposition.Let pm)=n2+n+41.1 (1.1) We begin with p(0)=41,which is prime;then p(1)=43,p(2)=47,p(3)=53,.,p(20)=461 are each prime.Hmmm,starts to look like a plausible claim.In fact we can keep checking through n =39 and confirm that p(39)=1601 is prime. But p(40)=402+40+4141.41,which is not prime.So Claim 1.1.3 is false since it's not true that p(n)is prime for all nonnegative integers n.In fact,it's not hard to show that no polynomial with integer coefficients can map all IThe symbol::=means"equal by definition."It's always ok simply to write"="instead of::= but reminding the reader that an equality holds by definition can be helpful.“mcs” — 2018/6/6 — 13:43 — page 5 — #13 1 What is a Proof? 1.1 Propositions Definition. A proposition is a statement (communication) that is either true or false. For example, both of the following statements are propositions. The first is true, and the second is false. Proposition 1.1.1. 2 + 3 = 5. Proposition 1.1.2. 1 + 1 = 3. Being true or false doesn’t sound like much of a limitation, but it does exclude statements such as “Wherefore art thou Romeo?” and “Give me an A!” It also ex￾cludes statements whose truth varies with circumstance such as, “It’s five o’clock,” or “the stock market will rise tomorrow.” Unfortunately it is not always easy to decide if a claimed proposition is true or false: Claim 1.1.3. For every nonnegative integer n the value of n 2 C n C 41 is prime. (A prime is an integer greater than 1 that is not divisible by any other integer greater than 1. For example, 2, 3, 5, 7, 11, are the first five primes.) Let’s try some numerical experimentation to check this proposition. Let p.n/ WWD n 2 C n C 41:1 (1.1) We begin with p.0/ D 41, which is prime; then p.1/ D 43; p.2/ D 47; p.3/ D 53; : : : ; p.20/ D 461 are each prime. Hmmm, starts to look like a plausible claim. In fact we can keep checking through n D 39 and confirm that p.39/ D 1601 is prime. But p.40/ D 402 C 40 C 41 D 41
41, which is not prime. So Claim 1.1.3 is false since it’s not true that p.n/ is prime for all nonnegative integers n. In fact, it’s not hard to show that no polynomial with integer coefficients can map all 1The symbol WWD means “equal by definition.” It’s always ok simply to write “=” instead of WWD, but reminding the reader that an equality holds by definition can be helpful