Problem Set 10—Proving Set Relationships

Purpose

This problem set reinforces your ability to prove conjectures about sets, their relationships to other sets, and their operations.

Background

This problem set is based on material in sections 5.2 and 5.3 of our textbook. We discussed, or will discuss, this material in class on March 22 and March 24.

Activity

Solve the following problems. Formal proofs should be word-processed (i.e., not hand-written) and should follow the guidelines in Sundstrom’s text.

Problem 1

Exercise 9 in section 5.2 of our textbook (determine whether it is true or not that for all sets A and B that are subsets of some universal set, A ∩ B is disjoint from A - B; support your answer with either a proof or a counterexample).

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 (Proofs Out Of Context)

A recurrence relation is a kind of piecewise function definition that is sometimes used to define functions on the natural numbers. In a recurrence relation, one or more parts of the definition explicitly define the function’s value on a few small numbers, while other parts define the function’s value on larger numbers in terms of its value on smaller numbers. As a general rule, recurrence relations are only useful for defining functions on inductive sets, for example you’ll never see recurrence relations used to define a function on the real numbers.

Here is an example of a recurrence relation:

f(n) = 1 if n = 1
f(n) = 2 + f(n-1) if n > 1

You can figure out some values of f(n) from this definition as follows: f(1) = 1, because the definition says that explicitly. f(2) is defined by the second line of the definition, because 2 > 1. Therefore f(2) = 2 + f(1) = 2 + 1 = 3. Similarly f(3) = 2 + f(2) = 5. Note that f(0) is undefined, as is f applied to any value less than 0. It might appear from these examples that f generates the positive odd numbers, i.e., that f(n) = 2n - 1.

Prove the conjecture from the previous paragraph, i.e., prove that f(n) = 2n - 1 for all natural numbers n.

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.