Mathematics Hothouse

Reference: AMS, Student Mathematical Library: Basic Set Theory by A. Shen, et al. Chapter 1. Section 1.

Problem 1:

Consider the oldest mathematician amongst chess players and the oldest chess player amongst mathematicians. Could they be two different people?

Problem 2:

The same question for the best mathematician amongst chess players and the best chess player amongst mathematicians.

Problem 3:

One tenth of mathematicians are chess players, and one sixth of chess players are mathematicians. Which group (mathematicians or chess players) is bigger? What is the ratio of sizes of these two groups?

Problem 4:

Do there exist sets A, B and C such that , and ?

Problem 5:

Which of the following formulas are true for arbitrary sets A, B and C:

i)

ii)

iii)

iv)

v)

vi)

Problem 6:

Give formal proofs of all valid formulas from the preceding problem. (Your proof should go like this : “We have to prove that the left hand side equals the right hand side. Let x be any element of the left hand side set. Then, ….Therefore, x belongs to the right hand side set. On the other hand, let…”)

Please give counterexamples to the formulas which are not true.

Problem 7:

Prove that the symmetric difference is associative:

for any sets A, B and C. Hint: Addition modulo two is associative.

Problem 8:

Prove that:

for arbitrary sets .

Problem 9:

Consider an inequality whose left hand side and right hand side contain set variables and operations and -. Prove that if this equality is false for some sets, then it is false for some sets that contain at most one element.

Problem 10:

How many different expressions can be formed from set variables A and B by using union, intersection and set difference? (Variables and operations can be used more than once. Two expressions are considered identical if they assume the same value for each set of values of the variables involved.) Solve the same problem for three sets and for n sets. (Answer: In the general case, )

Problem 11:

Solve the same problem if only and are allowed. For n=2 and n-3, this problem is easy to solve; however, no general formula for any n is known. This problem is also called “counting monotone Boolean functions in n variables”.)

Problem 12:

How many subsets does an n-element subset have?

Problem 13:

Assume that A consists of n elements and consists of k elements. Find the number of different sets C such that .

Problem 14:

A set U contains 2n elements. We select k subsets of A in such a way that none of them is a subset of another one. What is the maximum possible value of k? (Hint: Maximal k is achieved when all subsets have n elements. Indeed, imagine the following process: We start with an empty set and add random elements one by one until we get U. At most one selected set can appear in this process. On the other hand, the expected number of selected sets that appear during this process can be computed using the linearity of expectation. Take into account that the probability to come across some set is minimal when Z contains n elements, since all the sets of a given size are equiprobable.)

Your comments/solutions are welcome.

Regards,

Nalin Pithwa.