UNIVERSITY INSTITUTE OF ENGINEERING

CHANDIGARH UNIVERSITY

Bachelor of  Engineering  

Subject name- Discrete Mathematics and
Graph Theory
20 CST-352/20 ITT-352

Introduction to Set Theory

Course Outcome
CO2
Understand the concepts and perform the operations related to sets,
relations and functions
Why to learn Set Theory?
• Set Theory is a tool for formalizing and reasoning about computation.
• It is a source of fundamental ideas in computer science from theory to
practice.
• Knowledge of set theory facilitate your ability to think abstractly.
• Provides the foundation to build a firm understanding and analysis of
new ideas in computer science.
Introduction to Set Theory
• A set is any well-defined collection of “objects”.
• The objects in the collection are called elements of the set.
• If the order of the elements is changed or any element of a set is
repeated, it does not make any changes in the set.
Examples
• A set of all positive integers
• A set of all the planets in the solar system
• A set of all the states in India
• A set of all the lowercase letters of the alphabet
• The collection of pencils in your backpack is a set i.e. Each pencil in
your backpack is an element of the set.
Notation
• Sets are usually designated with capital letters.
• Example: A = {a, e, i, o, u}
• Elements of a set are usually designated with lower case letters.
• In the set A above, the individual elements of the set are designate as,
a, e, i, etc.
Notation
• Example: A = {1,2,3,4,5,6}
• Verbal description of set A is:
⮚A is the set of all integers from 1 to 6, inclusive
• Mathematical inclusion rule for the set A is:
⮚A ={Integers x|1 ≤ x ≤ 6}
• The following notation is used to show set membership:
⮚x € A means that x is a member of the set A
⮚x ∉A means that x is not a member of the set A
Representation of a Set
Sets can be represented in two ways −
• Roster or Tabular Form
• Set Builder Notation
Roaster or Tabular Form
• The set is represented by listing all the elements comprising it.
• The elements are enclosed within braces and separated by commas.
• Example 1 − Set of vowels in English alphabet, A={a,e,i,o,u}
• Example 2 − Set of odd numbers less than 10, B={1,3,5,7,9}
Set Builder Form
• The set is defined by specifying a property that elements of the set have in
common.
• Set builder notation has the general form {variable | descriptive statement}.
• The vertical bar (in set builder notation) is always read as “such that”.
• It is frequently used when the roster method is either inappropriate or
inadequate.
Set Builder Notation
• The set is described as A={x:p(x)}
• Example 1 −
The set {a,e,i,o,u} is written as −
A={x:x is a vowel in English alphabet}
• Example 2 −
The set {1,3,5,7,9} is written as −
B={x:1≤x<10 and (x%2)≠0}
Set Builder Notation
• If an element x is a member of any set S, it is denoted by x∈S and if
an element y is not a member of set S, it is denoted by y∉S.
• Example − If S={1,1.2,1.7,2},1∈S but 1.5∉S
Example - subset
• The set A = {1, 2, 3} is a subset of the set B ={1, 2, 3, 4, 5, 6} because
each element of A is an element of B.
• It is written as A ⊂ B to designate this relationship between A and B.
• We could also write {1, 2, 3} ⊂{1, 2, 3, 4, 5, 6}
Example – not a subset of
• The set A = {3, 5, 7} is not a subset of the set B = {1, 4, 5, 7} because
3 is an element of A but is not an element of B.
• The empty set is a subset of every set, because every element of the
empty set is an element of every other set.
Some Important Sets
• N − the set of all natural numbers ={1,2,3,4,.....}
• Z − the set of all integers ={.....,−3,−2,−1,0,1,2,3,.....}
• Z+ − the set of all positive integers
• Q − the set of all rational numbers
• R − the set of all real numbers
• W − the set of all whole numbers
Basic Operations on Sets
There are three major operations performed on sets that are discussed
below:
• Union of sets (∪)
• Intersection of sets (∩)
• Difference of sets ( – )
Union of Sets
• If two sets A and B are given, then the union of A and B is equal to the
set that contains all the elements, present in set A and set B.
• This operation can be represented as;
A ∪ B = {x: x ∈ A or x ∈ B}
• Where x is the elements present in both the sets A and B.
• Example:
⮚If set A = {1,2,3,4} and B {6,7}
⮚Then, Union of sets, A ∪ B = {1,2,3,4,6,7}
Intersection of Sets
• If two sets A and B are given, then the intersection of A and B is the
subset of universal set U, which consist of elements common to both A
and B.
• It is denoted by the symbol ‘∩’. This operation is represented by:
• A∩B = {x : x ∈ A and x ∈ B}
⮚Where x is the common element of both sets A and B.
⮚The intersection of sets A and B, can also be interpreted as:
Intersection of Sets
• A∩B = n(A) + n(B) – n(A∪B)
⮚n(A) = cardinal number of set A,
⮚n(B) = cardinal number of set B,
⮚n(A∪B) = cardinal number of union of set A and B.
Example: 
• Let A = {1,2,3} and B = {3,4,5}
• Then, A∩B = {3}; because 3 is common to both the sets.
Difference of Sets
• If there are two sets A and B, then the difference of two sets A and B is
equal to the set which consists of elements present in A but not in B.
• It is represented by A-B.
Example
• If A = {1,2,3,4,5,6,7} and B = {6,7} are two sets. Then, the difference
of set A and set B is given by; A – B = {1,2,3,4,5}.
• It can be said that the difference of set A and set B is equal to the
intersection of set A with the complement of set B. Hence,
A−B=A∩B’.
Algebra of sets
Complement Sets
Sets of Sets
Empty Set
To Prove Set Identity
Set Identities
De Morgan’s Law
Solve Examples
Set Identities
Combination of Set
Combination of sets-Okay, so we have sets. Now what can we do with them?
When you first learn about numbers back before kindergarten, the next thing
you learn is how to combine numbers using various operations to produce
other numbers. These include +,−,×,÷,+,−,×,÷, exponents, roots, etc. Sets, too,
have operations that are useful for combining to make other sets. These include

