Chapter 1: Sets

Chapter 1

SETS

Who is the founder of set theory?

Georg Cantor, in full Georg Ferdinand Ludwig Philipp Cantor, (born March 3, 1845, St. Petersburg, Russia—died January 6, 1918, Halle, Germany), German mathematician who founded set theory and introduced the mathematically meaningful concept of transfinite numbers, indefinitely large but distinct from one another.

Between the years 1874 and 1897, the German mathematician and logician Georg Cantor created a theory of abstract sets of entities and made it into a mathematical discipline.

SET THEORY

Definition: Set is a collection of well defined or  well-determined objects or elements or numbers or members or functions .

Well defined means known characteristics and properties clearly expressed, explained, or described.

N.B.:-

(i) Sets, are generally denoted by capital English alphabets like A, B, C, P, Q, R etc.

(ii) Objects,elements,members of a set synonymous terms or similar or homogeneous terms.

(iii) The elements of a set are represented by small letters a,b,c,x,y,z, etc..

(iv) If a is an element of a set A, then a is belongs to A.   i.e., a ∈  A 

(v) If b is not an element of a set A, then b does not belong to A   i.e., b ∉   A

Examples:     

(i) The collection of three boys: Mohan, Ram, Prakash.

(ii) The collection N of all natural numbers.

(iii) The collection R of all real numbers.

(iv) The collection of all first year students of DAV

(v)  The collection of the roots of the equation x²⁷-1=0

But the following collections are not sets.

(i)  The collection of some natural numbers.

(ii) The collection of the politicians of India.

(iii) Collection of good cricket players of India.

These are not sets because the terms ‘some’ in (i) politicians in (ii) and good cricket players in (iii) are not well defined.

Example: Collection of tall students in your school.

It is not a set because tall is not well defined.

Similarly , 

Interesting, honesty, intelligence, better, tall ,etc… are not well defined.

Notations: -

• N: the set of natural numbers
• W: the set of Whole numbers
• I=Z: the set of Integer numbers
• Z⁺: the set of Positive Integer numbers
• Z^- : the set of negative Integer numbers
• Q : the set of Rational numbers
• Q’=T : the set of Irrational numbers
• C: the set of Complex numbers
• ∃ : there exists
• ∄ : there does not exists

Description or Representation of a set:  A set is generally described in two ways.

(1) Roster method / Tabular method / set by extension:

In this method the elements of the set are written within the curly brackets ({  }) and separated by a comma (,).

To write a set in Roster method elements are not to be repeated.

Example:        

(i) Set of all vowels of English alphabets.      =          {a, e, i, o u}

(ii) Set of all primes less than 8 =  {2, 3, 5, 7}

(2) Set Builder Method / Set selector method / method of specification:

It is represented by a symbol or variable that all the elements  of set possess a single common property and within the curly bracket which is not possessed by any elements outside the set.         

i.e., a set is described by a charactering properly of its elements.

Example: (i) The set of all even natural numbers is written by

A = {x|  x = 2n for n Î N}

(ii) The set of all prime numbers in between 5 and 15 is written by

B = { x|  x is a prime no. & 5 < x < 15}

Note:   If an element a  remains in a set A, we say etc. a belongs to A and can be written by x Î A. If a does not remain in A we say a does not belongs to A and is written by x Ï A.

Types of sets:

[1] Empty set / Null set / Void set / Phi set (ɸ):

A set is said to be empty set or null set or void set if it has no element. i.e., ɸ={ }

Example:

(i)  The set of all the months which are of 35 days.

(ii)   {x² | x² < 0}

[2] Singleton Set:

A set consisting of a single element is called a singleton set.

Example:

(i) A= { 5 }

(ii)  B= {Rama}

(iii) Present prime minister of India etc.

[3] Finite set:

A set is said to be finite if it is void set or its elements can be counted by natural numbers for any natural number. n Î N and the counting can be terminated for some n.

Example:

(i)  Set of even prime numbers.

(ii) {Arun, Mohan, Ramesh}

(iii) { 1, 2, 3, 4, -------- 100}

[4] Cardinality of a finite set:

The cardinality or cardinal number of a finite set is defined as the number of elements present in that set.

Cardinality of a set is denoted by n (A) on |A|

[5] Infinite sets:

A set whose elements cannot be listed by the natural numbers for any natural no. nÎN.

Example: A= set of points on a line.

N.B.:- All infinite sets cannot be described in the roster method.

