MACM 101 Lecture 19: Lecture 19 Part 1_ Mathematical Induction II
34 views2 pages
21 Dec 2018
School
Department
Course
Professor
Document Summary
One of the axioms of positive integers is the principle of well ordering: Every non-empty subset of n contains the least element. Note that the sets of all integers, rational numbers, and real numbers do not have this property. Suppose that mathematical induction is not valid. Then there is a predicate p(n) such that p(1) is true, k ( p(k) p(k + 1)) is true, but there is n such that p(n) is false. Let t n be the set of all n such that p(n) is false. By the principle of well-ordering t contains the least element a. However, since p(a 1) p(a), we get a contradiction. Induction mechanism can be used to define things. To define a function f: n r we complete two steps: Inductive step: for all k define f(k + 1) as a function of f(k), or, more general, as a function of f(1), f(2), , f(k). Give a recursive definition of f(n) = 2n.
Get access
Grade+20% off
$8 USD/m$10 USD/m
Billed $96 USD annually
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
40 Verified Answers
Class+
$8 USD/m
Billed $96 USD annually
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
30 Verified Answers