Expert answer:Induction and Relations and Functions, math homewo

Answer & Explanation:I have a worksheet on Induction and Relations and functions that I could use some help with.  I need to have explanations for the answers/ work shown, please.  I want to compare to what I think is correct.  For question #16 & #17 I have included the pages it refers to.ThanksPatrickmath301week2homework.docxmath301week2homework.pdfweek_2_ordered_fields.pdf
math301week2homework.docx

math301week2homework.pdf

week_2_ordered_fields.pdf

Unformatted Attachment Preview

MATH 301 Week 2 Homework, Spring, 2016. Due Sunday, February 14.
NAME: _____________________________________
Instructions: You are encouraged to discuss homework, use online resources, and to seek help from the instructor when you
need it, but your submitted write-up of your work must be your own, in your own words.
Induction
#1. Prove by induction that 9 + 12 + 15 + … + 3(n + 2) = 3n(n + 5)/2 for all n  N.
Page 1 of 8
#2. Prove the summation formula for the following particular finite geometric series. (Do not prove the
general formula for a geometric progression and then substitute the value for the ratio. Instead, prove this
particular formula shown below.)
Prove by induction that
4
1 2
1
1
+ 4( ) + ⋯+ 4( ) = 1 −
5
5
5
5
for every n  N.
#3. Prove by induction that (1.01)n  1 + (0.01)n for every n  N .
Page 2 of 8
Relations and Functions
#4. Find an example of a relation that is reflexive and symmetric, but not transitive. (Note that you can
just list an appropriate set of ordered pairs.)
#5. Let S be a set. Let A and B be subsets of S. Let R be the relation given by A R B iff A  B.
That is, A is related to B iff A is a subset of B.
State which of the three properties (reflexive, symmetric, and transitive) apply. If a property does not
hold, provide a counterexample.
#6. State the range of each function f: R → R. (no work required to be shown)
#6(a) f(x) = 3 sin(4x)
#6(b) f(x) = 2(x + 1)2 + 5
#7. Let X = {1, 2, 3, 4, 5} and Y = {4, 5 ,6, 7}. Define a function f: X → Y as follows:
f (1) = 7, f (2) = 6, f (3) = 4, f (4) = 5, f (5) = 6.
For each statement, is it True or False? (no explanation required)
________ (a) ∃ x ∈ X such that f (x) = 3x.
________ (b) ∃ y ∈ Y such that ∀ x ∈ X, f (x) = y.
________ (c) ∀x ∈ X, ∃ y ∈ Y such that f (x) = y.
________ (d) ∀y ∈ Y, ∃ x ∈ X such that f (x) = y.
________ (e) f is injective.
________ (f) f is surjective.
#8. Let f: A → B. Recall that f is injective iff  a, a’  A, if f(a) = f(a’), then a = a’.
Write the contrapositive of the quantified if-then statement (the statement in bold).
Page 3 of 8
#9. Claim: The function f: R → R defined by f(x) = 7 − 4x is injective. Consider the following “proofs” of
the claim. INSTRUCTIONS: Critique each proof (A, B, C, D, E). For each proof, is it a valid argument
establishing the claim or not? What are the flaws, if any?
Proof A:
Let a = 0 and a’ = 1.
f(a) = 7 and f(a’) = 3.
Since f(a)  f(a’ ) and a  a’ , f is injective.
Proof B:
Let a, a’  R and suppose a = a’.
Multiply both sides by −4, so −4a = −4a’
Add 7 to both sides, so
7 − 4a = 7 − 4a’
Thus, f(a) = f(a’).
Therefore f is injective.
Proof C:
Let a, a’  R and suppose a  a’.
Then
−4a  −4a’
and also 7 − 4a  7 − 4a’
So, f(a)  f(a’).
Therefore f is injective.
Proof D:
Let a, a’ R and suppose f(a) = f(a’).
Then 7 − 4a = 7 − 4a’.
Subtract 7 from both sides, so −4a = −4a’ .
Divide both sides by −4, so a = a’.
Thus f is injective.
Proof E:
Let a, a’  R and suppose f(a)  f(a’).
Then 7 − 4a  7 − 4a’
and
−4a  −4a’
and so
a  a’
Thus f is injective.
Page 4 of 8
#10. Define f: R → R defined by f(x) = x2. Let S = [0, 9] and T = [− 9, 0].
#10(a) Find f(S), f(T), and f(S  T). Is f(S  T) = f(S)  f(T)?
#10(b) Find f −1(S), f −1 (T), and f −1 (S  T). Is f −1 (S  T) = f −1 (S)  f −1 (T)?
#11. Classify each function as injective, surjective, bijective, or none of these, as appropriate. If not
injective, briefly explain. If not surjective, briefly explain. (Otherwise, no explanation required.)
#11 (a) f: Z → Z defined by f(n) = 5 − n
#11 (b) f: N → Z defined by f(n) = n2 + 2n
#11 (c) f: Z → Z defined by f(n) = n2 + 2n
Page 5 of 8
Cardinality
#12. For each statement, is it True or False? (no explanation required)
1
1
1
1
________ (a) ⋂∞
=1 (6 − , 6 + ) is a countable set.
________ (b) ⋃∞
=1 (6 − , 6 + ) is a countable set.
________ (c) No subset of the irrational numbers is countable.
________ (d) Every subset of the rational numbers is countable.
#13. State a specific function f that is a bijection f: (0, 1) → (1, ). (Note that you can then conclude that
intervals (0, 1) and (1,) have the same cardinality. You are not asked to carry out a formal proof that
your f is bijective.)
#14. HINT: Look at page 2 of my posted notes on Cardinality.
#14(a) Show that the intervals (0, 1) and (3, 8) have the same cardinality by finding a
bijection f:(0, 1) → (3, 8).
#14(b) Suppose r < s. Prove that the intervals (0, 1) and (r, s) have the same cardinality by finding a bijection f:(0, 1) → (r, s). #14(c) Suppose a < b and c < d. Our goal is to show that open intervals (a, b) and (c, d) have the same cardinality. By part (b), there exist bijections g:(0, 1) → (a, b) and h:(0, 1) → (c, d). State a specific function f that is a bijection f: (a, b) → (c, d), where f is an appropriate composition of functions involving functions g, h, and/or their inverses. [Recall composition of functions ---see Relations and Functions notes, page 9]. You do not need a complicated formula. Just make use some of the functions g, h, g−1, h−1, with an appropriate composition. Page 6 of 8 ORDERED FIELDS #15. Consult the list of properties A1 - A5, M1 - M5, DL, O1 - O4 from my Ordered Field notes. Rather than considering those properties applied on the set R of real numbers, restrict the set as indicated below. In other words, check which properties still apply, when R is replaced by the set specified. #15 (a) Which properties are not satisfied on the set N? (Just list the identifying labels.) #15(b) Which properties are not satisfied on the set Z? (Just list the identifying labels.) #15(c) Let S = {x in R such that x  0}. Which properties are not satisfied on the set S? (Just list the identifying labels.) #16. Prove that 0 < 1/2 < 1. Fill in the blanks of the proof. Refer to the field axioms and order axioms and the Theorem in my Ordered Field notes, pages 1-2. Proof: Note that 0 < 1 (by Theorem part ___) Adding 1 to both sides, 0 + 1 < 1 + 1 by order axiom ___. 0 + 1 = 1 by field axiom _____, and 1 + 1 = successor of 1, which is designated by 2 (Peano axiom in Induction notes). So, we have 1 < 2. Since 0 < 1 and 1 < 2, we have 0 < 1 < 2. Then 0 < 1/2 < 1/1 by Theorem, part ___ Note that 1/1 = 1 (because 1  1 = 1). Thus, we have 0 < 1/2 < 1, as desired. Page 7 of 8 #17. Let x be a real number. Claim: If 0  x <  for all real numbers  > 0, then x = 0.
Fill in the blanks of the proof of the claim. Refer to the field axioms and order axioms and the Theorem
in my Ordered Field notes, pages 1-2.
Proof of Claim, by contradiction:
Suppose not.
Suppose for all real numbers  > 0, we have 0  x <  , but x  0. Since 0  x and x  0, we must have x __ 0. (fill in blank with <, = or, >, whichever is appropriate)
Set  = (1/2) x.
Since 1/2 > 0 (by problem #16) ,
we have  = (1/2) x > (1/2)  0 by order axiom ____.
=0
since (1/2)  0 = 0 by Theorem, part ___.
Since 1/2 < 1 (by problem #16) and x __ 0, we have  = (1/2) x < 1  x by order axiom ____, and so  = (1/2) x < x since 1  x = x by field axiom ____. In summary, we know x __ 0 and we have found a particular  > 0 for which x __ . (fill in the blanks to
show the correct order relationships between the numbers)
We have reached a contradiction of our hypothesis that x < , and so we conclude that x must be equal to 0. Page 8 of 8 MATH 301 Week 2 Homework, Spring, 2016. Due Sunday, February 14. NAME: _____________________________________ Instructions: You are encouraged to discuss homework, use online resources, and to seek help from the instructor when you need it, but your submitted write-up of your work must be your own, in your own words. Induction #1. Prove by induction that 9 + 12 + 15 + … + 3(n + 2) = 3n(n + 5)/2 for all n ∈ N. Page 1 of 8 #2. Prove the summation formula for the following particular finite geometric series. (Do not prove the general formula for a geometric progression and then substitute the value for the ratio. Instead, prove this particular formula shown below.) Prove by induction that + 4 + ⋯+ 4 = 1 − for every n ∈ N. #3. Prove by induction that (1.01)n ≥ 1 + (0.01)n for every n ∈ N . Page 2 of 8 Relations and Functions #4. Find an example of a relation that is reflexive and symmetric, but not transitive. (Note that you can just list an appropriate set of ordered pairs.) #5. Let S be a set. Let A and B be subsets of S. Let R be the relation given by A R B iff A ⊆ B. That is, A is related to B iff A is a subset of B. State which of the three properties (reflexive, symmetric, and transitive) apply. If a property does not hold, provide a counterexample. #6. State the range of each function f: R → R. (no work required to be shown) #6(a) f(x) = 3 sin(4x) #6(b) f(x) = 2(x + 1)2 + 5 #7. Let X = {1, 2, 3, 4, 5} and Y = {4, 5 ,6, 7}. Define a function f: X → Y as follows: f (1) = 7, f (2) = 6, f (3) = 4, f (4) = 5, f (5) = 6. For each statement, is it True or False? (no explanation required) ________ (a) ∃ x ∈ X such that f (x) = 3x. ________ (b) ∃ y ∈ Y such that ∀ x ∈ X, f (x) = y. ________ (c) ∀x ∈ X, ∃ y ∈ Y such that f (x) = y. ________ (d) ∀y ∈ Y, ∃ x ∈ X such that f (x) = y. ________ (e) f is injective. ________ (f) f is surjective. #8. Let f: A → B. Recall that f is injective iff ∀ a, a' ∈ A, if f(a) = f(a'), then a = a'. Write the contrapositive of the quantified if-then statement (the statement in bold). Page 3 of 8 #9. Claim: The function f: R → R defined by f(x) = 7 − 4x is injective. Consider the following "proofs" of the claim. INSTRUCTIONS: Critique each proof (A, B, C, D, E). For each proof, is it a valid argument establishing the claim or not? What are the flaws, if any? Proof A: Let a = 0 and a' = 1. f(a) = 7 and f(a') = 3. Since f(a) ≠ f(a' ) and a ≠ a' , f is injective. Proof B: Let a, a' ∈ R and suppose a = a'. Multiply both sides by −4, so −4a = −4a' Add 7 to both sides, so 7 − 4a = 7 − 4a' Thus, f(a) = f(a'). Therefore f is injective. Proof C: Let a, a' ∈ R and suppose a ≠ a'. Then −4a ≠ −4a' and also 7 − 4a ≠ 7 − 4a' So, f(a) ≠ f(a'). Therefore f is injective. Proof D: Let a, a'∈ R and suppose f(a) = f(a'). Then 7 − 4a = 7 − 4a'. Subtract 7 from both sides, so −4a = −4a' . Divide both sides by −4, so a = a'. Thus f is injective. Proof E: Let a, a' ∈ R and suppose f(a) ≠ f(a'). Then 7 − 4a ≠ 7 − 4a' and −4a ≠ −4a' and so a ≠ a' Thus f is injective. Page 4 of 8 #10. Define f: R → R defined by f(x) = x2. Let S = [0, 9] and T = [− 9, 0]. #10(a) Find f(S), f(T), and f(S ∩ T). Is f(S ∩ T) = f(S) ∩ f(T)? #10(b) Find f −1 (S), f −1 (T), and f −1 (S ∩ T). Is f −1 (S ∩ T) = f −1 (S) ∩ f −1 (T)? #11. Classify each function as injective, surjective, bijective, or none of these, as appropriate. If not injective, briefly explain. If not surjective, briefly explain. (Otherwise, no explanation required.) #11 (a) f: Z → Z defined by f(n) = 5 − n #11 (b) f: N → Z defined by f(n) = n2 + 2n #11 (c) f: Z → Z defined by f(n) = n2 + 2n Page 5 of 8 Cardinality #12. For each statement, is it True or False? (no explanation required) ________ (a) ⋂ 6 − , 6 + is a countable set. ________ (b) ⋃ 6 − , 6 + is a countable set. ________ (c) No subset of the irrational numbers is countable. ________ (d) Every subset of the rational numbers is countable. #13. State a specific function f that is a bijection f: (0, 1) → (1, ∞). (Note that you can then conclude that intervals (0, 1) and (1,∞) have the same cardinality. You are not asked to carry out a formal proof that your f is bijective.) #14. HINT: Look at page 2 of my posted notes on Cardinality. #14(a) Show that the intervals (0, 1) and (3, 8) have the same cardinality by finding a bijection f:(0, 1) → (3, 8). #14(b) Suppose r < s. Prove that the intervals (0, 1) and (r, s) have the same cardinality by finding a bijection f:(0, 1) → (r, s). #14(c) Suppose a < b and c < d. Our goal is to show that open intervals (a, b) and (c, d) have the same cardinality. By part (b), there exist bijections g:(0, 1) → (a, b) and h:(0, 1) → (c, d). State a specific function f that is a bijection f: (a, b) → (c, d), where f is an appropriate composition of functions involving functions g, h, and/or their inverses. [Recall composition of functions ---see Relations and Functions notes, page 9]. You do not need a complicated formula. Just make use some of the functions g, h, g−1, h−1, with an appropriate composition. Page 6 of 8 ORDERED FIELDS #15. Consult the list of properties A1 - A5, M1 - M5, DL, O1 - O4 from my Ordered Field notes. Rather than considering those properties applied on the set R of real numbers, restrict the set as indicated below. In other words, check which properties still apply, when R is replaced by the set specified. #15 (a) Which properties are not satisfied on the set N? (Just list the identifying labels.) #15(b) Which properties are not satisfied on the set Z? (Just list the identifying labels.) #15(c) Let S = {x in R such that x ≥ 0}. Which properties are not satisfied on the set S? (Just list the identifying labels.) #16. Prove that 0 < 1/2 < 1. Fill in the blanks of the proof. Refer to the field axioms and order axioms and the Theorem in my Ordered Field notes, pages 1-2. Proof: Note that 0 < 1 (by Theorem part ___) Adding 1 to both sides, 0 + 1 < 1 + 1 by order axiom ___. 0 + 1 = 1 by field axiom _____, and 1 + 1 = successor of 1, which is designated by 2 (Peano axiom in Induction notes). So, we have 1 < 2. Since 0 < 1 and 1 < 2, we have 0 < 1 < 2. Then 0 < 1/2 < 1/1 by Theorem, part ___ Note that 1/1 = 1 (because 1 ⋅ 1 = 1). Thus, we have 0 < 1/2 < 1, as desired. Page 7 of 8 #17. Let x be a real number. Claim: If 0 ≤ x < ε for all real numbers ε > 0, then x = 0.
Fill in the blanks of the proof of the claim. Refer to the field axioms and order axioms and the Theorem
in my Ordered Field notes, pages 1-2.
Proof of Claim, by contradiction:
Suppose not.
Suppose for all real numbers ε > 0, we have 0 ≤ x < ε , but x ≠ 0. Since 0 ≤ x and x ≠ 0, we must have x __ 0. (fill in blank with <, = or, >, whichever is appropriate)
Set ε = (1/2) x.
Since 1/2 > 0 (by problem #16) ,
we have ε = (1/2) x > (1/2) ⋅ 0 by order axiom ____.
=0
since (1/2) ⋅ 0 = 0 by Theorem, part ___.
Since 1/2 < 1 (by problem #16) and x __ 0, we have ε = (1/2) x < 1 ⋅ x by order axiom ____, and so ε = (1/2) x < x since 1 ⋅ x = x by field axiom ____. In summary, we know x __ 0 and we have found a particular ε > 0 for which x __ ε. (fill in the blanks to
show the correct order relationships between the numbers)
We have reached a contradiction of our hypothesis that x < ε, and so we conclude that x must be equal to 0. Page 8 of 8 Ordered Fields Assume the existence of a set R, called the set of real numbers, and two operations + and ⋅, called addition and multiplication, such that the following properties apply: Field Axioms A1. Closure property of addition: For all x, y ∈ R, x + y ∈ R and if x = w and y = z, then x + y = w + z. A2. Commutative law of addition: For all x, y ∈ R, x + y = y + x. A3. Associative law of addition: For all x, y, z ∈ R, x + (y + z) = (x + y) + z. A4. Identity for addition: There is a unique real number 0 such that x + 0 = x, for all x ∈ R. A5. Additive inverse: For each x ∈ R, there is a unique real number -x such that x + (-x) = 0. M1. Closure property of multiplication: For all x, y, ∈ R, x ⋅ y ∈ R, and if x = w and y = z, then x ⋅ y = w ⋅ z. M2. Commutative law of multiplication: For all x, y ∈ R, x ⋅ y = y ⋅ x. M3. Associative law of multiplication: For all x, y, z ∈ R, x ⋅ (y ⋅ z) = (x ⋅ y) ⋅ z. M4. Identity for multiplication: There is a unique real number 1 such that 1 is not 0 and x ⋅ 1 = x for all x ∈ R. M5. Multiplicative inverse: For each x ∈ R with x ⋅ 0, there is a unique real number 1/x such that x ⋅ (1/x) = 1. We also write x-1 in place of 1/x. DL. Distributive law: For all x, y, z ∈ R, x ⋅ (y + z) = x ⋅ y + x ⋅ z. Order axioms (shown below for <, but also apply to >)
O1. Trichotomy law: For all x, y ∈ R, exactly one of the relations x = y, x > y, or x < y holds. O2. Transitive property: For all x, y, z ∈ R, if x < y and y < z, then x < z. O3. Addition principle for inequalities: For all x, y, z ∈ R, if x < y, then x + z < y + z. O4. Multiplication principle for inequalities: For all x, y, z ∈ R, if x < y and z > 0, then x ⋅ z < y ⋅ z. An ordered field is any mathematical system satisfying the 15 axioms. Discussed in the Lebl book in section 1.1 Examples: Q and R. Page 1 of 2 Here is a sampling of results that can be proven. Theorem. Let x, y, and z be real numbers. (a) If x + z = y + z, then x = y. (b) x ⋅ 0 = 0. (c) (-1) ⋅ x = -x. (d) x ⋅ y = 0 iff x = 0 or y = 0. (e) x < y iff -y < -x. (f) If x < y and z < 0, then x ⋅ z > y ⋅ z.
(g) If x ≠ 0 , then x2 > 0.
(h) 0 < 1. (i) If 0 < x < y, then 0 < 1/y < 1/x. Proof of (e): Suppose that x < y. x + (-x) < y + (-x) by O3 (Addition principle for inequalities) 0 < [y + (-x)] by A5 (Additive inverse) 0 + (-y) < [y + (-x)] + (-y) by O3. 0 + (-y) < y +[ (-x)] + (-y)] by A3 (Associative property for +). (-y) + 0 < y +[ (-y)] + (-x)] by A2 (Commutative property for +). -y < [y + (-y)] + (-x) by A4 (Identity for +) and A3 (Associative property for +) -y < 0 + (-x) by A5 (Additive inverse) -y < (-x) + 0 by A2 (Commutative property for +). -y < -x by A4 (Identity for +) So, if x < y, then -y < -x. Suppose that -y < -x. Then -(-x) < -(-y) (applying a < b ⇒ -b< -a, with a = -y and b = -x) x Purchase answer to see full attachment

How it works

1. Paste your instructions in the instructions box. You can also attach an instructions file
2. Select the writer category, deadline, education level and review the instructions 
3. Make a payment for the order to be assignment to a writer
4.  Download the paper after the writer uploads it 

Will the writer plagiarize my essay?

You will get a plagiarism-free paper and you can get an originality report upon request.

Is this service safe?

All the personal information is confidential and we have 100% safe payment methods. We also guarantee good grades