[6] Equivalent sets:

Two finite sets A & B are said to be equivalent if their cardinal numbers are same i.e. n (A) = n (B)

Example: A = {1, 2, 3, 4, 5},  B = {a, b, c, d, e)

[7] Equal sets:

Two sets A and B are said to be equal if every elements of A is an element of B.

Example: {0, 1, 2, 3} = {2, 1, 0, 3}

[8] Subsets & super sets:

Let A and B be two sets such that every element of A is also an element of B, then A is said to be the subset of B and is denoted by AÌ B. and B is called the super set of A and denoted by B É A.

If n(A)=n, then Total No. of Subset of set A = 2ⁿ

Example:

            A = { a, e, i, o, u}

            B = {a, b, c, d, e, --------- x, y, z}

            Hence A Ì B & B É A

Theorem: The empty set (or void set) is a subset of every set. Empty set is represented by f.

Proof: Let A be any set and f must be a member of A .

            Þ  f Í A

Theorem:

The total number of subsets of a finite set containing n elements is 2ⁿ.

Proof: A be a finite set & |A| = n

Consider those subsets of A that have r elements. Since no. of selections or r elements from n different things is

Hence the total no. of subsets is

[9] Proper subset / proper set :

If A Ì B and B contain at least one element that is not in A, then A is called a proper subset of B.

Only itself is not Proper subset.

If n(A)=n, then Total No. of Proper Subset of set A = 2ⁿ-1

Example: A = {1, 2, 3}     B = {1, 2, 3, 4, 5, 6, 7}

Properties : (i) f is subset of every set’

                   (ii) If AÍ B and BÍ A ,then A=B

                   (iii) If A Í B and B Í C then A Í C

                   (iv) A Í AUB , B Í AUB

                   (v) If AÍ B and xÎ A, then x Î B

                   (vi) A Í A

                   (vii) A Ç  B Í A  ,  AÇB Í B

[10] Power set:

            The collection of all the subsets of a set A is called the power set of A. It is denoted by P(A).

Example: A = {a, b, c}

                P(A) = {f, {a}, {b}, {c}, {a,b}, {b,c}, {c, a}, {a, b, c}}

Note:   The cardinality of the power set of a set A having n elements is 2ⁿ.

[11] Universal set  (U  / S  / x / w):

A set that contains all sets in a given context is called the universal set, denoted by E or U.

Example: When we study 2-dimensional co-ordinate geometry, then the set of all the points in xy-plane is the universal set.

 

VENN-DIAGRAMS & OPERATIONS ON SETS

Venn-diagrams:

The graphical representation of a set is called Venn-diagram.

A Venn diagram is an illustration that uses circles to show the relationships among things or finite groups of things. Circles that overlap have a commonality while circles that do not overlap do not share those traits. Venn diagrams help to visually represent the similarities and differences between two concepts.

A diagram used to represent all possible relations of different sets. A Venn diagram can be represented by any closed figure, whether it be a Circle or a Polygon (square, hexagon, etc.). But usually, we use circles to represent each set. 

A large rectangle is used to represent the universal set and it is usually denoted by the symbol E or sometimes U.

All the other sets are represented by circles or closed figures within this larger rectangle.

Every set is the subset of the universal set U.

Operations on sets:

Union f sets:

Let A and B be two sets, then the union of A & B is the set of all those elements which belong to A or to B or to both A and B. It is represented as AÈB.

  

Example: 

Properties:

(1) A È B = B È A           (Commutative law)                      

(2) A Í A È B & B Í A È B

(3) A È A = A (Idempotent law)

(4) A È f = A (Identity law)

(5) A È U = U where U is the universal set.

The union of n sets i.e. A₁, A₂, A₃ ……… A_n is denoted by

A₁ È A₂ È A₃ ---------- È A_n =

(6) AÍ B Þ AUCÍ BUC  then A Í AUC for any C

(7) AUB = B  iff  A Í B

 Intersection of Two sets:

Let A & B are two sets. The intersection of A & B, denoted by A Ç B is a set of all elements those belongs to both A & B.

 Properties of Intersection:

 Facts:

 (1) A Ç B = B Ç A (Commutative law)

 (2) A Ç A = A (Idempotent law)

 (3) A Ç f = f (Identity law)

 (4) A Ç B Í A & A Ç B Í B

 (5) A Ç U = A

Distributive for intersection over union

A È (BÇ C) = (A È B) Ç (A È C)

Distributive property for union over

