Set Theory

CHAPTER 2

SET THEORY

Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics. The modern study of set theory was initiated by Cantor and Dedekind in the 1870s. After the discovery of paradoxes in informal set theory, numerous axiom systems were proposed in the early twentieth century, of which the Zermelo– Fraenkel axioms, with the axiom of choice, are the best-known. The language of set theory is used in the definitions of nearly all mathematical objects, such as functions, and concepts of set theory are integrated throughout the mathematics curriculum. Elementary facts about sets and set membership can be introduced in primary school, along with Venn diagrams, to study collections of commonplace physical objects. Elementary operations such as set union and intersection can be studied in this context. More advanced concepts such as cardinality are a standard part of the undergraduate mathematics curriculum. Set theory, formalized using first-order logic, is the most common foundational system for mathematics. Beyond its use as a foundational system, set theory is a branch of mathematics in its own right, with an active research community. Contemporary research into set theory includes a diverse collection of topics, ranging from the structure of the real number line to the study of the consistency of large cardinals.

1. NULL SET In mathematical set s, the null set, also called the empty set, is the set that does not contain anything. It is symbolized or { }. There is only one null set. This is because there is logically only one way that a set can contain nothing. The null set makes it possible to explicitly define the results of operations on certain sets that would otherwise not be explicitly definable. The intersection of two disjoint sets (two sets that contain no elements in common) is the null set. For example: {1, 3, 5, 7, 9, ...} {2, 4, 6, 8, 10, ...} = 2. SINGLETON SET A set having exactly one element . A singleton set is denoted by simplest example of a nonempty set.

and is the

3. FINITE SET Finite sets are sets that has a finite number of members. If the elements of a finite set are listed one after another, the process will eventually “run out” of elements to list.

SET THEORY

ALGEBRA

Example: A = {0, 2, 4, 6, 8, …, 100} C = {x : x is an integer, 1 < x < 10}

4. INFINITE SET An infinite set is a set which is not finite. It is not possible to explicitly list out all the elements of an infinite set. Example: T = {x : x is a triangle} N is the set of natural numbers A is the set of fractions

5. EQUAL SETS: Two sets are equal if they contain the same identical elements. If two sets have only the same number of elements, then the two sets are One-to-One correspondence. Equal sets are One-to-One correspondence but correspondence sets are not always equal sets. Example: Which of the following sets are equal and which ones are One-to-One correspondence ? A = {a , f , j , q } B = {1, 2, 3, 5, 8} C = {x, y,z, w} D = {8, 1, 3, 5, 2} Solution: B and D are equal. They have identical elements. A and C are One-to-One correspondence or matching sets. Each set has 4 elements. They have the same number of elements but not the same elements. B and D are One-to-One correspondence and equal sets. They have the same identical elements.

6. SUBSET

A subset is a portion of a set. is a member of

. If

itself), this is written

is a subset of

is a proper subset of . If

(written

(i.e., a subset other than the set

is not a subset of

notation is generally not used, since cannot be the same.) Some important results on subset 1. Every set is a subset of itself. 2. Every set has empty set as its subset. Management Studies Training Institute Quest for the best Page 2

) iff every member of

, this is written

