Problem Set 8—Proofs about Sets

Purpose

This problem set mainly reinforces your ability to prove relationships between sets. It also develops your ability to reason about Cartesian products of sets.

Background

Most of this problem set is based on ideas about proving set relationships from sections 5.2 and 5.3 of our textbook. We discussed that material in class on April 2 and 4. This problem set also contains questions about Cartesian products, which are described in section 5.4 of our textbook, and which we discussed in class on April 6.

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 14 in section 5.2 of our textbook (prove that for all sets A, B, and C that are subsets of some universal set, if A ∩ B = A ∩ C and A^C ∩ B = A^C ∩ C, then B = C).

Problem 2

Exercise 11a from section 5.3 of our textbook; use set algebra in your proof (prove that A - (A∩B^C) = A∩B, where A and B are subsets of some universal set U).

Problem 3

Exercise 5 from section 5.3 of our textbook (use Venn diagrams to form a conjecture about the relationship between A - (B∩C) and (A-B) ∪ (A-C), then prove that conjecture in two ways; see book for more details).

Problem 4

Let A = {-1,0,1} and B = {a,b}. Find the Cartesian product A × B.

Problem 5

Exercise 6 from section 5.4 of our textbook (prove part 7 of theorem 5.25; see the book for details).

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 construct element-chasing proofs about set relationships, (2) how to use the algebra of set operations to construct proofs about set relationships, (3) what the Cartesian product is, and (4) how to express proofs formally.
• 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 in which you partially or completely fail to understand one 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 two 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.