Notes I: Sets and Functions: Solutions

Problem 1:

If \{ A_{i}\} and \{ B_{j}\} are two classes of sets such that \{ A_{i}\} \subseteq \{ B_{j}\}, prove that \bigcup_{i}A_{i} \subseteq \bigcup_{i}B_{i} and \bigcap_{j}B_{j} \subseteq \bigcap_{i}A_{i}.

Answer 1:

The first part is clear as the hypothesis says the set of sets \{ A_{i}\} is a subset of the set of sets \{ B_{j}\}. So, quite clearly \bigcup_{i}A_{i} \subseteq \bigcup_{j}A_{j}. For the second part, we can use the generalized De Morgan’s laws. (Note: if you try to derive it straight, you will prove exactly what is opposite of the required result :-)). For the second part note that X \subseteq Y \Longleftrightarrow Y^{'} \bigcap X^{'}. Using the result in the first part, that is, consider \bigcup_{i}A_{i} \subseteq \bigcup_{j}A_{j} and now take the complement of both sides so we get: \bigcup_{i}A_{i} \subseteq \bigcup_{j}B_{j} \Longleftrightarrow (\bigcup_{j}B_{j})^{'} \subseteq (\bigcup_{i}A_{i})^{'}, that is, \bigcap_{j}B_{j} \subseteq \bigcap_{i}A_{i}. QED.

Problem 2:

