Problem Set 7—Introduction to Set Theory

Purpose

This problem set mainly reinforces your understanding of basic set operations and proofs involving them. Additionally, it also develops your ability to apply material from this course outside the context in which you learned it.

Background

Our textbook covers the basic set operations and terminology in section 5.1, and we discussed that material in class on March 30. Proofs about sets are discussed in section 5.2, and we will cover them in class on April 2.

For a review of the idea of a set and some set notations, see section 2.3 of our textbook.

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

Parts a, b, c, d, e, g, i, and k of Exercise 8 in section 5.1 of our textbook. These problems all ask you to find various combinations of certain sets. See the book for details.

Problem 2

Exercise 2 in section 5.2 of our textbook. (Draw a Venn diagram showing sets A, B, and C such that A ⊆ B and B ⊆ C. Then prove that in general if A ⊆ B and B ⊆ C, then A ⊆ C. See the book for additional discussion.)

Problem 3

Inspired by Exercise 14 in section 5.1 of our textbook. Our textbook points out that subset relationships are in many ways analogous to “less than” or “less than or equal” relationships between real numbers. Exercise 14 further points out that real numbers have a “Law of Trichotomy” that says that for any real numbers a and b, exactly one of the following is true: a < b, a = b, a > b (or equivalently, b < a).

Show that the proper subset relation does not behave completely analogously to “less than” by showing that it is possible to have two sets A and B that are both subsets of a universal set, but for which none of the relations A ⊂ B, A = B, and B ⊂ A hold. State this claim as a proposition and give a formal proof of it.

Problem 4 (Proofs Out of Context)

This problem continues the set of out of context problems from Prof. Nicodemi that we started in Problem Set 4. From that problem set, recall the following, all of which you can now take as proven:

Fact 1. For all real numbers x and y, if x > 0 then there is a natural number n such that nx > y.

Proposition 1. For all real numbers x, if x > 0 then there is a natural number n such that 0 < 1/n < x.

In addition to what you have from Problem Set 4, here is one new fact:

Fact 2. For any real number x there is an integer m such that x ≤ m and m-1 < x.

Proposition 2. For any real numbers x and y such that x < y, there is a natural number n such that ny - nx > 1.

Proposition 3. If x and y are real numbers such that x < y and n is a natural number such that ny - nx > 1, there is an integer q such that nx < q < ny. (Hint: It may help with part of the proof to find m as in Fact 2 for ny, then subtract 1.)

Theorem. For any real numbers x and y such that x < y, there is a rational number s such that x < s < y. (Hint: this is just one step from Proposition 3.)

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) the concept of set union, (2) the concept of set intersection, (3) the concept of set difference, (4) the concept of set complement, (5) what it means for one set to be a subset of another, (6) how to prove claims about subset relationships, and (7) how to express proofs formally, including proofs out of context.
• 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 or two 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 three to five 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.