Math 521 – 3/19 Mar 19, 2018 Shawn Math 521 No comments yet 5.3 Recursive Definitions and Structural Induction Mar 19, 2018 Shawn Math 240 No comments yet Math 521 – 3/16 Mar 18, 2018 Shawn Math 521 No comments yet Math 521 – 3/14 Mar 16, 2018 Shawn Math 521 No comments yet 5.2 Strong Induction and Well-Ordering Mar 14, 2018 Shawn Math 240 No comments yet 1 2 3 4 5
![Theorem 2.38 (Nested Intervals Theorem) • Statement ○ If {I_n } is a sequence of closed intervals in R s.t. I_n⊃I_(n+1),∀n∈N ○ Then ⋂24_(n=1)^∞▒I_n is nonempty • Intuition • Proof ○ Let I_n≔[a_n,b_n ] ○ Let E≔{a_n }_(n∈N § E is nonempty § E is bounded above by b_1 since b_1≥a_n,∀n∈N § So supE exists ○ Let x≔supE ○ For m,n∈N, a_n≤a_(m+n)≤b_(m+n)≤b_m § a_n≤b_m⇒x≤b_n,∀m∈N § x=supE⇒a_m≤x,∀m∈N ○ So, x∈[a_m,b_m ],∀m∈N ○ Therefore x∈⋂24_(n=1)^∞▒I_n Theorem 2.39 • Statement ○ Let k be a positive integer ○ If {I_n } is a sequence of k-cells s.t. I_n⊃I_(n+1),∀n∈N ○ Then ⋂24_(n=1)^∞▒I_n is nonempty • Proof ○ Let I_n consists of all points x ⃗=(x_1,x_2,…,x_k ) s.t. ○ a_(n,j)≤x_j≤b_(n,j), where 1≤j≤k,n=1,2,3,… ○ Let I_(n,j)=[a_(n,j),b_(n,j) ] ○ For each j, {I_(n,j) } satisfies the hypothesis of Theorem 2.38 ○ Therefore ∃x_j^∗∈⋂24_(n=1)^∞▒I_(n,j) , for 1≤j≤k ○ Let (x^∗ ) ⃗=(x_1^∗,x_2^∗,…,x_k^∗ ) ○ By construction, (x^∗ ) ⃗∈⋂24_(n=1)^∞▒I_n Theorem 2.40 • Statement ○ Every k-cell is compact • Proof ○ Let I={(x_1,x_2,…,x_k )∈Rk│a_j≤x_j≤b_j,1≤j≤k} be a k-cell ○ Let δ=√(∑_(j=1)^k▒(b_j−a_j )^2 ), then |x ⃗−y ⃗ |≤δ,∀x ⃗,y ⃗∈I ○ Suppose {G_α } is an open cover of I with no finite subcover ○ Build sequence {I_n } § Let c_j=(a_j+b_j)/2 § Consider intervals [a_j,c_j ] and [c_j,b_j ] § Those intervals describes 2^k k-cells Q_i whose union is I § Since the number of Q_i is finite, and {G_α } has no finite subcover § ∃Q_i not covered by a finite subcover of {G_α }; call this I_1 § Repeat this process on I_1 to obtain I_2,I_3,… § We can build a sequence {I_n } ○ {I_n } is a sequence of k-cells s.t. § I⊃I_1⊃I_2⊃… § I_n is not covered by any finite sub-collection of {G_α } § If x ⃗,y ⃗∈I_n, then |x ⃗−y ⃗ |≤δ/2^n ○ By Theorem 2.38, ∃x ⃗^∗∈I_n,∀n∈N ○ Then (x^∗ ) ⃗∈G_α, for some G_α § G_α is open § i.e. ∃r 0 s.t. |y ⃗−(x^∗ ) ⃗ | r⇒y ⃗∈G_α § By Archimedean Property, ∃n∈N s.t. δ/2^n r § In this case, I_n⊂G_α, which is impossible, since § I_n is not covered by any finite sub-collection of {G_α } § So no such open cover {G_α } exists ○ So every open cover of I have a finite subcover ○ Therefore I is compact](https://shawnzhong.com/wp-content/uploads/2018/04/img_5acaeec101efa.png)
![Strong Induction • To prove that P(n) is true for all positive integers n • where P(n) is a propositional function, complete two steps: • Basis Step ○ Verify that the proposition P(1) is true. • Inductive Step ○ Show the conditional statement § [P(1)∧P(2)∧…∧P(k)]→ P(k+1) ○ holds for all positive integers k. • Strong Induction is sometimes called ○ the second principle of mathematical induction ○ complete induction Proof using Strong Induction • Prove that every natural number n 7 can be written as 3p+5q • where p and q are natural numbers • Prove this result using strong induction • Basis Step ○ 8=3×1+5×1 • Inductive Step ○ Inductive hypothesis: The statement is true for any n for k≥n≥8 ○ In particular it is true for k+1−3 (assuming k+1−3≥8) ○ So k+1−3=3p+5q and so k+1=3(p+1)+5q • What happens if k+1=9 or k+1=10? ○ Add those cases into the basis step ○ 9=3×3+5×0 ○ 10=3×0+5×2 Which Form of Induction Should Be Used? • We can always use strong induction instead of mathematical induction. • But there is no reason to use it if it is simpler to use mathematical induction • In fact, the principles of mathematical induction, strong induction, and the well-ordering property are all equivalent. • Sometimes it is clear how to proceed using one of the three methods, but not the other two. Proof of the Fundamental Theorem of Arithmetic • Show that if n is an integer greater than 1 • Then n can be written as the product of primes. • Let P(n) be the proposition that n can be written as a product of primes. • Basis Step ○ P(2) is true since 2 itself is prime. • Inductive Step ○ The inductive hypothesis is P(j) is true for j∈Z with 2≤j≤k ○ To show that P(k+1) must be true under this assumption ○ Two cases need to be considered: ○ If k+1 is prime, then P(k+1) is true. ○ Otherwise, k+1 is composite ○ And it can be written as the product of two positive integers ○ a and b with 2≤a≤b≤k+1 ○ By inductive hypothesis a and b can be written as product of primes ○ Therefore k + 1 can also be written as the product of those primes. • Hence, every integer greater than 1 can be written as product of primes Well-Ordering Property • Well-ordering property ○ Every nonempty set of nonnegative integers has a least element. • The well-ordering property is one of the axioms of the positive integers • The well-ordering property can be used directly in proofs. • The well-ordering property can be generalized. • Definition: A set is well ordered if every subset has a least element. ○ N is well ordered under ≤. ○ The set of finite strings over an alphabet using lexicographic ordering is well ordered. Proof of The Division Algorithm • Use the well-ordering property to prove the division algorithm ○ If a is an integer and d is a positive integer, then ○ there are unique integers q and r with 0≤r d, such that ○ a=dq+4 • Let S be the set of nonnegative integers of the form a=dq, q∈Z. • The set is nonempty since −dq can be made as large as needed • By the well-ordering property, S has a least element r=a−dq_0 • The integer r is nonnegative. • It also must be the case that r d • If it were not, then there would be a smaller nonnegative element in S ○ a−d(q_0+1)=a−dq_0−d=r−d 0 • Therefore, there are integers q and r with 0≤r d](https://shawnzhong.com/wp-content/uploads/2018/03/img_5aa936280eb33.png)
