Problem Set 10 — Sets and Functions

Purpose

This problem set provides further practice reasoning about sets and proofs about them, along with some initial practice reasoning about functions. It addresses the following learning outcomes:

• Outcome 1.2, Prove equivalence of statements involving logical quantifiers
• Outcome 2.2, Prove properties of and relationships between indexed families of sets
• 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

This problem set mainly draws on material in sections 5.4 and 5.5 of our textbook, which we discussed between April 12 and 14.

Part of the problem set also draws on knowledge of functions, as presented in sections 6.1 and 6.2 of the textbook, and discussed on April 16.

One question asks you to write expressions involving quantifiers. Quantifiers and the notation for them are described in section 2.4 of the textbook, and appear in class notes between February 26 and March 3.

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

Problem 9 from section 5.4 of our textbook (determine whether it is true that if \(A \times B = A \times C\) for sets \(A\), \(B\), and \(C\) with \(A \ne \emptyset\), then \(B = C\), proving your answer and explaining where the requirement that \(A \ne \emptyset\) enters the argument).

Problem 2

Suppose \(\mathcal{A} = \{A_i | i \in \Lambda\}\) where the \(A_i\) are sets and \(\Lambda\) is an indexing set. Use the symbolic notation for quantifiers introduced in section 2.4 of our textbook to write expressions that say what the statements

and

mean. In other words, write an expression involving the symbols for “there exists” and/or “for all” that is true exactly when relation (1) holds, and another that is true exactly when relation (2) holds.

Problem 3

Problem 4b in section 5.5 of our textbook (prove part 4 — one of De Morgan’s laws — of Theorem 5.30).

Problem 4

You have probably run into the idea of a function’s “inverse” before. Informally, the inverse of function \(f\) is an association that undoes \(f\). More formally, the inverse of \(f\), written \(f^{-1}\), associates elements from the codomain of \(f\) with elements of the domain, with the property that \(f^{-1}(y) = x\) if and only if \(f(x) = y\). The inverse of a function is not necessarily a function itself, i.e., doesn’t necessarily meet all the requirements for being a function.

Consider the following functions from the reals to the reals:

1. \(f(x) = 2\),
2. \(g(x) = 2x\), and
3. \(h(x) = x^2\)

For each of these functions, describe as precisely and mathematically as you can their inverses. Then say which of the inverses are functions and which are not. You should be able to give the reasons why you believe an inverse is or isn’t a function, but don’t have to write it as a formal proof.

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.