Purpose
This problem set reinforces your ability to reason about functions. In particular, it develops your understanding of injections, surjections, and bijections; of function compositions; and of inverses.
Background
This exercise is based on sections 6.3 through 6.5 of our textbook. We discussed, or will discuss, this material in class between April 5 and April 12.
Activity
Solve the following problems. Formal proofs should be word-processed (i.e., not hand-written) and should follow the guidelines in Sundstrom’s text.
Problem 1
Exercise 8a in section 6.4 of our textbook (if f(x) = x + 1, find an expression for f n(x) and use induction to prove it correct; see the textbook for a definition of the f n notation).
Problem 2
Exercise 9 in section 6.5 of our textbook (prove that if f : A → B is a bijection, then f -1 : B → A is also a bijection).
Problem 3
An extension of exercise 14 in section 6.3 of our textbook: determine whether f(n) = (1 + (-1)n(2n-1)) / 4 is an injection, a surjection, and/or a bijection. Justify each conclusion with a formal proof or a counterexample. See the book for hints and more details.
Problem 4
This problem continues the set of out of context problems from Prof. Nicodemi that we saw in Problem Sets 5 and 9. From those problem sets, recall the following, all of which you can now take as proven:
Fact 1. For all real numbers x and y, if x > 0 then there is a natural number n such that nx > y.
Fact 2. For any real number x there is an integer m such that x ≤ m and m-1 < x.
Proposition 1. For all real numbers x, if x > 0 then there is a natural number n such that 0 < 1/n < x.
Corollary 1. For all real numbers x and y, if x < y then there is a natural number n such that x < x + 1/n < y.Proposition 2. For any real numbers x and y such that x < y, there is a natural number n such that ny - nx > 1.
Now prove the following:
Proposition 3. If x and y are real numbers such that x < y and n is a natural number such that ny - nx > 1, then there is an integer q such that nx < q < ny. Hint: first find m as in Fact 2 for ny and then subtract 1.
Theorem. For any real numbers x and y such that x < y, there is a rational number s such that x < s < y. Hint: this is only one step from Proposition 3.
Follow-Up
I will grade this exercise in a face-to-face meeting with you. During this meeting I will look at your solution, ask you any questions I have about it, answer questions you have, etc. Please bring a written solution to the exercise to your meeting, as that will speed the process along.
Sign up for a meeting via Google calendar. Please make the meeting 15 minutes long, and schedule it to finish before the end of the “Grade By” date above.