. (The

automatically means that

and

SET THEORY

ALGEBRA

3. Total number of subsets of a set having n enements is 2n. 7. UNIVERSAL SET A set fixed within the framework of a theory and consisting of all objects considered in this theory. The complement of the universal set is the empty set. 8. POWER SET In mathematics, the power set of a set S is the set of all subsets of S. The cardinality of the power set of S given S is finite is equal to 2n, where n is the cardinality of S. 9. VENN DIAGRAMS Venn diagrams or set diagrams are diagrams that show all hypothetically possible logical relations between a finite collection of sets (groups of things). Venn diagrams were conceived around 1880 by John Venn. They are used in many fields, including set theory, probability, logic, statistics, and computer science.

1. UNION OF SETS The union of two sets A and B is the set of elements, which are in A or in B or in both. It is denoted by A ∪ B and is read ‘A union B’ Example : Given U = {1, 2, 3, 4, 5, 6, 7, 8, 10} X = {1, 2, 6, 7} and Y = {1, 3, 4, 5, 8} Find X ∪ Y and draw a Venn diagram to illustrate X ∪ Y. Solution: X ∪ Y = {1, 2, 3, 4, 5, 6, 7, 8} ←1 is written only once.

2. INTERSECTION OF SETS. he intersection of A and B is written "A ∩ B". Formally: Management Studies Training Institute

Quest for the best Page 3

SET THEORY

• • •

•

ALGEBRA

x is an element of A ∩ B if and only if x is an element of A and x is an element of B. For example: The intersection of the sets {1, 2, 3} and {2, 3, 4} is {2, 3}. The number 9 is not in the intersection of the set of prime numbers {2, 3, 5, 7, 11, …} and the set of odd numbers {1, 3, 5, 7, 9, 11, …}. If the intersection of two sets A and B is empty, that is they have no elements in common, then they are said to be disjoint, denoted: A ∩ B = Ø. For example the sets {1, 2} and {3, 4} are disjoint, written {1, 2} ∩ {3, 4} = Ø.

3. DISJOINT SETS In mathematics two sets are said to be disjoint if they have no element in common. For example, {1, 2, 3} and {4, 5, 6} are disjoint sets. 4. DIFFERENCE OF SETS For two sets A and B , A – B is the set of all those elements of A which do not belong to B. Similarly, B – A is the set of all those elements of B which do not belong to A.

5. COMPLEMENT OF A SET If U is the universal set and a set A is such that A ⊆ U then complement od the set A is defined as U – A and represented as A ‘ or A C. A

U A

Management Studies Training Institute

Quest for the best Page 4

SET THEORY

ALGEBRA

The power set of non-empty set U, set P(U), together with operations union, intersection, difference and complement ( , , c) and their characteristics is called algebra of sets. Let A, B, C be subsets of universal set U. Then follows the laws of the algebra of sets: 1. Commutative Laws A B=B A, A 2. Associative Laws

B=B

A

(A B) C=A (B C), 3. Idempotent Laws

(A

B)

C=A

(B

C)

A A=A, A A=A 4. Distributive Laws A (B C)=(A B) 5. De Morgan Laws

(A

C),

A

A = , A U=U< BR> (A 6. Complement Laws (AC)C=A

(B

C)=(A

B)C =AC

BC,

B)

(A

(A

C)

B)C=AC

BC

(according to definition of union )

(x

PROOF OF LAWS 1. LET US PROVE COMMUTATIVE LAWS: (

x) (x

B or x (

x) (x

A

B)

(x

A or x

A

B)

(x

A and x

B)

A) B)

(according to definition of

intersection) (x B and x A) 2. LET’S PROVE THE ASSOCIATIVE LAW. Therefore, we have to prove these two statements: a)

(A

B)

C

b) A (B C) Let’s prove a).

A (A

(B B)

C), C.

Let x be any element in the set (A

B)

C,

x (A B) C. Management Studies Training Institute Quest for the best Page 5

SET THEORY

ALGEBRA

Then x

A

x

B implies x

A

B and x

So, we have x

C. A and x

A, x

B.

B and x

C.

We can write it on this way: x Therefore, x

A

(B

A and x

A

and x

(B

C,

C).

We see that from x (A B) proven. Let’s prove the statement b). Let x

B

C outcomes x

C). Then x

A and x

B

A

(B

C. From x

C). Statement a) is

B

C outcomes x

C

C.

Now we have shown that x

A, x

Therefore, x

A

C.

Then x

B)

From (A

(A

B and x

B and x

C.

C. Statement b) is proven.

B)

C

A

(B

outcomes (A

B)

C=A

C) and A

C)

(A

B)

4. LETS PROVE NOW DISTRIBUTIVE LAW from

to

