Homework 8 Math 3200 Fall 2024 PDF

Math 3200: Introduction to Higher Mathematics Fall 2024, Dr. Klipper Homework 8: Due Monday, October 28, 2024 Please hand in all required problems. (All problem numbers refer to the Taylor textbook.) Honors students must also hand in at least one challenge problem....

Math 3200: Introduction to Higher Mathematics Fall 2024, Dr. Klipper Homework 8: Due Monday, October 28, 2024 Please hand in all required problems. (All problem numbers refer to the Taylor textbook.) Honors students must also hand in at least one challenge problem. Any other challenge problems count for extra credit. You do not have to rewrite the problem statement in your responses. After graded work is returned to students, you may take up to two class days to submit a revision of one problem to earn points back. See syllabus for details. SUGGESTIONS: The denitions in this week's content are more complex than before. Review several logic strategies from Unit 1 and Unit 2, such as: Negation rules (to help with counterexamples), proof strategies for ∀ quantiers, Proofs using P ⇒Q assumptions, witness variable usage with ∃ quantiers Practice writing claims in symbols and making outlines of assumptions and goals. Recommended practice problems (ungraded): 5.4, 5.6, 5.7, 5.9, 5.10, 5.15, 5.17, 5.18 Required problems: 1. In this problem, our relation's domain and range elements have dierent types! Let A = {0, 1, 2} and B = {∅, {1}, {1, 2}, {1, 2, 3}}. Dene the relation E from A to B as follows: for any x∈A and any Y ∈ B, xEY ⇔ x∈Y (a) List the elements of E. (Write E explicitly as a set of ordered pairs.) SUGGESTION: For each Y ∈ B, determine all the x's in A related to it, where (x, Y ) ∈ E. (b) List the elements of the inverse relation E −1. RECALL: E −1 is the relation from B to A where Y E −1 x ⇔ xEY (c) Determine the domain dom(E) and range ran(E) of the relation E. 1 2. Dene the relation R on Q as the following set: R = {(x, y) ∈ Q2 | x ≤ y} \ {(0, 0), (0, 1)} In other words, xRy means x≤y but (x, y) ̸= (0, 0) and (x, y) ̸= (0, 1). Give counterexamples to show the following. Briey explain your answers. (a) R is not reexive. (b) R is not symmetric. (c) R is not transitive. HINTS: Although  ≤ is reexive and transitive, how does removing two pairs change this? Also keep in mind that x, y, z can be rational, not just integers. 3. In each part, give a specic relation R on A = {1, 2, 3, 4} with the listed properties. (Write R as a set of pairs, or dene R with a property, e.g.  (x R y) ⇔ (x = y).) Give short arguments or examples to explain why R has the needed properties. (a) R is reexive and transitive but is not symmetric. (b) R is symmetric but is neither reexive nor transitive. 4. Let P be the set of non-constant polynomials with real coecients. Dene the relation R on P by: for all p, q ∈ P , pRq ⇔ p(x) and q(x) share some common root (In symbols: pRq means ∃c ∈ R, (p(c) = 0) ∧ (q(c) = 0).) For instance, (x2 − x) R (x2 − 1) since both polynomials vanish at x = 1. However, ̸ (x2 − 4) (x + 3) R since their sets of roots, {−3} and {−2, 2}, are disjoint. (a) Prove or disprove: R is reexive on P. (HINT: Write  p R p in symbols.) (b) Prove or disprove: R is symmetric on P. (c) Prove or disprove: R is transitive on P. 5. Dene the relation M on R by: for all x, y ∈ R, xM y ⇔ 4(y − x) ∈ Z (Note 4(y − x) might not be even in cases where x ̸∈ Z or y ̸∈ Z.) MAJOR SUGGESTION: Rewrite the denition of xM y to get an equation where y is solved in terms of x. Problem 5 is continued on the next page. 2  (a) Determine the rst four values of y where 0.3 M y and y > 0.3. Briey explain your work. (b) Prove that M is an equivalence relation on R. (Following the major suggestion may help make this work much easier!) 6. Dene the relation ∼ on Q× (NONZERO rationals) by: for all a, b ∈ Q× , a a∼b ⇔ ∃m ∈ Z, = 2m b For instance, 4∼2 since 4/2 = 2 = 21 with 1 ∈ Z. Similarly, (−2/3) ∼ (−16/3) since (−2/3)/(−16/3) = 1/8 = 2−3 with −3 ∈ Z. Prove that ∼ is an equivalence relation on Q×. 7. In this exercise, we practice converting between an equivalence relation on A (contain- ing pairs in A × A) and its collection of equivalence classes (subsets of A). (a) Let R be the following equivalence relation on A = {1, 2, 3, 4}. (You do not have to check that it's an equivalence relation.) R = {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (2, 4), (3, 3), (4, 1), (4, 2), (4, 4)} Determine the members of each of the equivalence classes , , ,. (b) Suppose an equivalence relation S, also on A = {1, 2, 3, 4}, has the classes = = {1, 4} = = {2, 3} List all of the ordered pairs in the relation S. 8. Dene the relation P on R as follows: For all a, x ∈ R, aP x ⇔ (a − 1)2 = (x − 1)2 You may take for granted that P is an equivalence relation. (a) For each x ∈ R, determine the members of its equivalence class [x]. Namely, solve for all real numbers a (in terms of x) satisfying a P x. (b) We could also describe P using level sets of the function f (x) = (x − 1)2 : aP x means (a, f (a)), (x, f (x)) have the same height on y = f (x). Draw the graph of y = f (x), and indicate the class on your graph. (c) Which equivalence class only has a single member? Briey justify your answer using either part (a) or part (b). 3 Challenge problems: A. In this problem, we introduce a new denition: Denition: Let A,B ,C be sets, R be a relation from A to B , and S be a relation from B to C. The composite relation S ◦ R is the relation1 from A to C dened as follows for all x ∈ A and z ∈ C : x (S ◦ R) z ⇔ ∃y ∈ B, (x R y) and (y S z) Informally, (x, z) is in the composite when there is some bridge y connecting x to z in two steps, so that x R y S z. As a demonstration with A = B = C = R, suppose we dene xRy ⇔ y = ±x xSy ⇔ y = x2 Then (4, 16) ∈ (S ◦ R) because of 4 R 4 S 16 (or also 4 R − 4 S 16). (a) Let A = N and let R be the < relation on N. Thus, (m, n) ∈ R means m < n. For instance, both (1, 10) and (1, 2) are in R. However, briey explain the following: (1, 10) ∈ (R ◦ R) (1, 2) ̸∈ (R ◦ R) (b) In general, let R be an arbitrary relation on a nonempty set A. Prove: If R is transitive, then (R ◦ R) ⊆ R. 1 This is a special case of function composition, which we will study later 4