Problem Set 10—Relations and Countability

Purpose

This problem set mainly reinforces your ability to reason about equivalence relations and infinite sets, although it also gives you practice with proofs about inverses of functions.

Background

Our textbook discusses equivalence relations in sections 7.1 through 7.3. We discussed this material in classes on April 20 and 23.

This problem set’s exercises on infinite sets are based on material in sections 9.1 and 9.2 of the textbook. We will discuss that material in classes on April 25 and 27.

Finally, inverse functions are in section 6.5 of the textbook, and were discussed in class on April 18.

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

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 2

A variation on exercise 10a in section 7.2 of our textbook: define relation ∼ on ℤ by a ∼ b if and only if 2 divides a + b. Prove that ∼ is an equivalence relation, and then describe the equivalence class of the integer 1 for relation ∼.

Problem 3

Exercise 5c in section 9.1 of our textbook (prove that if A ∩ B is an infinite set, then A is an infinite set).

Problem 4

Exercise 2b in section 9.2 of our textbook (prove that the set of integers that are multiples of 5 is countably infinite).

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) what an equivalence relation is and how to prove that a relation is one, (2) what an equivalence class is, (3) how to determine whether a set is finite or not, and (4) how to show that a set is countably infinite.
• 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 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.