Last(!) Problem Set — Relations and Functions

Purpose

This problem set provides further practice reasoning about functions and relations. It addresses the following learning outcomes:

• Outcome 3.1, Determine whether a relation is an equivalence relation
• Outcome 3.2, Identify the equivalence classes of an equivalence relation
• Outcome 4.1, Construct proofs that functions are injections, surjections, and bijections
• Outcome 4.2, Determine whether two functions are inverses of each other
• Outcome 5*, Construct direct and indirect proofs and proofs by induction and determine the appropriateness of each type in a particular setting
• Outcome 7, Write solutions to problems and proofs of theorems that meet rigorous standards based on content, organization and coherence, argument and support, and style and mechanics.

(* On this problem set, I leave it to you to identify appropriate method(s) for the proofs. I will associate your grade(s) for those proofs with specific sub-outcomes of learning outcome 5 (i.e., 5.1 through 5.5) according to the methods you choose and how well you use them.)

Background

Part of this problem draws on material about functions from sections 6.3 and 6.5 of our textbook. We discussed this material between April 19 and 23.

Another part of the problem set draws on information about relations from sections 7.1 through 7.3 of the textbook. We discussed, or will discuss, this material between April 26 and 30.

Activity

Solve the following problems.

Write any proofs as formal proofs, following the usual mathematical conventions, including typeface rules (e.g., italic variable names, emphasized labels for theorems and proofs, etc.)

Problem 1

(Exercise 9 in section 6.5 of our textbook.) Prove that if \(f : A \to B\) is a bijection, then \(f^{-1} : B \to A\) is also a bijection.

Problem 2

(An extension of exercise 14 in section 6.3 of our textbook.) Determine whether function \(f : \mathbb{N} \to \mathbb{Z}\) defined by

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.

I expect that answering this question with complete formal proofs will be time-consuming, and that the proofs will be long, will involve multiple proof techniques, and may benefit from being written as multiple distinct proofs. Please take the time to think about these things as you write your answer to this question, possibly including taking the time to revise your first version of an answer into one you feel is clearer or simpler. These are all things mathematicians go through in devising “real” (as opposed to classroom) proofs.

Problem 3

A variation on exercise 10a in section 7.2 of our textbook: define relation \(\sim\) on \(\mathbb{Z}\) by \(a \sim b\) if and only if 2 divides \(a+b\). Prove that \(\sim\) is an equivalence relation, and then describe the equivalence class of the integer 1 for relation \(\sim\).

Problem 4

Define a “nearly equal” relation on real numbers by \(x\) is nearly equal to \(y\) if and only if \(|x-y| < 0.001\). Is this “nearly equal” an equivalence relation? Explain why or why not.

(This relation has a real-world connection to computing. Computers don’t represent real numbers exactly. Instead, they use a kind of scientific notation with a fixed number of digits. Any real number that can’t be exactly represented in that many digits has to be rounded. One consequence is that when programmers are comparing the results of real-valued calculations (e.g., testing to see if two different functions produce the same result) they don’t want to test for exact equality, because two results that are mathematically equal might round to slightly different values in the computer. Thus programmers often want a “nearly equal” test for numbers. Because “nearly equal” tests are supposed to behave like equality tests, except allowing for rounding errors, they should be equivalence relations.)

Follow-Up

I will grade this exercise during one of your weekly individual meetings with me. That meeting should happen on or before the “Grade By” date above. During the meeting I will look at your solution, ask you any questions I have about it, answer questions you have, etc. Sign up for the meeting via Google calendar. Please have a written solution to the exercise ready to share with me during your meeting, as that will speed the process along.