Introduction to Mathematical Analysis I - 3rd Edition

15 (b) f (A\B) =f (A)\ f (B) for A,B⊂X. 1.2.5 Prove part (ii) of Theorem 1.2.2. 1.2.6 Prove the remaining parts of Theorem 1.2.3. 1.2.7 Prove the remaining parts of Theorem 1.2.4. 1.2.8 Prove the remaining parts of Theorem 1.2.5. 1.2.9 Prove that the union of two finite sets is finite. Hint: it is easier to show when the sets are disjoint. 1.3 The Natural Numbers and Mathematical Induction We will assume familiarity with the set Nof natural numbers, with the usual arithmetic operations of addition and multiplication onN, and with the notion of what it means for one natural number to be less than another. In addition, we will also assume the following property of the natural numbers. Well-Ordering Property of the Natural Numbers: If Ais a nonempty subset of N, then there exists an element ℓ ∈Asuch that ℓ ≤x for all x ∈A. To paraphrase the previous property, every nonempty subset of positive integers has a smallest element. The principle of mathematical induction is a useful tool for proving facts about sequences. Theorem 1.3.1 — Principle of Mathematical Induction. For each natural number n∈N, suppose that P(n) denotes a proposition which is either true or false. Let A={n∈N: P(n) is true}. Suppose the following conditions hold: (i) 1∈A. (ii) For eachk ∈N, if k ∈A, then k+1∈A. Then A=N. Proof: Suppose conditions (i) and (ii) hold. Assume, by way of contradiction, that A̸=N. Set B=N\A, that is, B={n ∈N: P(n) is false}. Then B is a nonempty subset of N. By the WellOrdering Property of the natural numbers, there exists a smallest element ℓ ∈B. By condition (i), 1̸∈B. Hence, ℓ ≥2. It follows that k =ℓ−1 is a natural number. Since k < ℓ, thenk̸ ∈Band, hence, we have that P(k) is true. By condition (ii), we obtain that P(k+1) is true. But k+1=ℓ, andP(ℓ) is false, since ℓ ∈B. This is a contradiction, so the conclusion follows. □ The principle says that, given a list of propositions P(n), one for each n∈N, if P(1) is true and, moreover, P(k+1) is true whenever P(k) is true, then all propositions are true. We will refer to this principle as mathematical induction or simply induction. Condition (i) above is called the base case and condition (ii) the inductive step. When proving (ii), the statement P(k) is called the inductive hypothesis. ■ Example 1.3.1 Prove using induction that 1+2+· · ·+n= n(n+1) 2 for all n∈N.

RkJQdWJsaXNoZXIy NTc4NTAz