Mathematical Statements and Proofs Lecture 4 (Handout)

MOE Advanced Level Higher 3 (H3) Math Mathematical Proofs and Reasoning Lecture 4 1 / 42

Telegram Chat https://t.me/+My2fLlPuAUxlYjY1 2 / 42

Content 1 Proving Existential Statements: Constructive vs Nonconstructive 2 Pigeon Hole Principle 3 Continuous Functions 3 / 42

Proving Existential Statements Proving ∃x ∈ D, P(x) is true. There are two approaches. 1 Constructive proof (Direct proof) Find or construct a specific example for x in the set D that satisfies the statement P . 2 Non-constructive proof (Indirect proof) When specific examples are not easy or not possible. When the specific x satisfying P depends on more (unknown) conditions on P . 4 / 42

Example: Constructive There exists a quadratic polynomial that passes through the points (−3, 2) and (1, 2). A quadratic polynomial has the expression ax2 + bx + c for some real numbers a, b, c. Since it passes through the points (−3, 2) and (1, 2), have a(−3)2 + b(−3) + c = 2 a(1)2 + b(1) + c = 2 or 9a − 3b + c = 2 a + b + c = 2 This is a simultaneous equations. Solving the system (exercise), we have a = 2 3 − 1 3 c, b = 4 3 − 2 3 c, for any choice of real number c ̸= 2(why?). Choosing c = −1, the quadratic polynomial is x2 + 2x − 1. 5 / 42

Remark There are infinitely many examples, pick one to answer the existential question. Make sure that the chosen example satisfies the condition. Indeed, (−3)2 + 2(−3) − 1 = 9− 6 − 1 = 2 (1)2 + 2(1)− 1 = 1 + 2− 1 = 2 Why c ̸= 2? 6 / 42

Discussion Generalize the previous problem: (i) Given two points (x1, y1) and (x2, y2), is it possible to find a quadratic polynomial that passes through the points (x1, y1) and (x2, y2)? (ii) What are the necessary and sufficient conditions on the points (x1, y1) and (x2, y2) for the existence of such a quadratic polynomial? (iii) If a quadratic polynomial exists, is it unique? If not, explain why. 7 / 42

Discussion Prove that for any 2 rational numbers p and q such that p < q, there is a rational number r such that p < r < q. Let r = p + q 2 . First show that p < r < q. r = p + q 2 = p + q − p 2 > pand r = p + q 2 = q − q − p 2 < qsince p + q 2 > 0. Next, show that r is rational. By closure property of addition in Q (lecture 2), p + q is also a rational number. By closure property of multiplication in Q, (p + q) × 1 2 = p + q 2 = r is also a rational number. Remarks. This shows that the set of rational numbers is a dense subset of the set of reals. 9 / 42

Definition Definition A function f from a set D to a set Y is a rule that assigns a unique value f (x) in Y to each x ∈ D. D Y f a b c d... w x y z ... 10 / 42

Nomenclature Definition A function f from a set D to a set Y is a rule that assigns a unique value f (x) in Y to each x ∈ D. (i) D is called the domain, Y is called the codomain of the function. (ii) For every a ∈ D, there must be a unique y ∈ Y such that f (a) =y. f (a) =y is called the image of a. (iii) The range R = {f (x) | x ∈ D} of f is a subset of the codomain R ⊆ Y that contains all the images of f . (iv) If the domain of f is not explicitly stated or restricted by context, the domain is assumed to be the largest set of real x values for which the formula gives real y values. This is called the natural domain of f . 11 / 42