A Ç (B È C) = (A Ç B) È (A Ç C)

The intersection of n different sets is written by

A₁ Ç A ₂ Ç A₃ ------- Ç A_n = 

Disjoint sets:

If the intersection of two sets A & B is a null set, then we say A & B are two disjoint sets.

Example:

A = {a, b, c}

B = {Rama, Shyama, Gopal}

 Difference of sets:

Difference of sets:

The difference of two sets A & B, denoted by A – B, is the set of all element of A which do not belongs to B.  i.e.  A – B = {x| x Î A and x Ï B}

Example:

A = {1, 2, 3, 4, 5, 6}  B = {2, 5, 7, 11, 12, 13}

A – B = {1, 3, 4, 6}

 

Symmetric Difference of sets:

Let A and B are two sets. Then the symmetric difference of A & B, written by A D B is defined as

i.e. the set of all elements which are not common to both A & B.

Example: A = {1, 2, 3, 4, 5, 6, 7, 8},  B = {5, 7, 8, 10, 11, 12}

A D B = {1, 2, 3, 4, 6, 10, 11, 12}

Note:   A D B = B D A

 Complement of a set (w.r.t. universal set U)

Let U be the universal set & A be any set  st. A Ì C. Then the complement of A with respect to U, denoter by A^c (or A¹) or U –A, is defined as the set of all elements of U which donot belongs to A.

 

Example:

Z = { -----------  -3, -2, -1, 0, 1, 2, 3, ------------}  be the universal set.

A = { ----------  -4, -2, 0, 2, 4, --------------}

Then    A^c = { ------------   -3, -1, 1, 3, -------------}

Properties of complement:

Facts:

1. A Ç A^c = f
2. U^c = f & f^c = U
3. A È A^c = U
4. (A^c) = A
5. Demorgan’s laws

•  (i)  (AÈB)^| = A^| Ç B^|
•  (ii) (A Ç B)^| = A^| È B^|

Practical Problems on Union and Intersection(Applications of Sets)

Daily Life Examples Of Sets

1. In Kitchen. Kitchen is the most relevant example of sets. ...
2. School Bags. ...
3. Shopping Malls. ...
4. Universe. ...
5. Playlist. ...
6. Rules. ...
7. Representative House.   etc…

Cardinality of Finite sets:

If A & B are two finite sets, then the cardinality of A È B is given by

|AÈB| = |A| + |B| - |A Ç B|

Note:  

(1) n(AÈB )= |AÈB| = |A| + |B|  if A Ç B = f, i.e. A & B are two finite disjoint sets.

 (2) n(AÈBÈC)=|AÈBÈC| = |A| + |B| + |C| - |AÇB| - |BÇC| - |CÇA| + |AÇBÇC|

  (3)  n (A – B) = n (A ∪ B) – n (B)

n (B – A) = n (B) – n (A ∩ B)

 (4) n (A ∪ B)′= n (U) – n (A ∪ B) = n (U) – n (A) – n (B) + n (A ∩ B)

 (5)  n ( A ∪ B )' = n ( U) – n ( A ∪ B)

Order pair:

Let A be a set and a, b Î A, then the order pair of a & b in A denoted by (a, b). Here a is called first co-ordinate & b is called the second co-ordinate.

N.B.    In a order pair (a, b), the respective order of the entries is always constant, we can not alter their respective orders. If we do so, it will be an different element.

Cartesian product of two sets:

Definition:

If A and B are two non-empty sets, then their Cartesian product, denoted by A X B is defined to be the set of order pairs as

A X B = {(a, b)  |  x ÎA, b Î B}

Example:  A = {a, b, c}

                  B = {1, 2, 3}

                  A X B = {(a, 1), (a, 2), (a,3), (b,1), (b, 2), (b,3), (b,1), (c, 2), (c, 3)}

Note:  

(1) A X B ¹ B X A is A ¹ B i.e. Cartesian product is not commutative.

(2) If cardinality of A is n and cardinality of B is n then cardinality of     (A X B) is mn.

 (3) A X (B Ç C) = (A X B) Ç (A X C)

 (4) A X (B ÈC) = (A X B) È (A X C)

Solved examples:

Q.1: Prove that A – B = A Ç B^/, where A & B are any two sets.1

Proof:  Let x Î A –B be an arbitrary element.

Û x Î& x Ï B

Û x Î A & x Î B^/

Û x Î AÇB^/

\ A – B Ì A Ç B^/                              ----------- (1)

