## Monthly Archives: June 2020

### Set Theory Primer : Some basic thinking and problem solving

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 $A \bigcap B \neq \phi$, $A \bigcap C = \phi$ and $(A\bigcap B)-C = \phi$ ?

Problem 5:

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

i) $(A \bigcap B) \bigcup C = (A \bigcup C) \bigcap (B \bigcup C)$

ii) $(A \bigcup B) \bigcap C = (A \bigcap C) \bigcup (B \bigcap C)$

iii) $(A \bigcup B) - C = (A-C)\bigcup B$

iv) $(A \bigcap B) - C = (A - C) \bigcap B$

v) $A - (B \bigcup C) = (A-B) \bigcap (A-C)$

vi) $A - (B \bigcap C) = (A-B) \bigcup (A-C)$

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:

$A \triangle (B \triangle C) = (A \triangle B) \triangle C$ for any sets A, B and C. Hint: Addition modulo two is associative.

Problem 8:

Prove that:

$(A_{1}\bigcap A_{2}\bigcap \ldots A_{n}) \triangle (B_{1} \bigcap B_{2} \bigcap \ldots B_{n}) = (A_{1} \triangle B_{1}) \bigcup (A_{2} \triangle B_{2}) \ldots (A_{n} \triangle B_{n})$ for arbitrary sets $A_{1}, A_{2}, \ldots, A_{n}, B_{1}, B_{2}, \ldots, B_{n}$.

Problem 9:

Consider an inequality whose left hand side and right hand side contain set variables and operations $\bigcap, \bigcup$ 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, $2^{2^{n}-1}$)

Problem 11:

Solve the same problem if only $\bigcup$ and $\bigcap$ 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 $B \subset A$ consists of k elements. Find the number of different sets C such that $B \subset C \subset A$.

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 $Z \subset U$ is minimal when Z contains n elements, since all the sets of a given size are equiprobable.)

Regards,

Nalin Pithwa.

Purva building, 5A
Flat 06
Near Dimple Arcade, Thakur Complex
Mumbai, Maharastra 400101
India.

### Skill Check IV: IITJEE Foundation Maths

I. State whether the following statements are True or False:

(i) 0 is to the left of all negative numbers on the number line.

(ii) 3 is greater than -3333.

(iii) $1\frac{2}{5}$ will lie to the right of the mid-point between 1 and 2 on the number line.

(iv) $1\frac{2}{5}$ will lie to the left of the mid-point between 1 and 2 on the number line.

(v) If a decimal fraction is non-terminating and non-recurring, it is known as a rational number.

(vI) The rational number $3\frac{1}{5}$ lies between $3\frac{2}{11}$ and $3 \frac{3}{11}$

II. How many natural numbers lie between 212 and 2120?

III. How many integers lie between -219 and +2190?

IV. Write the following numbers in descending order: (i) -213, +126, -212, +127, -127 (ii) $-1\frac{7}{11}, -3\frac{7}{11}$, $-2\frac{7}{11}, -5\frac{7}{11}, -4\frac{7}{11}$ (iii) $\frac{3}{5}, -\frac{2}{9}, \frac{5}{7}, -\frac{3}{10}, \frac{11}{21}$ (iv) -2.3838, -2.3388, -2.8838, -2.8833, -2.3883 (v) $3.\overline{8}, 3.\overline{6}, 3.88, 3.6\overline{8}, 3.8\overline{6}$

V. Write the following numbers in ascending order: (i) +418, -481, -418, +481, -841 (II) $-1\frac{3}{11}, -1\frac{4}{11}, -1\frac{5}{11}, -1\frac{6}{11}, -1\frac{7}{11}$ (iii) $\frac{2}{5}, \frac{11}{23}, \frac{7}{15}, \frac{9}{20}, \frac{3}{7}$ (iv) $6.7134, 6.7431, 6.7341, 6.7413, 6.7143$ (v)$7.9\dot{8}, 7.\dot{9}, 7.\overline{98}, 7.8\dot{9}, 7.\dot{8}$

VI. Insert a rational number between the following pairs of numbers: (i) -0.001 and +0.001 (ii) -8 and -3 (iii) 85 and 86 (iv) 5.5 and 6 (v) $\frac{1}{4}$ and $\frac{1}{5}$ (vi) $2\frac{2}{5}, 2\frac{3}{5}$ (vii) 3.0688 and 3.0699 (viii) 5.2168 and 5.2169 (ix) $1\frac{9}{15}, 1\frac{11}{15}$ (x) $-8\frac{6}{7}, -8\frac{5}{7}$

VII. Insert 2 rational numbers between the following numbers: (a) 3.18 and 3.19 (b) $2\frac{2}{5}, 2 \frac{3}{5}$

VIII. Represent the following rational numbers on the number line:

(i) $2\frac{1}{3}$ (ii) $-\frac{5}{7}$ (iii) $3.7$ (iv) $4.85$ (v) $6 \frac{7}{11}$

IX. Which of the following rational numbers will have a terminating decimal value? (a) $\frac{3}{5}$ (b) $-\frac{5}{7}$ (c) $\frac{1}{2}$ (d) $-\frac{7}{10}$ (v) $\frac{7}{15}$

X. Convert each of the following decimal fractions in the form $\frac{p}{q}$, where p and q are both integers, but q is not zero: (a) 0.32 (b) 0.42 (c) 0.85 (d) 1.875 (e) 0.4375 (f) $3.\dot{7}$ (g) $1.6\dot{4}$ (h) $5.\overline{23}$ (i) $7.11\dot{3}$ (j) $8.9\overline{505}$

We will continue this series later…

Regards,

Nalin Pithwa