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