Problem Set 12—Functions

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 ⁿ(x) and use induction to prove it correct; see the textbook for a definition of the f ⁿ 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)ⁿ(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.

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.