By set operation are use for Combining of set

• Union of sets (∪)
• Intersection of sets (∩)
• Difference of sets ( – )
Types Or Classes of Sets
Sets can be classified into many types. Some of which are discussed as:
• Finite Set
• Infinite Set
• Subset
• Proper Subset
• Universal Set
• Empty or Null Set
Types of Sets
• Singleton Set or Unit Set
• Equal Set
• Equivalent Set
• Overlapping Set
• Disjoint Set
Finite Sets
• Finite sets are sets having a finite or countable number of elements.
• It is also known as countable sets as the elements present in them can
be counted.
• In the finite set, the process of counting elements comes to an end.
• The starting and ending elements are present in the set.
Finite Sets
Example
Consider a set of even natural numbers less than 11
A = {2, 4, 6, 8, 10}
As set A has 5 elements which is a finite number and the elements can
be counted.
Properties of Finite Sets
• A proper subset of a finite set is finite.
• The union of any number of finite sets is finite.
• The intersection of two finite sets is finite.
• The cartesian product of finite sets is finite.
• The cardinality of a finite set is a finite number and is equal to the
number of elements in the set.
• The power set of a finite set is finite.
Infinite Sets
• The elements of infinite sets are endless, that is, infinite.
• If any set is endless from start or end or both sides having continuity
then that set is infinite.
• For example, the set of whole numbers, W = {0, 1, 2, 3, ……..} is an
infinite set as the number of elements is infinite.
• The set of real numbers is an example of uncountable infinite sets.
• The elements of an infinite set are represented by dots as the dots
represent the infinity of the set.
Infinite Sets
Example
The set of integers, Z = {……… -2, -1, 0, 1, 2, ……….} is a countable
infinite set as the number of elements in the set is infinite and its
elements can be put in one-to-one correspondence with the set of natural
numbers.
Properties of Infinite Sets
• The union of any number of infinite sets is an infinite set.
• The power set of an infinite set is infinite.
• The superset of an infinite set is also infinite.
• A subset of an infinite set may or may not be infinite.
• Infinite sets can be countable or uncountable.
• For example, the set of real numbers is uncountable whereas the set
of integers is countable.
Difference between Finite and Infinite sets
Finite Sets Infinite Sets

