RI Chapter 1 Methods of Proof

RAFFLES INSTITUTION H3 Mathematics (9820) ________________ Chapter 1: Methods of Proof Page 1 of 24 Chapter 1: Methods of Proof SYLLABUS INCLUDES Knowledge of terms such as ‘Definition’ and ‘Theorem’ Conditional Statements (such as ‘if P then Q’ and ‘P if and only if Q’) Necessary and sufficient conditions Existential and universal quantifiers (such as ‘there exists’, ‘for each’ and ‘for all’) Logical connectives (such as ‘and’, ‘or’, ‘not’, ‘implies’) Converse, inverse, contrapositive and negation of statements Set notation and language Use of direct proof, proof by mathematical induction, disproof by counterexample, proof by contradiction, proof of existence, proof by construction, pigeonhole princip le, symmetry principle CONTENT 1 Introduction 1.1 Elements of logic 1.1.1 Statements 1.1.2 Quantifiers 1.1.3 Conditional Statements 2 Methods of Proof 2.1 Direct Proofs 2.2 Proof by Contradiction 2.3 Use of Contrapositives 2.4 Use of Counter Examples 2.5 Mathematical Induction 2.5.1 Conjectures 2.5.2 Weak Induction 2.5.3 Strong Induction 2.6 Method of Infinite Descent 2.7 Pigeonhole Principle

Raffles Institution H3 Mathematics _________________________________________________________________________________________ ________________ Chapter 1 : Methods of Proof Page 2 of 24 1 Introduction So far, most of the Mathematics formally taught in secondary school has been “computational”. The objective of this Chapter is to help us now think about Mathematics a little more carefully or rigorously. We will emphasize the role of “definitions” and the demonstration of “proof”. Many of the ideas discussed here will be re -visited in later Chapters. Anyone who has studied both elementary Euclidean geome try and an experimental science like Physics, should be aware of the very different ways in which the propositions of these two disciplines are established. In the Physical sciences, the propositions or “laws” are accepted because they are confirmed by observation. Mathematics is often used though to “describe” these laws but it is the acceptance of these Mathematical descriptions by empirical observations. In Euclidean geometry, propositions or “theorems” are accepted because they are deduced by means of a logical proof from previously established truths. It was the ancient Greeks who first used this axiom atic method to give geometry a formal structure. This method consists of accepting without proof certain propositions, known as axioms. Then all the other statements (called theorems) of the system are derived from the axioms by principles of logic. The treatment here is brief and is mainly intended to give a “flavor” of things to come. At the end of this Chapter we will focus on “induction” which is an important and useful “method of proof” to establish the truth of statements involving subsets of the positive integers. 1.1 Elements of Logic 1.1.1 Statements A statement, or a proposition, is a sentence which is either true or false, but not both. Example 1 The following are examples of statements. 1. Everyone in this room is taller than 160cm. 2. 2 0e  3. There are integers x and y such that 2 3 0.xy+= 4. If x and y are any odd integers, then xy is an odd integer. 5. For all real values x, 2 0x  and sin 1x . Given a statement p, ~p (read as “not p”) is the negation of the statement p. For example, consider the following statement, p:“I have a headache.” The statement, “I do not have a headache” is the negation of p. The negation of statement 2. 2:0qe  is 2~ : 0qe = What is the negation of 3, 4 and 5 ? Negation of 3 : There are no integers x and y such that 2 3 0.xy+= Negation of 4 : There exist some x and y which are odd integers, and xy is an even integer. Negation of 5 : There exists a real values x, such that either 2 0x  or sin 1x .

Raffles Institution H 3 Mathematics _________________________________________________________________________________________ ________________ Chapter 1 : Methods of Proof Page 3 of 24 1.1.2 Quantifiers Let us introduce the logical quantifiers: which symbolizes "for all" , and which symbolizes "there exists" Example 2 Forms of quantified statements as typically seen in Mathematical statements. 1. 2, 0.xx   • For any real number x, 2 0x  . 2. 2, 2.xx  = • There exists a real number such that 2 2x = . Negation of Statements Negating statements with quantifiers can be tricky. Before we try negating the 2 statements above in Example 2, let us look at a more concrete example. Example 3 Now, consider the following statement, p: The height of everyone in the room is at least 150cm. For this statement to be true, the height of every single person in the room must be at least 150. For it to be false, it suffices for there are to be at least one person in the room whose height is less than 150cm. p:  Alan, Beth,... ,Zach , 150iih   ; ~p:  Alan, Beth,... ,Zach , 150iih   In other words p: ( )( ) ( )( )~ , ,~x p x x p x   Now let us look back at Example 2 and try to negate the two statements. 1. p : ~ p : 2. q : ~ q : Write the negation of the following statements as a simple exercise. 1. , 2 3.xx  −   2. 2,if is odd, then is odd.x x x 2, 0.xx   2, 2.xx  =

Raffles Institution H 3 Mathematics _________________________________________________________________________________________ ________________ Chapter 1 : Methods of Proof Page 4 of 24 1.1.3 Conditional Statements An important connective is the conditional statement pq The conditional statement p implies q ( pq ) means that if p is a true statement then q is also a true statement. pq fails to hold only when p is true and q is false ! If p is false then the statement pq is said to be vacuously true. Example 4 p: x > 2 q: x > 1 Any number which is greater than 2 is also greater than 1, so pq . Note: (i) pq does not require that p is true or p is false, but only that if p is true then q is true. Comments (ii) pq does not mean that qp (converse) or ~~pq . (iii) It does, however follow that ~~qp (contrapositive). There are several ways in which pq can be expressed in Mathematics. We say p is the hypothesis of the conditional statement and q is the conclusion. (i) “if p then q” (ii) “p only if q” (iii) “p is a sufficient condition for q” (iv) “q is a necessary condition for p” p is a necessary and sufficient condition for q means p if and only if q (p iff q) or symbolically, pq . Example 5 (a) p: y = x2; q: d 2d y xx = Which of the following statements are correct? A p is a necessary condition for q. B p is a necessary and sufficient condition for q. C (~p) is a sufficient condition for (~q). D (~q) is a necessary condition for (~p). E q is a necessary condition for p. A statement and its contrapositive are either both true or both false, i.e. pq and ~~qp are equivalent statements.

Raffles Institution H 3 Mathematics _________________________________________________________________________________________ ________________ Chapter 1 : Methods of Proof Page 5 of 24 (b) : ( 1)( 2) 0; : 2p x x q x− −   Which of the following statements are correct? A qp B ~~pq C q is a sufficient condition for p. D q is a necessary condition for p. E p is a necessary condition for q. (c) Insert the correct conditional symbol between the given statements. That is, , or p q p q p q   (i) 2: 4; : 2p x q x== (ii) 2 : 0; : 11 xp q xx −