2.

Introduction to Set Theory

------------------------------------------------------------------------------------------------
● Syllabus
Concept of Sets: Notation – subset, superset, Empty set, Universal set. Examples.
Operation on Sets: Union – Intersection – Complementation – Difference – Symmetric
difference – problems relating simple set identities.
Definition of power set, Cartesian product of finite number of sets, simple problems,
cardinality of a set, Finite and Infinite sets.
------------------------------------------------------------------------------------------------
2.1 Concept of Sets
Definition: An “Unordered collection” of “well-defined objects” is known as Set.
A = {1,2,3} = {3,2,1} #Unordered
1∈A,α∉A #well-defined (we can clearly check membership)

Elements of a Set: The objects contained by a set are called the elements of the set.
If A = {1,2,3}, then 1,2,3 are elements of the set.
We can say “1 belongs to set A” represented as 1 ∈ A

Cardinality of a set: The cardinality of a set is the total number of unique elements in a set.
Example:
A = {1,6,7,8,9}
The cardinality of a set is: n(A) or |A| = 5

Examples of set:
1. Let X = {apple,tomato, orange}. Here, orange ∈ X, but potato ∉ X.
2. X = {2n : n is an integer}
3. The empty set, denoted ∅, is the set that has no element.
4. N := {1, 2, . . .}, the set of Natural numbers;
5. W := {0, 1, 2, . . .}, the set of whole numbers
6. Z := {0, 1, −1, 2, −2, . . .}, the set of Integers;
𝑝
7. Q := { 𝑞 : p, q ∈ Z, q ≠ 0}, the set of Rational numbers;
8. R := the set of Real numbers; and
9. C := the set of Complex numbers.

2.1.1 Representation of Sets

There are two ways to express sets:
1. Roster Form (or Tabular Form)
Example :- A = { a, o, i, u, e }
S = { -1 , 1}
P = {red, blue, green}
Introduction to Set Theory | 1
 2. Set Builder Form
M = {x : x is a natural number and 3 < x < 10}
is read as “the set of all x such that x is a natural number and x lies between 3 and 10.”
Hence, the numbers 4, 5, 6, 7, 8 and 9 are the elements of the set A.

Example :- A = { x : x is a vowel in English alphabet}

S = { x : x²-1 = 0}
P = {x : color pen i have}

Example: “A set which contains all odd numbers less than 10”. Express this statement in Roaster
Form and Set Builder Form.

Solution: P= { 1, 3, 5, 7, 9} #Roaster Form

P = {x | x is the odd numbers less than 10} #Set Builder Form.

2.1.2 Types of Sets

The sets are further divided into categories based on the components or types of elements they
contain. Basic set theory distinguishes between the following types of sets:

Finite Set: The set with a finite number of elements

is called a finite set.

Infinite Set: The set with an infinite number of

elements is called an infinite set.

Empty set / Null Set / Void Set: The set which has no elements is said to be an empty set;
represented as { } or ϕ.
Ex- A = {x : x is a student presently studying in semester 3 and 5}

Singleton set: The set containing only one element is a singleton set.
Ex-
P = {x | x is even prime number}
P = {x | x is natural numbers less than 2}

Subset (⊆): A is a subset of B when all of the elements of set A

belong to set B.
B = {1,2,3,4,5}
A = {1,2,3}
Hence, A⊆B

2018301|Discrete Mathematics Lecture Notes|GP Muz.|2023| 2

 - A ⊆ B if a ∈ A ⇒ a ∈ B
- If A is not a subset of B we write it as A ⊄ B.
- Every set is a subset of itself
- An empty Set is a subset of every set.

Proper Subset: If a subset has fewer elements than the original set then it is called the proper
subset. For example, in set A = {1, 2} and B = {1, 2, 3}, the subset A doesn’t contain all the
elements of the original set B, hence A ⊂ B.

Superset: A set A is a superset of another set B if all elements of the set B are elements of the set
A. The superset relationship is denoted as A⊃B.

Equal Set: If two sets have the same elements, they are
equal.
Here all the elements of A and B are the same, or we can
say that A is the subset of B and B is a subset of A, So
A=B.

Power Set: Let X be a set. Then, the set that contains all subsets of X is called the power set of X
|𝑥|
and is denoted by P(X) or 2 .
|𝑥|
Cardinality of Power Set |P(A)| = 2 , where |x| means no. of elements in set X.
Let X = {x, y, z}. Then P(X) = {∅, {x}, {y}, {z}, {x, y}, {x, z}, {y, z}, {x, y, z}}.

Universal Set: Any set that contains all the sets under
discussion is referred to as a universal set.
U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

Venn diagrams are the ways of pictorially describing sets.

Introduction to Set Theory | 3

2.2 Operations on Sets
The following are the four most commonly used set operations:
i) Union of Sets ( ∪ ) ii) Intersection of Sets ( ∩ ) iii) Difference of sets ( – )
iv) Complement of Sets ( ′ ) v) Symmetric Difference of Sets (∆,⊕,⊖)

