Problem Set 9—Sets and Functions

Purpose

This problem set reinforces your ability to reason about functions and create proofs dealing with them, and also gives you some more practice working with sets.

Background

Part of this problem set deals with material from sections 5.4 and 5.5 of our textbook, which we discussed on April 6 and 9 respectively. Problem 1 refers to the size, or “cardinality,” of finite sets. The last subsection of section 5.1 (starting on page 223 in my copy of the book) discusses this idea.

The rest of the problem set is based on material from sections 6.1 through 6.4 of the textbook. We discussed that material in class between April 11 and 16.

Activity

Solve the following problems. All proofs should be word-processed (i.e., not hand-written) and should follow the guidelines for formal proofs from Sundstrom’s text and class discussion.

Problem 1

Let A and B be finite sets. Prove that the cardinality of A × B is card(A) × card(B).

Problem 2

Exercise 4b in section 5.5 of our textbook (prove that the complement of the union of all sets in an indexed family is the intersection of the complements of the sets; see the textbook for a more formal and precise description of the problem).

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

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).

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.

I will use the following guidelines to grade this problem set:

• What I expect (8 points). Between your written answers and verbal explanations, I expect you to show that you understand (1) how to prove/disprove that functions are injections, (2) how to prove/disprove that functions are surjections, (3) how to prove/disprove that functions are bijections, (4) how to reason about compositions of functions, (5) how to reason about indexed families of sets, and (6) how to create and express formal proofs.
• Three quarters of what I expect (6 points). A plausible, but not the only, example of a solution that would meet three quarters of my expectations for this problem set is one with significant errors in solutions to one or more problems even though you generally understand the expected items, OR one that shows that you fail to understand 1 of the expected items.
• Half of what I expect (4 points). Some plausible, but not the only, examples of solutions that would meet half my expectations include ones that show you do not understand 2 to 4 of the expected items but do understand the others, OR solutions that show you partially understand all the expected items.
• Exceeding expectations (typically 1 point added to what you otherwise earn). Demonstrating that you have significantly engaged with math beyond what is needed to solve the given problems exceeds what I expect; exploring new or extended conjectures arising from any of the problems is one way to do this.