All finite sets are countable. Infinite sets can be countable or uncountable.

The union of two finite sets is finite. The union of two infinite sets is infinite.

A subset of an infinite set may be finite or

A subset of a finite set is finite.
infinite.

The power set of a finite set is finite. The power set of an infinite is infinite.

Example: Set of even natural numbers less than Example: Set of points on a line, Real numbers,
100, Set of names of months in a year etc.
Notes on Finite Sets and Infinite Sets
• An empty set is a finite set with cardinality equal to zero.
• The cardinality of rational numbers is equal to the cardinality of
natural numbers.
• All finite sets are countable whereas infinite sets may or may not be
countable.
Equal Sets
• Equal sets are sets with the exact same elements.
• Let two sets K = {4, 3, 6, 1} and V = {1, 3, 4, 6}.
• K=V
• Even though the elements are in a different order, they are the same
elements. These sets are equal.
Subset
• A set X is a subset of set Y (Written as X⊆Y) if every element of X is
an element of set Y.
• Here set Y is a subset of set X as all the elements of set Y is in set X.
• Hence, we can write Y⊆X.
• Here set Y is a subset (Not a proper subset) of set X as all the elements
of set Y is in set X. Hence, we can write Y⊆X.
Proper Subset
• The term “proper subset” can be defined as “subset of but not equal
to”.
• A Set X is a proper subset of set Y (Written as X⊂Y) if every element
of X is an element of set Y and |X|<|Y|.
• Here set Y⊂X since all elements in Y are contained in X too and X
has at least one element is more than set Y.
Universal Set
• A universal set is a set which contains all objects under consideration,
including itself.
• It is a collection of all elements in a particular context or application.
• All the sets in that context or application are essentially subsets of this
universal set.
• Universal sets are represented as U.
• For example, if we define U as the set of all living things on planet earth,
the set of all animals is a subset of U.
Empty Set or Null Set
• An empty set contains no elements.
• It is denoted by ∅.
• As the number of elements in an empty set is finite, empty set is a
finite set.
• The cardinality of empty set or null set is zero.
• Example − S={x|x∈N and 7<x<8}=∅
Singleton Set
• Singleton set or unit set contains only one element. A singleton set is
denoted by {s}.
• Example − S={x|x∈N, 7<x<9} = {8}
Equal Set:
• If two sets contain the same elements, they are said to be equal.
Equivalent Set:
• If the cardinalities of two sets are same, they are called equivalent sets. i.e.|A|
=|B|=3
Overlapping Set
• Two sets that have at least one common element are called
overlapping sets.
• In case of overlapping sets −
⮚n(A∪B)=n(A)+n(B)−n(A∩B)
⮚n(A∪B)=n(A−B)+n(B−A)+n(A∩B)
⮚n(A)=n(A−B)+n(A∩B)
⮚n(A)=n(A−B)+n(A∩B)
⮚n(B)=n(B−A)+n(A∩B)
Disjoint Set
• Two sets A and B are called disjoint sets if they do not have even one
element in common.
• Therefore, disjoint sets have the following properties −
⮚n(A∩B)=∅
⮚n(A∪B)=n(A)+n(B)
Venn Diagram

• In Venn diagram a set is represented by a