, i. e. A

(B

(B

C).

3. LET US PROVE IDEMPOTENT LAWS: (

x) (x

A

A)

x

A or x

A

(

x) (x

A

A)

x

A and x

x A

A x

A

B) (A C) We have to prove following two statements: a)

A

b)

(A

(B B)

C)

(A

(A

C)

B) A

(A (B

C) C).

Management Studies Training Institute

Quest for the best Page 6

(B

C)=(A

B

SET THEORY

ALGEBRA

Let x

A

(B

C). Then x

and x

B

C. If x

Therefore, x If x

B

A or x

A, then x

(A

B)

C, then x

(A

A

B

C, or x is an element in both sets, x

B and x

A

A

C.

C).

B and x

C. Then x

A

B and x

A

C.

So, x (A B) (A C). Statement a) is proven. Let’s prove statement b). Let x

(A

B)

(A

C). Then

If x

A, then x

A

(B

If x

A, then x

B, because x

That means if x

x

A

B and x

A, then x

A

B, and also x

B and x

C, i.e. x

(A

From A

C) and (A

(B

C)

C)

(A

(A B)

C.

C) and statement b) is proven.

Therefore in any case from x statement b) is proven. (B

A

B)

(A

(A

B)

(A

C, because x B

(A

C.

C.

C) outcomes x

B)

A

C)

A

A

(B

(B

C) and

C) outcomes A

C).

5. LET US PROVE DE MORGAN LAWS: A (A

=

,

B)C =AC

A

U=U

BC,

(A

B)C=AC

Each of the sets A and

contains A

(A

)

)