The difference between two sets A and B, denoted by A-B, is the set of all elements in A and not in B, thus A-B = A \bigcap B^{'}. Show the following:

(a)A-B = A - (A \bigcap B) = (A \bigcup B) -B.

Answer (a): A-B is the set of elements x \in A, but not in B. Hence, A-B = A-(A \bigcap B), simply by definition. Again, if we consider elements in A or B or both, and then take away elements of B, we are just left with elements of A only, but not of B. That is, A-B = A-(A \bigcap B) = (A \bigcup B) - B. QED. ps: A venn diagram may help visualize v well.

(b) TPT: (A-B) - C = A - (B \bigcup C) (PS: a Venn diagram can help visualize and perhaps, guide the writing of the proof also).

Let x \in A-B, but x \notin C. Then, x \in A, but x \notin B, or x \notin C, or not in both B and C. That is, x \in A-(B \bigcup C). By reversing the argument, we get the other subset relationship. Hence, (A-B)-C = A- (B \bigcap C). QED.

(c) TPT: A - (B-C) = (A-B) \bigcup (A \bigcap C).

Answer (c): Let x \in A-(B-C). That is, x \in A and x \notin (B-C). That is, x \in A, x \notin B, x \in C. That is, x \in A, x \notin B, or x could be both in A and C. That is, x \in (A-B) \bigcup (A \bigcap C). Simply reversing the arguments, we get the reverse subset relation. Hence, the two sets are equal. Hence, A-(B-C) = (A-B) \bigcup (A \bigcap C). QED.

(d) TPT: (A \bigcup B) - C = (A-C) \bigcup (B-C).

answer (d): let x \in A\bigcup B, but x \notin C. Then, x \in A, or x \in B, or x is an element of both A and B, but x is not an element of C. Which clearly means, x is an element of A but not C, OR x is an element of B but not C. That is, x \in (A-C) \bigcup (B-C) (upon reversing the arguments, we get the other subset relations. Hence, the two sets are equal). QED.

problem (e): TPT: A-(B \bigcup C) = (A-B) \bigcap (A-C) (once again, note that for set theoretic relations with up to three sets, venn diagrams are helpful to visualize and guide the proofs..)

answer (c): let x \in A, but not in B \bigcup C. That is, x is an element of A, but not of B, not of C, or not both of B and C. That is, x is an element of A not of B, and x is an element of A not of C. That is, x \in (A-B) \bigcap (A-C). Reversing the arguments, we get the other subset relationship. Hence, the two sets are equal. Hence, A - (B \bigcup C) = (A-B) \bigcap (B-C). QED.

Problem 3:

The symmetric difference of two sets A and B, denoted by A \triangle B, is defined by A \triangle B = (A-B) \bigcup (B-A); it is the union of the difference of two sets in opposite orders. Prove the following:

3(a) Symmetric difference is associative: A \triangle (B \triangle C) = (A \triangle B) \triangle C.

Answer 3a: please refer a previous blog.

3(b): TPT: A \triangle \phi = A; and A \triangle A = \phi. (this is some sort of ‘existence of additive inverse of ‘in a symmetric relation’).

Answer 3b: both results are obvious from definition.

3(c): TPT: Symmetric difference is commutative operation: A \triangle B = B\triangle A.

answer 3c: By definition, LHS is (A-B)\bigcup (B-A) = (B-A) \bigcup (A-B), which is RHS. Hence, done.

3(d): TPT: Some sort of distributive law: A \bigcap (B \triangle C) = (A \bigcap B) \triangle (A \bigcap C).

answer 3d: Let x \in A, and also simultaneously x \in (B \triangle C). That is, x \in A, and x \notin (B \bigcap C). That is, x \in A, x \notin (A \bigcap B)\bigcap (B \bigcap C). That is, x \in RHS. Reversing the arguments, we get the other subset relation. Hence, the two sets are equal. Hence, we can say “intersection distributes over symmetric difference.” QED.

Problem 4:

A ring of sets is a non-empty class A of sets such that if A and B are in A then A \triangle B is in A and A \bigcap B is also in A. Show that A must contain the empty set, A \bigcup B and A-B. Also, show that if a non empty class of sets contains the union and difference of any pair of the sets, then it is a ring of sets. Also, prove that a Boolean algebra of sets is a ring of sets.

Answer 4(i): TPT: A must also contain the empty set, the set A \bigcup B and the set A-B. As A \triangle B is in A, so also A \triangle A = \phi \in A; now, it is already given that the ring of sets is non-empty, so it contains a non empty universal set also, call it U. We know from problem 2 in this blog that A - B = A \bigcap B^{'}. As U exists, so does B^{'} by definition and so A-B is in A. Also, as A-B exists, A-B^{'} exists in A, but A-B^{'}=A\bigcap B also exists in A. QED.

Answer 4(ii): TPT: If a non empty class of sets contains the union and difference of any pair of the sets, then it is a ring of sets.

Let A be any non-empty class of sets. Clearly, it therefore has a non empty universal set. As \phi \in U, so also \phi is contained in A. Hence, the complement of a set A is also in A. Now, A \bigcup B \in A, so U - (A \bigcup B) is in A, that is, by De Morgan law, B^{'} \bigcap A^{'} is in A. That is, again, A \bigcap B is in A. Now, since A-B is in A, hence, B-A is in A, and since A \bigcup B is in A, then (A-B) \bigcup (B-A) is in A also. Hence, A is a ring of sets.

4(iii) TPT: Show that a boolean algebra of sets is a ring of sets.

Answer 4(iii); Firstly, as a boolean algebra of sets is non-empty, and it also contains the empty set and the Universal set. As A is in A implies that A^{'} is in A, so A \bigcup B^{'} is also in A (by definition of Boolean algebra), but this is precisely that A-B is in A. Now, as A \triangle B = (A-B) \bigcup (B-A) clearly is also in A. Hence, a Boolean algebra of sets is a ring of sets.

Problem 5:

Show that the class of all finite subsets (including the empty set) of an infinite set is a ring of sets but is not a Boolean algebra.

Answer 5:

In problem 4 above, we showed that if a non empty class of sets contains the union and difference of any pair of the sets, then it is a ring of sets. The given class is a subclass of all an infinite set such that it contains finite subsets only; that is, again, we know that finite unions of finite subsets and finite intersections of finite subsets also lie in that subclass, but the complements might be infinite sets so that it need not always be a Boolean algebra of sets.

Problem 6:

Show that the class of all finite unions of closed-open intervals on the real line is a ring of sets but is not a Boolean algebra of sets.

Answer 6:

Same reasoning as above tells us that it is indeed a ring of sets; but consider for example the closed-open interval [a,b), the complement of this is not in that class as it is an infinite interval so that it is not a Boolean algebra of sets.

Problem 7:

Assuming that the Universal set U is non empty, show that Boolean algebras of sets can be described as rings of sets which contain U.

Answer 7:

As U \neq \phi, by definition of Boolean algebras, U^{'} is in this class of sets, so that the empty set is also a part of this class of sets. Again, by definition of Boolean algebras, the union of two sets of this class is also in this set so also the intersection of any two sets of this class is also in this class. So, for any two sets A and B, A-B is also in this set (as complement of B exists), and so also, A \triangle B = (A-B) \bigcup (B-A) is also in this set. In other words, this is also a ring of sets.

Regards,

Nalin Pithwa

Set theory: more basic problems to solve and clear and apply

I am producing the list of questions first so that the motivated reader can first read and try them …and can compare with my answers by scrolling down only much later; here we go:

  1. If \{ A_{i}\} and \{ B_{j}\} are two classes of sets such that \{ A_{i}\} \subseteq \{ B_{j}\}, then prove that \bigcup_{i}A_{i} \subseteq \{ B_{j}\} and \bigcap_{j} B_{j} \subseteq \bigcap_{i}A_{i}.
  2. The difference between two sets A and B, denoted by A-B, is the set of elements in A and not in B; thus, A - B = A \bigcap B^{'}. Prove the following simple properties: (a) A-B = A-(A \bigcap B) = (A \bigcup B)-B; (b) (A-B)-C = A-(B \bigcup C); (c) A - (B-C) = (A-B) \bigcup (A \bigcap C); (d) (A \bigcup B) - C = (A-C) \bigcup (B-C); (e) A - (B \bigcup C) = (A-B) \bigcap (A-C)
  3. The symmetric difference of two sets A and B, denoted by A \triangle B, is defined by A \triangle B = (A-B) \bigcup (B-A); it is thus the union of their differences in opposite orders. Prove the following : (a) Symmetric difference is associative : A \triangle (B \triangle C) = (A \triangle B) \triangle C (b) A \triangle \phi=A (c) A \triangle A = \phi (c) Symmetric difference is commutative: A \triangle B = B \triangle A (d) Some sort of distributive rule also holds: A \bigcap (B \triangle C) = (A \bigcap B) \triangle (A \bigcap C)
  4. A ring of sets is a non-empty class A of sets such that if A and B are in A, then A \triangle B and A \bigcap B are also in A. Show that A must also contain the empty set, A \bigcup B, and A-B. Show that if a non-empty class of sets contains the union and difference of sets any pair of its sets, then it is a ring of sets. Prove that a Boolean algebra of sets is a ring of sets.
  5. Show that the class of all finite subsets (including the empty set) of an infinite set is a ring of sets but is not a Boolean algebra of sets.
  6. Show that the class of all finite unions of closed-open intervals on the real line is a ring of sets but is not a Boolean algebra of sets.
  7. Assuming that the universal set U is non-empty, show that Boolean algebras of sets can be described as a ring of sets which contain U.

I will put up my solutions as soon as I can.

Regards,

Nalin Pithwa.

Symmetric difference is associative

We want to show that : A \triangle (B \triangle C) = (A \triangle B) \triangle C

Part I: TPT: LHS  \subset RHS

Proof of Part I: let x \in LHS

Then, x \in A \triangle (B \triangle C). By definition of symmetric difference,

x \in \{ A - (B \triangle C)\} \bigcup \{(B \triangle C) -A \}

Hence, x \in A, x \notin (B \triangle C), OR x \in B \triangle C, x \in A

That is, x \notin A \bigcap (B \triangle C).

Hence, x \notin A, and x \notin B \triangle C

Hence, x \notin A and x \in B \bigcap C.

Hence, x \in (B \bigcap C)-A.

Hence, x \in B, x \in C, but x \notin A.

Therefore, x \in B, but x \notin A \bigcap C. —- Call this I.

Consider y \in (A \triangle B) \triangle C.

Therefore, y \notin (A \triangle B) \bigcap C.

Therefore, y \notin C, and y \notin A \triangle B

Therefore, y \notin C, and y \in A \bigcap B.

Therefore, y \in (A \bigcap B)-C.

Hence, y \in A, y \in B, but y \notin C.

That is, y \in B, y \notin A \bigcap C. Call this II.

From I and II, LHS \subset RHS.

Part II: TPT: RHS \subset LHS.

Quite simply, reversing the above steps we prove part II.

QED.

Cheers,

Nalin Pithwa

What is the use of Mathematics

Mathematics Hothouse

Well, you might be asking this question in high school. You might have found that Math is a lot of formulae and manipulations similar to black magic in Algebra and wild imaginations in Geometry — I mean the proofs. So Math means prove this and that. Right?

I agree to some extent. Initially, it is sort of drab or *mechanical*. But, there is a good analogy. Think how you learnt writing the English alphabet — keep on drawing a big A, retracing it 10 times daily and perhaps, your Mom would have whacked you if you did not want to practise it. But, after you know English, the whole world of opportunities opens up for you; your vistas have widened. Exactly same is the case with Mathematics of high school and junior college. But, of course, there are applications of high school math which you learn later when you pursue…

View original post 565 more words

Probability Theory Primer: part I

Illustrative Example 1:

What is the chance of throwing a number greater than 4 with a fair die whose faces are numbered from 1 to 6?

Solution 1:

There are 6 possible ways in which the die can fall, and of these two are the favourable events required.

Hence, required chance is \frac{2}{6}=\frac{1}{3}.

Illustrative example 2:

From a bag containing 4 white and 5 black balls a man draws 3 at random; what are the odds against these being all black?

Solution 2:

The total number of ways in which 3 balls can be drawn is 9 \choose 3, and the number of ways of drawing 3 black balls is 5 \choose 3; therefore, the chance of drawing 3 black balls is equal to

\frac{{5 \choose 3}}{{9 \choose 3}}=\frac{5.4.3}{9.3.7}=\frac{5}{43}.

Thus, the odds against the event are 37 to 5.

Illustrative example 3:

Find the chance of throwing at least one ace in a single throw with two dice.

Solution 3:

In die games, there is no ace. We can pick up any number as an ace in this question. Once it is chosen, it is fixed.

So, the possible number of cases is 6 \times 6=36.

An ace on one die may be associated with any of the six numbers on the other die, and the remaining five numbers on the first die may each be associated with the ace on the second die; thus, the number of favourable cases is 11.

Therefore, the required probability is \frac{11}{36}.

Illustrative example 4:

Find the chance of throwing more than 15 in one throw with 3 dice.

Solution 4:

A throw amounting to 18 must be made up of 6, 6, 6 and this can occur in one way only; 17 can be made up of 6. 6. 5 which can occur in 3 ways; 16 may be made up of 6, 6, 4 and 6, 5, 5 each of which arrangements can occur in 3 ways.

Therefore, the number of favourable cases is 1+3+3+3, that is, 10.

And, the total number of cases possible is 6^{3}, that is, 216.

Hence, the required probability is \frac{10}{216}=5/108.

Illustrative example 5:

A has 3 shares in a lottery, in which there are 3 prizes and 6 blanks; B has 1 share in a lottery in which there is 1 prize and 3 blanks; show that A’s chance of success is to B’s as 16:7.

Solution 5:

A may draw 3 prizes in one way; A may draw 2 prizes and 1 blank in \frac{3.3}{1.2} \times 6 ways; A may draw 1 prize and 2 blanks in 3 \times \frac{6.5}{1.2} ways; the sum of these numbers is 64, which is the number of ways in which A can win a prize. Also, he can draw 3 tickets in \frac{9.8.7}{1.2.3} ways, that is, 84 ways.

Hence, A’s chance of success is \frac{64}{84} = \frac{16}{21}.

B’s chance of success is clearly \frac{1}{3}.

Therefore, the required ratio is \frac{\frac{16}{21}}{\frac{1}{3}} = \frac{16}{7}.

Tutorial questions:

  1. In a single throw with two dice, find the chances of throwing (a) a five (b) a six.
  2. From a pack of 52 cards, two cards are drawn at random, find the chance that one is a knave and other is a queen.
  3. A bag contains 5 white, 7 black and 4 red balls. Find the chance that 3 balls all drawn at random are all white.
  4. If four coins are tossed, find the chance that there are two heads and two tails.
  5. One of two events must happen; given that the chance of one is two-thirds that of the other, find the odds in favour of the other.
  6. If from a pack four cards are drawn, find the chance that they will be the four honours of the same suit.
  7. Thirteen persons take their places at a round table, show that it is five to one against two particular persons sitting together.
  8. There are three events A, B, C, out of which one must, and only one can happen; the odds are 8 is to 3 against A; 5 to 2 against B; find the odds against C.
  9. Compare the chance of throwing 4 with one die, 8 with two dice and 12 with three dice.
  10. In shuffling a pack of cards, four are accidentally dropped; find the chance that the missing cards should be one from each suit.
  11. A has 3 shares in a lottery containing 3 prizes and 9 blanks; B has 2 shares in a lottery containing 2 prizes and 6 blanks; compare their chances of success.
  12. Show that the chances of throwing six with 4, 3 or 2 dice respectively are as 1:6:16
  13. There are three works, one consisting of three volumes, one of four volumens, and the other of one volume. They are placed on a shelf at random; prove that the chance that the volumes of the same works are all together is \frac{3}{140}.
  14. A and B throw with two dice; if A throws 9, find B’s chance of throwing a higher number.
  15. The letters forming the word Clifton are placed at random in a row; what is the chance that the two vowels come together?
  16. In a hand, what is the chance that the four kings are held by a specified player?

Regards,

Nalin Pithwa.

 

 

 

 

 

Compilation of elementary results related to permutations and combinations: Pre RMO, RMO, IITJEE math

1. Disjunctive or Sum Rule:

If an event can occur in m ways and another event can occur in n ways and if these two events cannot occur simultaneously, then one of the two events can occur in m+n ways. More generally, if E_{i} (i=1,2,\ldots,k) are k events such that no two of them can occur at the same time, and if E_{i} can occur in n_{i} ways, then one of the k events can occur in n_{1}+n_{2}+\ldots+n_{k} ways.

2. Sequential or Product Rule:

If an event can occur in m ways and a second event can occur in n ways, and if the number of ways the second event occurs does not depend upon how the first event occurs, then the two events can occur simultaneously in mn ways. More generally, $if E_{1} can occur in n_{1}, E_{2} can occur in n_{2} ways (no matter how E_{1} occurs), E_{3} can occur in n_{3} ways (no matter how E_{1} and E_{2} occur), \ldots, E_{k} can occur in n_{k} ways (no matter how the previous k-1 events occur), then the k events can occur simultaneously in n_{1}n_{2}n_{3}\ldots n_{k} ways.

)3. Definitions and some basic relations:

Suppose X is a collection of n distinct objects and r is a nonnegative integer less than or equal to n. An r-permutation of X is a selection of r out of the n objects but the selections are ordered. 

An n-permutation of X is called a simply a permutation of X.

The number of r-permutations of a collection of n distinct objects is denoted by P(n,r); this number is evaluated as follows: A member of X can be chosen to occupy the first of the r positions in n ways. After that, an object from the remaining collections of (n-1) objects can be chosen to occupy the second position in (n-1) ways. Notice that the number of ways of placing the second object does not depend upon how the first object was placed or chosen. Thus, by the product rule, the first two positions can be filled in n(n-1) ways,….and all r positions can be filled in

P(n,r) = n(n-1)\ldots (n-r+1) = \frac{n!}{(n-r)}! ways.

In particular, P(n,n) = n!

Note: An unordered selection of r out of the n elements of X is called an r-combination of X. In other words, any subset of X with r elements is an r-combination of X. The number of r-combinations or r-subsets of a set of n distinct objects is denoted by n \choose r (read as ” n ‘choose’ r). For each r-subset of X there is a unique complementary (n-r)-subset, whence the important relation {n \choose r} = n \choose {n-r}.

To evaluate n \choose r, note that an r-permutation of an n-set X is necessarily a permutation of some r-subset of X. Moreover, distinct r-subsets generate r-permutations each. Hence, by the sum rule:

P(n,r)=P(r,r)+P(r,r)+\ldots + P(r,r)

The number of terms on the right is the number of r-subsets of X. That is, n \choose r. Thus, P(n,r)=P(r,r) \times {n \choose r}=r! \times {n \choose r}.

The following is our summary:

  1. P(n,r) = \frac{n!}{(n-r)!}
  2. {n \choose r}=\frac{P(n,r)}{r!}=\frac{n!}{r! (n-r)!}=n \choose {n-r}

4. The Pigeonhole Principle: Basic Version:

If n pigeonholes (or mailboxes) shelter n+1 or more pigeons (or letters), at least 1 pigeonhole (or mailbox) shelters at least 2 pigeons (or letters).

5. The number of ways in which m+n things can be divided into two groups containing m and n equal things respectively is given by : \frac{(m+n)!}{m!n!}

Note: If m=n, the groups are equal (and hence, indistinguishable), and in this case the number of different ways of subdivision is \frac{(2m)!}{2!m!m!}

6. The number of ways in which m+n+p things can be divided into three groups containing m, n, p things severally is given by: \frac{(m+n+p)!}{m!n!p!}

Note: If we put m=n=p, we obtain \frac{(3m)!}{m!m!m !} but this formula regards as different all the possible orders in which the three groups can occur in any one mode of subdivision. And, since there are 3! such orders corresponding to each mode of subdivision, the number of different ways in which subdivision into three equal groups can be made in \frac{(3m)!}{m!m!m!3!} ways.

7. The number of ways in which n things can be arranged amongst themselves, taking them all at a time, when p of the things are exactly alike of one kind, q of them are exactly alike of a another kind, r of them are exactly alike of a third kind, and the rest are all different is as follows: \frac{n!}{p!q!r!}

8. The number of permutations of n things r at a time, when such things may be repeated once, twice, thrice…up to r times in any arrangement is given by: n^{r}. Cute quiz: In how many ways, can 5 prizes be given away to 4 boys, when each boy is eligible for all the prizes? (Compare your answers with your friends’ answers :-))

9. The total number of ways in which it is possible to make a selection by taking some or all of n things is given by : 2^{n}-1

10. The total number of ways in which it is possible to make a selection by taking some or all out of p+q+r+\ldots things, whereof p are alike of one kind, q alike of a second kind, r alike of a third kind, and so on is given by : (p+1)(q+1)(r+1)\ldots-1.

Regards,

Nalin Pithwa.

III. Tutorial problems. Symmetric and alternating functions. RMO and IITJEE math

  1. Simplify: (b^{-1}+c^{1})(b+c-a)+(c^{-1}+a^{-1})(c+a-b)+(a^{-1}+b^{-1})(a+b=c)
  2. Simplify: \frac{(x-b)(x-c)}{(a-b)(a-c)} + \frac{(x-c)(x-a)}{(b-c)(b-a)} + \frac{(x-a)(x-b)}{(c-a)(c-b)}
  3. Simplify: \frac{b^{2}+c^{2}-a^{2}}{(a-b)(a-c)} + \frac{c^{2}+a^{2}-b^{2}}{(b-c)(b-a)} + \frac{a^{2}+b^{2}-c^{2}}{(c-a)(c-b)}
  4. Simplify: \frac{b-c}{1+bc} + \frac{c-a}{1+ca} + \frac{a-b}{1+ab}
  5. Simplify: \frac{a(b-c)}{1+bc} + \frac{b(c-a)}{1+ca} + \frac{c(a-b)}{1+ab}
  6. Factorize: (b-c)^{2}(b+c-2a)+(c-a)^{2}(c+a-2b)+(a-b)^{2}(a+b-2c). Put b-c=x, c-a=y, a-b=zand b+c-2a=y-z
  7. Factorize: 8(a+b+c)^{2}-(b+c)^{2}-(c+a)^{2}-(a+b)^{2}. Put b+c=x, c+a=y, a+b=z.
  8. Factorize: (a+b+c)^{2}-(b+c-a)^{2}-(c+a-b)^{2}+(a+b-c)^{2}
  9. Factorize: (1-a^{2})(1-b^{2})(1-c^{2})+(a-bc)(b-ac)(c-ab)
  10. Express the following substitutions as the product of transpositions: (i) \left(\begin{array}{cccccc}123456\\654321\end{array}\right) (ii) \left(\begin{array}{cccccc}123456\\246135\end{array}\right) (iii) \left(\begin{array}{cccccc}123456\\641235\end{array}\right)

Regards,

Nalin Pithwa.