Problem Set 11—Functions

Purpose

This problem set develops your ability to reason about functions. It also reinforces your understanding of families of sets.

Background

Our textbook covers families of sets in section 5.5, and we discussed them in class on November 8. The material on functions used in this exercise is discussed in sections 6.1 through 6.3. We will discuss it in classes between November 11 and November 16.

Problem 4 comes from a set of problems posed by Prof. Nicodemi. She took them from real analysis, and asked her Math 239 students to solve them. I think they make a good exercise in applying proof ideas from this course in a context different from what we are mostly looking at, and I’m curious how you will do with them. I plan to give you a couple of her problems per problem set for the rest of the semester. Think of them as problems to challenge yourself against more than problems that exercise specific topics from our current classes.

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 8b from section 5.5 of our textbook (prove that if A_α ⊆ C, then the union of all the A_α is also a subset of C; see book for a more detailed statement of the problem).

Problem 2

Exercise 2 in section 6.2 of our textbook (ultimately, determine whether f(x) = x²+4 (mod 6) and g(x) = (x+1)(x+4) (mod 6) are equal; see the book for more details and hints).

Problem 3

Exercise 14 in section 6.3 of our textbook, justifying each conclusion with either a proof or a counterexample (determine whether f(n) = (1 + (-1)ⁿ(2n-1)) / 4 is an injection and/or a surjection; see book for hints and more details).

Problem 4

Take the following as given:

Fact 1. For any real numbers x > 0 and y, 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 but x ≰ m - 1.

Now prove the following propositions, but first figure out what they mean by finding examples:

Proposition 1. For any real number x such that x > 0, there is a natural number n such that 0 < 1/n < x.

Corollary to Proposition 1. For any real numbers x and y such that x < y, there is a natural number n such that x < x + 1/n < y.

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.