A and (A

BC as a subset,

Since null set is a subset of every set, then The sets U and A are always subsets of A A

(A

U) and U

(A

(A

). Hence A

=

.

U,

U)

But every set is a subset of the universal set, (A definition of equality of two sets follows A Management Studies Training Institute

Quest for the best Page 7

U=U.

U)

U and according to the

SET THEORY

(A

B)c

(according to the definition of complement)

(U\A) Ac (A

ALGEBRA

U\(A

B)

(U\B) Bc

B)c

by the definition of complement

(U\A) Ac

U\(A

B)

(U\B)

Bc

6. LET US PROVE COMPLEMENT LAWS: On the first way let it be A (Ac)c

Ac=S Then A

S and

Ac

S:

(S\Ac)

A On the second way let it be A x

A x

x

x

. Then (

x) x

A or x

A.

Ac

(Ac)c A

x

Ac

x (Ac)c That was the proof. Set operations as union and intersection are defined on the same way on any number of sets. Let F be any number of sets, i.e. F is set which elements are sets. Then union of F is B= A F A, i.e. B= A(A F) the smallest set, which contains all elements from all, sets A from F and nothing else. We can say that more precisely: x B if and only if x is element of at least one member of F. Analogous is defined the intersection of any number of sets, D=

A

F

A,

D=

A(A

F)

Management Studies Training Institute

Quest for the best Page 8

SET THEORY

ALGEBRA

as “the biggest” set that is contained in each set of F. In the other words: y and only if y is element of each element A from F. Accordingly we introduce de Morgans theorems: (

A)C=

AC (A

D, if

F)

( A)C= AC (A F) Accepting the existence of union of any number of sets is so natural that we take it as an axiom. Axiom of union: Let F be non-empty set of sets. Then exist such a set B for which is valid that x

A for at least one A

F

x

B.

MULTIPLE CHOICE QUESTIONS

1. There are 19 hockey players in a club. On a particular day 14 were wearing the prescribed hockey shirts, while 11 were wearing the prescribed hockey pants. None of them was without hockey pant or hockey shirt. How many of them were in complete hockey uniform? (A) 8 (B) 6 (C) 9 (D) 7 2. All the students of a batch opted psychology, Business, or both. 73% of the students opted Psychology and 62% opted Business. If there are 220 students, how many of them opted for both psychology and Business? (A) 60 (B) 100 (C) 70 (D) 77 3. How many ml of water must be added to 48 ml of alcohol to make a solution that contains 25% alcohol? (A) 48 (B) 64 (C) 144 (D) 192 4. In a group of women, 7 have nose studs, 8 have ear rings and 3 have neither. How many of these have both nose studs and ear rings? (A) 0 (B) 2 (C) 3 (D) 7

Management Studies Training Institute

Quest for the best Page 9

SET THEORY

ALGEBRA

5. In a science talent examination, 50% of the candidates fail in mathematics and 50% fail in Physics. If 20% fail in both these subjects, then the percentage who pass in both Mathematics and Physics is (A) 0% (B) 20% (C) 25% (D) 50% 6. In a survey, it was found that 65% of the people watched news on TV, 40% read in newspaper, 25% read newspaper and watched TV. What percentage of people neither watched TV nor read newspaper? (A) 0% (B) 5% (C) 10% (D) 20% 7. In a class 20 opted for Physics, 17 for math, 5 for both and 10 for other subjects. How many students are there in the class? (A) 35 (B) 42 (C) 52 (D) 60 8. In a community of 175 persons, 40 read the Times, 50 read the Samachar and 100 do not read any. How many persons read both the papers? (A) 10 (B) 15 (C) 20 (D) 25 9. 125 aliens descended on a set of film as Extra Terrestrial beings. 40 had two noses, 30 had three legs, 20 had four ears, 10 had two noses and three legs, 12 had three legs and four ears, 5 had two noses and four ears and 3 had all the three unusual features. How many were there without any of these unusual features? (A) 5 (B) 35 (C) 80 (D) None of these. 10. Out of 450 students in a school, 193 students read Science Today, 200 students read Junior Statesman, while 80 students read neither. How many students read both the magazines? (A) 137 (B) 80 (C) 57 (D) 23 11. The employees of a company come to work by one or two methods of transport; car, bus, two- wheeler. It is found that they come to the company in different ways, 40 travel by car, 35 travel by bus, 20 by two-wheeler and 10 by both car and bus. How many employees are there in the company? (A) 75 (B) 85 (C) 95 (D) 80 12. A number of vehicles were tested and the following defects were noted. 12 vehicles had defects in brakes; 10 vehicles had defects in steering; 17 vehicles had defect in lights; 5 vehicles had defects in brakes and steering; 6 vehicles had defects in steering and lights; 7 vehicles had defects in brakes and lights; 2 vehicles had defects in all the three. How many vehicles were tested and how many vehicles had only one defect? (A) 23; 9 (B) 22; 8 (C) 23;8 (D) 22; 9 13. In a class of 250 students, 25 like playing chess, carom and cards,40 are not interested in any of these games. If 40,25& 35 like playing chess, carom and Management Studies Training Institute Quest for the best Page 10

SET THEORY

ALGEBRA

cards only respectively, find the number of students interested in only two of the three games? (A) 75 (B) 85 (C) 95 (D) 80 14. In a sample survey of 1000 people, it was found that 650 read The Hindu, 500 read Indian Express and 400 read News Today. 350 people read both The Hindu and Indian Express.100 read both Indian Express and News Today and 250 read both News and The Hindu. If 50 read all the three papers, how many people do not read any paper at all? How many read only The Hindu? (A) 200; 200 (B) 100; 100 (C) 150 ; 150 (D) 110 ; 100 15. In a survey among a college students it was found that 50 students study Mathematics, 40 Physics, 24 Chemistry, 16 Physics and Chemistry, 22 Mathematics and Physics, 14 Mathematics and Chemistry and 10 students study all three subjects. Find the number of students surveyed. (A) 75 (B) 85 (C) 95 (D) 72 Answer Keys 1 B 2 D 1 1

B

1 2

A

3

C

4

C

5

B

1 3

B

1 4

B

1 5

D

6

Management Studies Training Institute

Quest for the best Page 11

D

7

B

8

B

9

1 0

D