This is discrete math 1. a) Write a recursive function that translates a non-neg

Question

This is discrete math

    1. a) Write a recursive function that translates a non-negative number into its equivalent binary string.                                   

b) Give a recursive definition of a function annoy, which takes a string and a number as its two inputs and outputs a string. The output string is formed by repeating the input string the input number of times. For examples: annoy(bon, 2) = bonbon; annoy(my!, 3) = my!my!my!.     

c) Bonus: Prove the equivalence of well-ordering and the principle of mathematical induction. No partial credit will be given.

Hint: Prove well-ordering principle using mathematical induction and Prove mathematical induction using well-ordering.                                  

Explanation / Answer

c)Well-ordering principle: Every nonempty subset T of N has a least element. That is, there is an m T such that m n for all n T. Intutively clear as it may seem at the first glance, this principle turns out to be logically equivalent to the mathematical induction, the fifth axiom of Peano, which is quite surprising. Theorem 1. The mathematical induction is logically equivalent to the well-ordering principle. Proof. Part I. We show the well-ordering principle implies the mathematical induction. Let S N be such that 1 S and k S implies k 0 S. We want to establish that S = N by the well-ordering principle. Suppose NS is not empty. Then by the well-ordering principle there is a least element m NS. Since 1 S we know 1 / NS. Therefore m 6= 1 and so by one of the homework 2 problems there is some q N such that m = q 0 = q + 1, which implies q < m by the definition of <. We conclude that q S; or else we would have q N S and so m would not be the least element of N S, which is absurd. However, since S has the property that k S implies k 0 S, we conclude that m = q 0 S because q S. This contradicts m N S. The contradiction establishes that N S is empty. Hence S = N. Part II. We show the mathematical induction implies the well-ordering principle. Let S(n) be the statement: Any set of natural numbers containing a natural number n has a least element. Consider the set E = {m N : S(m) is true}. 1 E because 1 is the least element of N (why?). We next show m E implies m0 E. Now m E means if X is a subset of N containing a natural number m, then X has a least element. From this we want to establish m0 E. So let C be any subset of N containing a natural number m0 . If C has no element < m0 , then m0 is the least element of C and we are done. Otherwise, we can now suppose there is a natural number y C such that y < m0 . In particular, y m because by one of the homework 3 problems we know there is no natural number strictly between m and m0 . Therefore, C now has an element y m, so that the induction hypothesis given in the preceding paragraph implies that C has a least element. In any event, we have proven C has a least element, so that m0 E. Hence, the mathematical induction implies E = N. 1 2 In summary, the mathematical induction implies that the statement S(n) is true for all n N. To establish the well-ordering principle, let T N be a nonempty set. There is some m T because T is nonempty, so that T contains a natural number m, which is just m itself. Then T has a least element because the statement S(m) is true by the preceding paragraph.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.