i) Union of Sets ( ∪ )
The union of two sets A and B is the set C which consists of all those
elements which are either in A or in B (including those which are in
both). In symbols, we write A ∪ B = { x : x ∈A or x ∈B }

Example: Let A = {1, 2, 3}, B= {3, 4, 5, 6}. Find A∪B.

Solution: A∪B = {1, 2, 3, 4, 5, 6}.

Some Properties of the Operation of Union

(i) A ∪ B = B ∪ A (Commutative law)
(ii) ( A ∪ B ) ∪ C = A ∪ ( B ∪ C) (Associative law )
(iii) A ∪ ϕ = A (Law of identity element, ϕ is the identity of ∪)
(iv) A ∪ A = A (Idempotent law)
(v) U ∪ A = U (Law of U)

ii) Intersection of Sets ( ∩ )

The intersection of sets A and B is the set of all elements which are
common to both A and B. The symbol ‘∩’ is used to denote the
intersection.
In symbols, we write A ∩ B = {x : x ∈ A and x ∈ B}.

Example: Find the intersection of A = {2, 3, 4} and B = {3, 4, 5}.

Solution : A ∩ B = {3, 4}

Some Properties of Operation of Intersection

(i) A ∩ B = B ∩ A (Commutative law).
(ii) ( A ∩ B ) ∩ C = A ∩ ( B ∩ C ) (Associative law).
(iii) ϕ ∩ A = ϕ, U ∩ A = A (Law of ϕ and U).
(iv) A ∩ A = A (Idempotent law)
(v) A ∩ ( B ∪ C ) = ( A ∩ B ) ∪ ( A ∩ C ) (Distributive law ) i. e.,∩ distributes over ∪

Note: Disjoint Sets: If A and B are two sets such that A ∩ B = ϕ, then
A and B are called disjoint sets.

2018301|Discrete Mathematics Lecture Notes|GP Muz.|2023| 4

iii) Difference of sets ( – )
The difference of the sets A and B in this order is the set of elements
which belong to A but not to B. Symbolically, we write A – B.

Example: Let A = { 1, 2, 3, 4, 5, 6}, B = { 2, 4, 6, 8 }. Find A – B

and B – A.
Solution: A – B = { 1, 3, 5 }, since the elements 1, 3, 5 belong to A
but not to B and
B – A = { 8 }, since the element 8 belongs to B and not to A.
Hence, A – B ≠ B – A.

iv) Complement of Sets ( ′ )

Let U be the Universal set and A a subset of U. Then, the
complement of A is the set of all elements of U which are not
𝑐
the elements of A, denoted by 𝐴 𝑜𝑟 A′, is defined by
A′ = {x : x ∈ U and x ∉ A }. Obviously A′ = U – A.

Example: Let U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} and A = {1, 3,

5, 7, 9}. Find A′.
Solution: We note that 2, 4, 6, 8, 10 are the only elements of U which do not belong to A.
Hence A′ = { 2, 4, 6, 8,10 }.

Some Properties of Complement Sets

1. Complement laws: (i) A ∪ A′ = U (ii) A ∩ A′ = ϕ
2. De Morgan’s law: (i) (A ∪ B)´ = A′ ∩ B′ (ii) (A ∩ B)′ = A′ ∪ B′
De Morgan's Law of Union: ( A ∪ B )′ = A′ ∩ B′.

De Morgan's Law of Intersection: ( A ∩ B )′ = A′ ∪ B′.

3. Law of double complementation : (A′)′ = A

4. Laws of empty set and universal set ϕ′ = U and U′ = ϕ.
These laws can be verified by using Venn diagrams.

Introduction to Set Theory | 5

v) Symmetric Difference of Sets (∆,⊕,⊖)
The set which contains the elements which are either in set A or
in set B but not in both is called the symmetric difference
between two given sets. It is represented by A ⊕ B or A ∆ B or
A ⊝ B and is read as a symmetric difference of set A and B.
Symbolically, A Δ B = (A ∪ B) - (A ∩ B).

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

then A Δ B = {1, 2, 5, 6}

2.3 Cartesian Product of Sets

A Cartesian Product of two sets A and B, written as A ✕ B , is the set containing ordered pair
from A and B. That is, if C = A ✕ B, then each element of C is of the form (x,y), where x ∈ A
and y ∈ B:
A ✕ B = {(x,y) | x ∈ A and y ∈ B}
For Example if set A = {2, 4} and B = {4, 6} then A ✕ B = {(2,4), (2,6), (4,4), (4,6)}.
For example, if A={1,2,3} and B={H,T}, then A ✕ B={(1,H),(1,T),(2,H),(2,T),(3,H),(3,T)}.

2.4 Set Theory Results