And A Ç B^/ Ì A – B                          ----------- (2)

From 1 & 2 we have,

A – B = A Ç B^/

Q.2: Prove that A È B = B È A, where A & B are any two sets.

Proof: Let x Î A È B be an arbitrary element.

Now x Î A È B

Û x Î A or x Î B

Û x Î B or x Î A

Û x Î B È A

\ A È B Í B È A                             -------------- (i)

And    B È A Í A È B                       --------------- (ii)

From (i) & (ii), we have

A È B = B È A

Q.3: Prove that A È (B Ç C) =(AÈB) Ç (A È C), for any three sets A, B & C.

Proof. Let x Î A È (B ÇC) be an arbitrary element.

Now x Î A È (B Ç C)

Û x Î A  or x Î (B Ç C)

Û x Î A or (x Î B and x Î C)

Û (x Î A or x Î B) and x Î A or x Î C)

Û x Î A È B and x Î A È C

 Û x Î (A È B) Ç (A È C)

\  A È (BÇC) Í  (A È B) Ç (A È c)                       -------------- (i)

And (A È B) Ç (A È C) = A È (B Ç C)                   -------------- (ii)

From (i) and (ii) we have

A È (BÇC) =  (A È B) Ç (A È c)

Q.4: Prove that A – (A – B) Í B for any two set A & B.

Proof:  Let x Î A – (A –B) be arbitrary.

Þ  x Î A and x Ï (A – B)

Þ  x Î A and (x Ï A and x Î B)

Þ x Î B

Þ A – (A – B) Í B

Q.5: For any three sets A, B and C, prove that  A Ç (B Ç C) = (A Ç B) Ç C

Proof: Let x Î A Ç (B Ç C) be an arbitrary element.

Now x Î A Ç (B Ç C)

Û x Î A and x Î (B Ç C)

Û x Î A and (x Î B and x Î C)

Û (x Î A and x Î B) and x Î C

Û x Î A Ç B) Ç C

\A Ç (B Ç C) Í (A Ç B) Ç C                      ------------ (1)

And (A Ç B) Ç C Í A Ç (B Ç C)                 ------------ (2)

From 1 & 2, we have

A Ç (B Ç C) = (A Ç B) Ç C

Q.6: If A D B = B D C, then prove that A = C for any three set A, B and C.

Proof:  Given that A D B = B D C

Þ (A È B) – (A Ç B) = (B È C) – (B Ç C)

Þ A ÈB = BÈC   and A Ç B = B Ç C

Þ (A ÈB) Ç B^c = (C È B) Ç B^c and A Ç B = B Ç C

Þ (A Ç B^c) È f = (C Ç B^c) È f and A Ç B = B Ç C

Þ (A Ç B^c) = C Ç B^c and A Ç B = B Ç C

Þ A – B = C – B and A Ç B = B Ç C

Þ (A – B) È A Ç B = (C – B) È (B Ç C)

Þ A = C

Q.7: Prove that for any three sets A, B, C

|AÈBÈC| = |A| + |B| + |C| - |A ÇB| - |BÇC| - |CÇA| + |AÇBÇC|

Proof: Let B È C = D

Now    |AÈBÈC|        = |AÈD|

= |A| + |D| - |A Ç D|

= |A| + |BÈC| - |AÇD|

= |A| + |B| + |C| - |BÇC| - |AÇ(BÈC)|

= |A| + |B| + |C| - |BÇC| - |(AÇB) È (AÇC)|

= |A| + |B| + |C| - |BÇC| - {|AÇB| + |AÇC| - |(AÇB) Ç (AÇC)|}

= |A| + |B| + |C| - |BÇC| - |AÇB|-|AÇC| + |AÇBÇC|

Þ |AÈBÈC| = |A| + |B| + |C| - |AÇB| - |BÇC| - |CÇA| + |AÇBÇC|

Q.8: A company must hire 25 programmers to handle systems programming jobs and 40 programmers for applications programming of those hired, 10 will be expected to perform jobs for both types. How many programmers must be hired?

Ans.     A = Set of system programmers hired

            B = Set of application programmers hired.

            According to the question

            |A|  = 25, |B| = 40 ,     |A Ç B| = 10

            The number of programmers that must be hired is

            |A È B| = |A| + |B| - |A Ç B|

            = 20 + 40 – 10 = 55

            Hence 55 programmers must be hired.

