need help with the practice sheet
Take-Home Quiz #14 Preparation for Exam 3 in MATH 263 Fall 2019 1. Fill in each blank to create a definition that is complete and correct. a. A relation ? from set A to set B is a function if __________________________________________________________________________________________________________________. b. A function ?: ? → ? is onto if __________________________________________________________________________________________________________________. c. A function ?: ? → ? is one-to-one if __________________________________________________________________________________________________________________. 2. Fill in the blank to create a definition that is complete and correct. a. A relation ℛ on a set A is reflexive if _______________________________________________________________________. b. A relation ℛ on a set A is symmetric if _________________________________________________________________________________________________________________. c. A relation ℛ on a set A is transitive if __________________________________________________________________________________________________________________. d. A relation ℛ on a set A is antisymmetric if __________________________________________________________________________________________________________________. e. A relation ℛ on a set A is a partial order on A if __________________________________________________________________________________________________________________. 3. Let ? = 1, 2, 3, 4 and ? = ?, ?, ?, ?, ? . a. Construct a function ?: ? → ? that is one-to-one, if possible. If it is not possible, explain why. b. Construct a function ?: ? → ? that is onto, if possible. If it is not possible, explain why. c. Construct a function ?: ? → ? that is not one-to-one, if possible. If it is not possible, explain why. 4. Let ?: ? → ? and ?: ? → ? be functions. TRUE or FALSE: a. The composition ? ∘ ? is a function. b. The composition ? ∘ ? is a function. c. If ? and ? are both onto, then ? ∘ ? is onto. d. If ? is one-to-one and ? is not one-to-one, the composed function ? ∘ ? might be one-to-one or might not be one-to-one it depends upon how ? and ? are defined. e. If ? is onto and ? is not onto, then the composed function ? ∘ ? might be onto or it might not be onto it depends upon how ? and ? are defined. 5. Let ?: ℤ → ℤ be defined as follows: ∀? ∈ ℤ, ? ? = 2? + 1. a. Find five distinct elements of ?. [Recall, function are relations with special properties, so their elements are ordered pairs.] b. If ? is a one-to-one function, prove it. If it is not one-to-one, give a counterexample to show it is not. c. If ? is onto, prove it. If it is not onto, give a counterexample to show it is not. 6. Let ? = ?, ?, ? be an alphabet and let set ? be the set of all strings of length less than 5 written over alphabet A. TRUE or FALSE: a. The empty string ? ∈ ?. b. The string ???? ∈ ?. c. The string ?????? ∈ ? . d. The string ?? is a substring of ???? in ?. e. The string ???? has exactly 9 different substrings. f. The string ?? is a substring of more than 18 distinct strings in ?. [Hint: Use counting rather than trying to list all elements of ? Think abo ho o can b ild ing in ? that have ?? as a factor. 7. Let the sequence ?? be defined by the following rule: For all integers ? 1, ?? = ? ∙ −1 ?. a. Find the first 6 terms of ?? . b. Circle exactly those statements below that are true for the sequence ?? : i. It is increasing. ii. It is decreasing. iii. It is non-increasing. iv. It is non-decreasing. c. Define a new sequence, ?? , as follows: ?? = ? ? = 1 i. Find the first 5 terms of ?? . ii. Circle exactly those statements below that are true for the sequence ?? : 1. It is not increasing. 2. It is not decreasing. 3. If n is even, ?? = ?! . 4. If n is odd, ?? = − ?! . d. Define a new sequence, ?? , as follows: ?? = ?? ? =1 i. Find the first 8 terms of ?? . ii. Circle exactly those statements below that are true for the sequence ?? : 1. It is not increasing. 2. It is not decreasing. 3. If n is even, ?? = ? 2 . 8. Let ? = 1, 2, 3, 4 . a. Construct a relation on ? that is not reflexive, not symmetric, and not transitive. b. Construct a relation on ? that is reflexive, symmetric and transitive and that is minimal in size. 9. Let ? = ?, ?, ? be an alphabet and say set ? is the set of all strings written over alphabet A. Define a sequence of strings from ?, call it ?? , as follows: ?0 = ??? and ?? = ??−1 ? ??−1 for all integers ? 1. a. Find ?1, ?2 and ?3. [For example, since ?0 = ??? we would have : ?1 = ???????.] b. Let ? ? be the following statement: For all ? 0, the string ?? in the sequence defined above has exactly 2? co ie of he le e a in i i. Prove the basis case in a proof by mathematical induction that the statement is true. ii. Write the (weak) induction hypothesis that you would need in a proof by mathematical induction that ? ? is true for all ? 0. iii. Can you see an argument that would work to prove that statement ? ? + 1 follows from the hypothesis that ? ? holds? 10. Let ? = ?, ?, ? be an alphabet and let set ? be the set of all strings written over alphabet A. Define a sequence of strings from ?, call it ?? , as follows: ?0 = ??? and ?? = ??−1 ? ??−1 for all integers ? 1. a. Find ?1, ?2 and ?3. [For example, since ?0 = ??? we would have : ?1 = ???????.] b. Let ? ? be the following statement: For all ? 0, the string ?? in the sequence defined above has exactly 2? co ie of he le e a in i i. Prove the basis case in a proof by mathematical induction that the statement is true. ii. Write the (weak) induction hypothesis that you would need in a proof by mathematical induction that ? ? is true for all ? 0. iii. Can you see an argument that would work to prove that statement ? ? + 1 follows from the hypothesis that ? ? holds? 11. Let the sequence ?? be defined by the following rule: For all integers ? 1, ?? = 3?. a. Find the first 4 terms of ?? . b. Circle exactly those statements below that are true for the sequence ?? : i. It is increasing. ii. It is decreasing. iii. It is non-increasing. iv. It is non-decreasing. v. ?? = 3??−1 for all integers ? 2. vi. ?? = 3 + ??−1 for all integers ? 2. c. Define a new sequence, ?? , as follows: ?? = ?? ? =1 i. Write the first 4 terms of ?? . [Hint: Leave the terms in expanded form.] ii. Let ? ? be the following statement: ?? = 3 1 + 2 + 3 + ⋯ + ? . Is this true for all ? 1? d. Define another new sequence, ?? , as follows: ?? = ? ? = 1 i. Write the first 4 terms of ?? . [Hint: Leave the terms in expanded form, i.e., show the factors of each ??.] ii. Let ? ? be the following statement: ?? = 3??! . Is this true for all ? 1? 12. Let ? = 1, 2, 3, 4 . Let ℛ = 1, 1 , 2, 2 , 2, 3 , 3, 2 , 3, 3 , 4, 4 . Is ℛ an equivalence relation on ?? If yes, construct the partition that ℛ induces on ?. If not, prove it is not by whatever means are required. 13. Consider the relation ℛ defined on ℤ by the rule ?, ? ∈ ℛ if and only if 4 | ? − ?. For each statement below, prove the statement if it is true. Give a counterexample if it is false. a. The relation ℛ is transitive. b. The relation ℛ is antisymmetric. 14. Let ? = 1, 2, 3, 4 . a. Construct an equivalence relation ℛ on ?. Give ℛ as a set of ordered pairs. b. Build the partition, call it ?, that the relation ℛ induces on the set ?. 15. Let ? = 1, 2, 3