closed curve usually a circle and its
elements by points within it.
• A statement involving sets can be easily
understood with pictorial representation
of sets.
• The diagram showing these sets is called
the Venn Diagram of that statement.
Cardinality of a Set
• Cardinal numbers are counting numbers, so to find the cardinality of
a set, the number of items in the set must be counted.
• This is a measurement of size or the number of elements within a
specific set.
• The cardinality of a set is notated using the absolute value symbol.
Cardinality of a Set
Here are some examples:
• X = { }, therefore lXl = 0
• W = {walrus}, therefore lWl = 1
• P = {numbers on a phone}, therefore lPl = 10
• C = {x: x > 30}, therefore lCl = ∞
How to Find Cardinality of a Set
• In order to determine the cardinality of a set, one must count the
items in the set.
• A set can never contain a negative number of items.
• The cardinality will always be either zero, infinity, or a positive
whole number.
How to Find Cardinality of a Set
Here is one example that often confuses students:
• T = {-64, -973, -35, -554}, therefore lTl = 4.
• Even though the items in the set are negative, the cardinality is the
count of the number of items in a set and it will always be either 0
or positive.
• There are four negative numbers so there are exactly four elements
in this set.
Power Set
• The power set is a set which includes all the subsets including the
empty set and the original set itself.
• It is denoted by P(A).
• Basically, this set is the combination of all subsets including null set,
of a given set.
• If the given set has n elements, then its Power Set will contain
2n elements.
• It also represents the cardinality of the power set.
Power Set
Example
If set A = {x, y, z} is a set, then all its subsets {x}, {y}, {z}, {x, y}, {y,
z}, {x, z}, {x, y, z} and {} are the elements of power set, such as:
Power set of A,
P(A) = { {x}, {y}, {z}, {x, y}, {y, z}, {x, z}, {x, y, z}, {} }
where P(A) denotes the power set.
Proper Power Set
• The power set P(A) = { { } , { a }, { b }, { c }, { a, b }, { b, c }, {c,
a }, { a, b, c } }
• Now, the Power Set has 2^3 = 8 elements.
• Proper Subset: If A and B are two sets, then A is called the proper
subset of B if A ⊆ B but B ⊇ A i.e., A ≠ B.
• The symbol '⊂' is used to denote proper subset. Symbolically, we
write A ⊂ B.
Cardinality of Power Set
• Cardinality represents the total number of elements present in a set.
• In case of power set, the cardinality will be the list of number of subsets of
a set.
• The number of elements of a power set is written as |P (A)|, where A is any
set.
• If A has ‘n’ elements then the formula to find the number of subsets of a
set in a power set is given by:
• |P(A)| = 2n
Cardinality of Power Set
For example, set A = {1, 2, 3}
• n = number of elements of A = 3
• So, the number of subsets in a power set of A will be:
• Subsets of A = {}, {1}, {2}, {3}, {1,2}, {2,3}, {1,3}, {1,2,3,}
• P|A| = 23 = 8
• Hence, P(A) is {{}, {1}, {2}, {3}, {1,2}, {2,3}, {1,3}, {1,2,3,}}
Properties of Power Set
• It is much larger than the original set.
• The power set of a countable finite set is countable.
• For a set of natural numbers, we can do one-to-one mapping of the
resulted set, P(S), with the real numbers.
• P(S) of set S, if operated with the union of sets, the intersection of sets
and complement of sets, denotes the example of Boolean Algebra.
• The total number of elements of a set is 2n.
Properties of Power Set
• An empty set is a definite element of a power set.
• The power set of an empty set has only one element.
• The power set of an infinite set has infinite number of subsets.
⮚For example, if Set X has all the multiples of 5 starting from 5, then we can
say that Set X has an infinite number of elements.
⮚Though there is an infinite number of elements, a power set still exists for set
X, in this case, it has infinite number of subsets. 
• The power set exists for both finite and infinite sets.
Cartesian product of two sets
The Cartesian Product of two sets P and Q in that order is the set of all
ordered pairs whose first member belongs to the set P and second
member belong to set Q and is denoted by P x Q, i.e.,
P x Q = {(x, y): x ∈ P, y ∈ Q}.  
 For example, if A = {1, 2} and B = {3, 4, 5}, then