Q.9: In a class of 35 students, 17 have taken mathematics, 10 have taken mathematics but not economics. Find the number of students who have taken both mathematics and economics and the number of students who have taken economics but not mathematics. If it is given that each student can have either mathematics or economic or both.

Ans.     Let      

A = Set of students who have taken mathematics.

B = Set of students who have taken economics.

Hence as per question,

|A È B| = 35

|A| = 17

|A – B| = 10

Now    |(A)| = |A – B| + |A Ç B|

Þ 17 = 10 + |A Ç B|

Þ |A Ç B| = 7

Hence 7 students have taken both mathematics and economics.

Now    |A ÈB| = |A| + |B| - |A Ç B|

Þ 35 = 17 + |B| - 7

 

Þ |B| = 35 – 10

= 25

Now   |B| = |B – A| + |A Ç B|

Þ 25 = |B – A| + 7

Þ |B – A| = 25 – 7

= 18

Hence 18 students have taken economics but not mathematics.

Q.10: In a class, 38 students play football. 15 play basketball, 20 play cricket.

In a survey of 60 readers, it was found that 25 read Times of India, 26 read The Hindu, 26 read Indian Express, 9 read both Times of India and The Hindu, 11 both Times of India and Indian Express, 8 read The Hindu and Indian Express and 3 read all the three News Papers. Find the number of readers who read at least one of the three News Papers and also find the no. of people who read only Times of India.

 

Ans:    Let       T = Set of readers who read Times of India.

                        H = Set of readers who read The Hindu.

                        E = Set of people who read Indian Express.

 

According to the question

                        |T| = 25                                          

                        |H| = 26                                                                                  

                        |E| = 26                                                                       

                        |TÇ H| = 9

                        |TÇE| = 11,  |H Ç E| = 8                                            

            &         |TÇHÇE| = 3 

            Now |TÈ H È E| = |T| + |H| + |E| - |TÇH| - |HÇE| - |EÇT| + |TÇHÇE|

                                        = 25 + 26 + 26 – 9 -11 – 8 + 3 = 52

            Thus the number of readers who read at least one, of the three news paper is 52.

            Now the number of readers who read only Times of India

                        = |T| - |TÇH| - |TÇS| + |TÇHÇE|

                        = 25 – 9 -11 + 3 = 8

            Hence 8 readers read only Times of India.

 

Q.11: If A = {1, 2, 3}      B = {4, 5, 6}. Find A X B & B X A

Ans:    A = {1, 2, 3}

            B = {4, 5, 6}

            A X B = {(1, 4), (1, 5), (1, 6), (2, 4), (2, 5), (2, 6), (3, 4), (3, 5), (3, 6)}

            B X A = {(4, 1), (4, 2), (4, 3), (5, 1), (5, 2), (5, 3), (6, 1), (6, 2), (6, 3)}

 

Q.12: Prove that for any three sets A, B, C A X (BÇC) = (A X B) Ç (A X C)

Proof: Let (x, y) Î A x (B Ç c) be an arbitrary order pair.

                  (x, y) Î A X (B Ç C)

            Û  x ÎA  and y Î (B Ç C)

            Û  x ÎA and (y Î B, y Î C)

            Û  (x ÎA ,y ÎB) and (x Î A, y Î C)

            Û  (x, y) Î (A X B) and (x, y) Î (A X C)

            Û  (x, y) Î (A X B) and (x, y) Î (A X C)

            Û  (x, y) Î (A X B) Ç (A X C)

            \  A X (BÇC) Í (A X B) Ç (A X C)                       ------------------- (i)

            And (A X B) Ç (A X C) Í A X (B Ç C)                   ------------------- (ii)

From (i) and (ii) we have

A X (BÇC) = (A X B) Ç (A X C)

Q.13: Prove that A X (B – C) = (A X B) – (A X C) for any three sets A, B & C

Proof:  Let (x, y) Î A X (B – C) be arbitrary (x, y) Î A X (B – C)

            Û  x Î A , y Î (B – C)

            Û  x Î A ,(y ÎB and y Ï C)

            Û  x Î A and y Î B) and (x Î A but y Ï C)

            Û  (x, y) Î A X B and (x, y) Ï A X C

            Û  (x, y) Î (A X B) – (A X C)

            \   A X (B – C) Í (A X B) – (A X C)                      --------------- (1)

            And (A X B) – (A X C) Í A X (B – C)                     --------------- (2)

            From 1 and 2, we have,

            A X (B – C) = (A X B) – (A X C)