Problem Set 9 — Set Theory

Purpose

This problem set provides practice reasoning about sets and proofs about them. It thus addresses the following learning outcomes:

• Outcome 2.1, Prove properties of and relationships between sets
• Outcome 5, Construct direct and indirect proofs and proofs by induction and determine the appropriateness of each type in a particular setting.*
• Outcome 6, Unravel abstract definitions, create intuition-forming examples or counterexamples, and prove conjectures
• 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 draws on material in sections 5.1 through 5.3 of our textbook. We discussed that material in classes between April 2 and April 9.

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

Exercises 15a, b, and c in section 5.1 of our textbook: determine whether certain intervals of the real numbers are subsets of each other; find intersections, unions, and differences of intervals. See the textbook for details.

Problem 2

Exercise 12b in section 5.2 of our textbook: prove that if \(A\), \(B\), and \(C\) are subsets of some universal set, and \(A \subseteq B\), then \(A \cup C \subseteq B \cup C\).

Problem 3

Exercises 5a and 5c in section 5.3 of our textbook: use Venn diagrams to form a conjecture about the relationship between \(A - (B \cap C)\) and \((A-B) \cup (A-C)\), where \(A\), \(B\), and \(C\) are subsets of some universal set; then use set algebra to prove your conjecture.

Problem 4

(This is an example of what I call a “Proofs Out of Context” problem, because it asks you to apply proof techniques from this course in contexts that you haven’t necessarily seen before. This particular problem is adapted from a set of out of context problems for Math 239 developed by Prof. Olympia Nicodemi.)

Assume the following is true: For all real numbers \(x\) and \(y\), if \(x > 0\) then there is a natural number \(n\) such that \(nx > y\).

Use this fact to prove the following two claims. Be prepared during grading to say what these claims, particularly the second, tell you about the real numbers.

Part A

For all real numbers \(x\), if \(x > 0\) then there is a natural number \(n\) such that \(0 < \frac{1}{n} < x\).

Part B

For all real numbers \(x\) and \(y\), if \(x < y\) then there is a natural number \(n\) such that \(x < x + \frac{1}{n} < y\).

The Part B claim should turn out to be a corollary of the one in Part A, i.e., something that mostly follows from that claim. So it is OK, and in fact expected, if a significant part of the logic in your proof is along the lines of “…it now follows from Part A that….”

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.