the Cartesian Product of A and B is
{(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5)}.
 Inclusion-Exclusion Principle

Inclusion-Exclusion Principle
Principle of Inclusion and Exclusion is an approach which derives the method of finding
the number of elements in the union of two finite sets. This is used for solving
combinations and probability problems when it is necessary to find a counting
method, which makes sure that an object is not counted twice.
Consider two finite sets A and B. We can denote the Principle of Inclusion and
Exclusion formula as follows
Let A, B be any two finite sets. Then n (A ∪ B) = n (A) + n (B) - n (A ∩ B)
Here "include" n (A) and n (B) and we "exclude" n (A ∩ B)
Suppose A, B, C are finite sets. Then A ∪ B ∪ C is finite and n (A ∪ B ∪ C) = n(A) + n(B) +
n(C) - n(A ∩ B) - n(A ∩ C) - n(B ∩ C) + n(A ∩ B ∩ C)
• IN GENERAL,
• n(A1 ⋃ A2 ⋃ A3 ⋃….⋃ An) = Σn(Ai ⋂ Aj) + Σn(Ai ⋂ Aj ⋂ Ak) – ….+ (-1)n-1 n(A1 ⋂ A2 ⋂ A3 ⋂
…⋂An)
 Examples
Example 1:
Among a group of students, 49 study Physics, 37 study English and 21 study Biology. If 9 of these students
study Maths Physics and English, 5 study English and Biology, 4 study Physics and Biology and 3 study
Physics, English and Biology, find the number of students in the group.
Solution:
Let P represent the number of students who study Physics, E represent the number of students who study
English and B represent the number of students who study Biology.
Number of students in the group = n(P⋃E⋃B)
Given n(P) = 49, n(E) = 37, n(B) = 21
n(P⋂E) = 9
n(E⋂B) = 5
n(P⋂B) = 4
n(P⋂E⋂B) = 3
n(P⋃E⋃B) = n(P) + n(E) + n(B) – n(P⋂E) – n(E⋂B) – n(P⋂B) + n(P⋂E⋂B)
= 49 + 37 + 21 – 9 – 5 – 4 + 3
= 92
Examples
Find the number of ways that you can put 7 letters into their respective envelopes such that exactly
3 go into the right envelope?
a) 350
b) 102
c) 315
d) 530
Solution:
Number of ways in which the 3 correct envelopes can be selected= 7C3
= 7×6×5/1×2×3
= 35
Derangement of the remaining 4 envelopes and letters = 9 (derangement value for 4 is 9)
So the total number of ways of arrangement = 9 × 35= 315.
Relevant Books
• Textbooks
⮚ C.L. Liu “Elements of Discrete Mathematics". McGraw Hill, 3rd Edition.
⮚ Santha,"Discrete Mathematics with Graph Theory, Cengage Learning, 1st
Edition.
• Reference Books
⮚ B. Kolaman, and R.C. Busby, “Discrete Mathematical Structures”, PHI, 1st
Edition.
⮚ Gersting, L. Judith “Mathematical Structures for computer Science”, Computer
Science Press.
• Links for e-book:
⮚ http://discrete.openmathbooks.org/pdfs/dmoi-tablet.pdf
References
Link of e-book
https://www.science4all.org/article/duality-in-linear-programming/
http://discrete.openmathbooks.org/pdfs/dmoi-tablet.pdf
Other Resources/webs links :
https://www.javatpoint.com/algebra-of-sets
• https://www.javatpoint.com/principle-of-duality-in-discrete-mathema
tics
• PPT - Discrete Mathematics SETS PowerPoint Presentation, free dow
nload - ID:4004039 (slideserve.com)
• PPT - Discrete Mathematics: Set Operations and Identities PowerPoi
nt Presentation - ID:5559797 (slideserve.com
)
• VEDIOLINK:
• https://www.youtube.com/watch?v=wGLTV8MgLlA&list=PLU6Sqd