## 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
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

## Skill Check III: IITJEE Foundation Maths

State whether the following statements are true or false:

1. If $A = \{ x | x = 5n, 5 < n < 10, n \in N\}$, then $n(A)=4$
2. If $n(A) = n(B)$, then $set A \leftrightarrow set B$
3. If Set $A= \{ x | x \in N, x<3\}$, then A is a singleton set.
4. The intelligent students of class VIII form a set.
5. The students passing the half-yearly exams in Class VIII B of school is a set.
6. $A = \{ x | x = p^{3}, p<4, p \in \mathcal{N}\}$ and $\{ x|x = m^{2}, m < 4, m \in \mathcal{N} \}$ are overlapping sets.
7. $A = \{ x | x \in \mathcal{N}\}$ is a subset of $B = \{ x | x in \mathcal{Z}\}$
8. If we denote the universal set as $\Omega = \{ p,q,r,s,t,u,v\}$ and $A = \{ q,u,s,t\}$, then $\overline{A} = \{ p, r, v\}$
9. $A = \{ x | x =2p, p \in \mathcal{N}\}$ and $B = \{ x | x =3p, p \in \mathcal{N}\}$ are disjoint sets.
10. If $A = \{ 2,3,4\}$, then $P(A)= \{ \phi, A, \{ 2\}, \{ 3\}, \{ 4 \}, \{ 2,3\}, \{ 2,4\}, \{ 3,4\}\}$ where $P(A)$ is the power set of set A.

II. If C is a letter in the word down all the subsets of C.

III. Write down the complements of all the 8 subsets of set C above.

IV. If $Q = \{ x : x =a^{2}+1, 2 \leq a \leq 5\}$, what is the power set of Q?

V. If $x = \{ x | x<20, x \in \mathcal{N}\}$, and if $A = \{x | x = 2a, 3 < a < 8, a \in \mathcal{N} \}$, and if $B = \{ x | x = 3b, b < 5, b \in \mathcal{N}\}$, and if $C = \{x | x = c+1, 5 < c < 15, c \in \mathcal{N} \}$, then find : (i) $n(B)$ (ii) $n(C)$ (iii) $\overline{A}$ (iv) $\overline{B}$ (v) $P(B)$

VI. If $A = \{ x| x \in \mathcal{N}, 3 < x < 10\}$, and if $B = \{ x| x =4a-1, a<5, a \in \mathcal{N}\}$ and if $C = \{ x | x = 3a+2, a<7, a \in \mathcal{N}\}$, then confirm the following: (i) the commutative property of the unions of sets B and C (ii) the commutative property of intersection of two sets A and C (iii) the associative property of the union of the sets A, B and C (iv) the associative property of intersection of sets A, B and C.

VII. If $A = \{ x | x \in \mathcal{N}, 4 \leq x \leq 12\}$, and $B = \{ x| x = a+1, a<8, a \in \mathcal{N}\}$, and $C= \{ x| x =2n, 1 < n <7, n \in |mathcal{N}\}$, then find (i) $A-B$ (ii) $B-C$ (iii) $B \bigcap C$ (iv) $A - (B \bigcap C)$ (v) $B - (A \bigcap C)$ (vi) $A-C$ (vii) $A- (B-C)$ (viii) $A- (B \bigcup C)$

VIII. If $\xi = \{ x | x \hspace{0.1in}is \hspace{0.1in} a \hspace{0.1in} letter \hspace{0.1in}of \hspace{0.1in}the \hspace{0.1in} English \hspace{0.1in} alphabet \hspace{0.1in} between \hspace{0.1in} but \hspace{0.1in} not \hspace{0.1in} including \hspace{0.1in} d \hspace{0.1in} and \hspace{0.1in} o\}$, and let $A = \{ l, m , n\}$ and let $B= \{ e,f,g,h,i,j,k,l\}$, and let $C = \{ j,k,l,m\}$, find (i) $\overline{A} \bigcup \overline{B}$ (ii) $\overline{B} \bigcap \overline{C}$ (iii) $A \bigcap C$ (iv) $B - (A \bigcap C)$ (v) $\overline{B-A}$ (vi) Is $(B-C) \subset (B-A)$? (vii) Is $\overline{A} \bigcap \overline{B} = \phi$?

IX. All 26 customers in a restaurant had either drinks, snacks, or dinner. 18 had snacks, out of which 6 had only snacks, 4 had snacks and drinks but not dinner, 2 had drinks and dinner but not snacks, and 3 had snacks and dinner but not drinks. If 14 customers had drinks, find (i) how many customers had all three — drinks, snacks as well as dinner. (ii) how many customers had dinner but neither snacks nor drinks (iii) how many customers had only drinks.

Regards,

Nalin Pithwa

Purva building, 5A
Flat 06
Mumbai, Maharastra 400101
India

## Maths will rock your world — a motivational article

keep dreaming the applications of math…try to count every thing….

Jan 23 2006

A generation ago, quants turned finance upside down. Now they’re mapping out ad campaigns and building new businesses from mountains of personal data

Neal Goldman is a math entrepreneur. He works on Wall Street, where numbers rule. But he’s focusing his analytic tools on a different realm altogether: the world of words.

Goldman’s startup, Inform Technologies LLC, is a robotic librarian. Every day it combs through thousands of press articles and blog posts in English. It reads them and groups them with related pieces. Inform doesn’t do this work alphabetically or by keywords. It uses algorithms to analyze each article by its language and context. It then sends customized news feeds to its users, who also exist in Inform’s system as — you guessed it — math.

How do you convert written words into math? Goldman says it takes a…

View original post 3,400 more words

## A motivation for Math and some Math competitive exams in India

what motivates you to keep going in math?

Sometime back, there was a tremendous publicity in the Indian media to two Fields medallists of Indian origin. They also talked about what motivated them towards Math when they were young. One should  not do Math just lured by its glamorous applications in IT or other engineering disciplines. But, one can develop both aptitude and attitude  towards it if one works from a young age.

What you need is intrinsic motivation. In this context, I like to quote the following words of a famous mathematician:

“And, a final observation. We should not forget that the solution to any worthwhile problem very rarely comes to us easily and without hard work; it is rather the result of intellectual effort of days or weeks or months. Why should the young mind be willing to make this supreme effort? The explanation is probably the instinctive preference for certain values, that is, the attitude…

View original post 214 more words