n(A ∪ B) = n(A) + n(B) – n(A ∩ B)
n(A ∪ B) = n(A) + n(B) {when A and B are disjoint sets}
n(U) = n(A) + n(B) –n(A∩B) + n((A∪B)’)
n(A∪B) = n(A−B) + n(B−A) + n(A∩B)
n(A−B) = n(A ∪ B) − n(B)
n(A−B) = n(A) − n(A∩B)
n(A’) = n(U) − n(A)
n(PUQUR) = n(P) + n(Q) + n(R) – n(P⋂Q) – n(Q⋂R) – n(R⋂P) + n(P⋂Q⋂R)

------------------------------------------------------------------------------------------------

2018301|Discrete Mathematics Lecture Notes|GP Muz.|2023| 6

 Practice Questions

1. Express these statements in Roaster Form and Set Builder Form.

a. “Positive Odd Numbers less than 20”.
b. “set of Natural Numbers less than 7”.
c. “Set of Vowels in the Alphabet”.
d. “The set of all prime numbers less than 100”.
2. Write the set A = {1, 4, 9, 16, 25, . . . }in set-builder form.
3. Which of the following two sets are equal?
a) A = {1, 2} and B = {1}
b) A = {1, 2} and B = {1, 2, 3}
c) A = {1, 2, 3} and B = {2, 1, 3}
d) A = {1, 2, 4} and B = {1, 2, 3}
4. The symmetric difference of A = {1, 2, 3} and B = {3, 4, 5} is
a) {1, 2} b) {1, 2, 4, 5} c) {4, 3} d) {2, 5, 1, 4, 3}
5. If A = {x : x is an even natural number},
B = {x : x is a natural number and multiple of 5} and
C = {x : x is a natural number and multiple of 10}, then what is the value of A ∩ (B ∪ C)?
(a) {10, 20, 30, …} (b) {5, 10, 15, 20…….}
(c) {2, 4, 6……..} (d) {20, 40, 60, ……….}
6. If a set a Contains 60 elements and another set B contains 70 elements and there are 50
elements in common, then how many elements does A B contain?
(a) 130 (b) 100 (c) 80 (d) 70
7. In a Group of 300 people, 150 can speak French & 200 can speak German. How many can
speak both French & German.
8. If A = {1, 2, 3, 4}, B = {3, 4, 5, 6}, C = {5, 6, 7, 8}. Find A ∪ B ∪ C.
9. If A = {3, 5, 7, 9, 11}, B = {7, 9, 11, 13}, C = {11, 13, 15}. Find A ∩ (B ∪ C).
10. If A = { 1, 2, 3, 4, 5, 6}, B = { 2, 4, 6, 8 }. Find A – B and B – A.
11. If U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} and A = {1, 3, 5, 7, 9}. Find A′.
12. Find the power set of the following set. Set B = {1,2,3,4}.
13. For the set A = {p, q, r, s, t, u, v, w, x, y}, how many elements will the power set have?
14. What is a Universal Set? What are the main set operations? Name them.
15. If the universal set is given by S={1,2,3,4,5,6}, and A={1,2}, B={2,4,5},C={1,5,6} are
three sets, find the following sets:
a. A∪B
b. A∩B
c. A′
d. B′
e. Check De Morgan's law by finding (A∪B)′ and A′∩B′.
f. Check the distributive law by finding A∩(B∪C) and (A∩B)∪(A∩C).

Introduction to Set Theory | 7

 16. Let A and B be two finite sets such that n(A) = 20, n(B) = 28 and n(A ∪ B) = 36, find
n(A ∩ B). Ans: 12
17. If n(A - B) = 18, n(A ∪ B) = 70 and n(A ∩ B) = 25, then find n(B). Ans: 52
18. In a college, 20 professors teach mathematics or physics. If 12 teach maths and 4 teach both
physics and maths, How many teach Physics? Ans: 12
19. In a group of 100 persons, 72 people can speak English and 43 can speak French. How
many can speak English only? How many can speak French only and how many can speak
both English and French? Ans: 57, 28, 15
20. Each student in a class of 40 plays at least one indoor game chess, carrom and scrabble. 18
play chess, 20 play scrabble and 27 play carrom. 7 play chess and scrabble, 12 play scrabble
and carrom and 4 play chess, carrom and scrabble. Find the number of students who play (i)
chess and carrom. (ii) chess, carrom but not scrabble. Ans: 10, 6
21. There are 100 students in a Student Activity Club of which 35 like drawing and 45 like
music. 10 students are interested in both drawing and music. Find the number of students
that like either of them or neither of them. Ans: 30
22. Explain cartesian product of sets with suitable examples.
23. If A = {1,2,3}, B = {3,4,5} and C = {0,2,3}, find (A ∩ B) ✕ C.
24. If A = {1,4}, B = {2,3,6} and C = {2,3,7}, then verify that
A ✕ (B - C) = (A ✕ B) - (A ✕ C).

------------------------------------------------------------------------------------------------

2018301|Discrete Mathematics Lecture Notes|GP Muz.|2023| 8