Set Theory

• Set are the fundamental discrete structures on which all the discrete structures are built.
Sets are used to group objects together, formally speaking
• “A well-defined, unordered collection of distinct objects (Called elements or members of
a set) of same type”. Here the type is defined by the one who is defining the set. For e.g.
A = {0,2,4,6, ---}, B = {1,3,5, ---}, C= {x| x ∈ Natural number}
• A set is generally denoted usually by capital letter. The objects of a set called the
elements, or members of the set. A set is said to contain its elements. Lower case letters
are generally used to denote the element of the set.
• x ϵ A, means element x is a member of A
• x ∉ A means x is not a member of A
• Cardinality of a set— It is the number of elements present in a Set, denoted like |A|, For
e.g. A = {0,2,4,6}, |A| = 4.
• Representation of set
o Tabular/Roster representation of set- here a set is defined by actually listing its
members. Generally Used when set contains few elements. Used in complex
analysis or large sets. E.g.
▪ A = {a, e, i, o, u}
▪ B = {1, 2, 3, 4}
▪ C = {---- -4, -2, 0, 2, 4, -----}.
o Set Builder representations of set- here we specify the property which the
elements of the set must satisfy. E.g.
▪ A = {x| x is an odd positive number less than 10}
▪ A = {x | x ϵ English alphabet && x is vowel}
▪ B = {x | x ϵ N && x <5}
▪ C = {x | x ϵ Z && x%2 = 0}
 Standard notations

• Set of all Complex number(C) - A complex number is a number that can be expressed in
the form ‘a + bi’, where ‘a’ and ‘b’ are real numbers and ‘i’ is the imaginary unit, that
satisfies the equation i2 = −1. In this expression, ‘a’ is the real part and ‘b’ is the
imaginary part of the complex number.
• Set of all Real number(R) - A real number is a value that represents a quantity along a
continuous line, containing all of the rational numbers and all of the irrational numbers.
• Set of all Rational number (Q) - A rational number is any number that can be expressed
as a fraction p/q of two integers, a numerator p and a non-zero denominator q.
• Set of all Irrational number (R-Q or R/Q or P)- An irrational number is a real
number that cannot be expressed as a fraction i.e. as a ratio of integers.
Therefore, irrational numbers, when written as decimal numbers, do not terminate, nor
do they repeat. E.g. root2.
• Set of all Integer(Z) - An integer is a number that can be written without a fractional
component.
• Set of all Whole number(W) - A natural number. whole number in Science
Expand. whole number. A member of the set of positive integers and zero.
• Set of all-Natural number(N) - A natural number is a number that occurs commonly and
obviously in nature. The set of natural numbers, can be defined as N = {1,2,3, 4.... ∞}
• Finite set - If there are exactly ‘n’ distinct elements in S where ‘n’ is a nonnegative
integer, we say that S is a finite set. For e.g. A = {1,2,3,4} and ‘n’ is the cardinality of S.
• Infinite set – A set contain infinite number of elements is called infinite set, if the
counting of different elements of the set does not come to an end. For e.g. a set of
natural numbers.
• Countable set – A set is said to be countable if there can be a one to one mapping
between the elements of the set and natural numbers. E.g. Set of stars.
• Uncountable set – A set is said to be uncountable if there cannot be a one to one
mapping between the elements of the set and natural numbers. E.g. Set of real
numbers.

Set

Empty Non-Empty

Finite Finite Infinite

Countable Countable Countable Uncountable

Q Which of the following is/are not true? (NET-Dec-2015)

(a)The set of negative integers is countable.
(b)The set of integers that are multiples of 7 is countable.
(c)The set of even integers is countable.
(d)The set of real numbers between 0 and ½ is countable.
(A) (a) and (c) (B) (b) and (d) (C) (b) only (D) (d) only

Q Let N be the set of natural numbers. Consider the following sets,

P: Set of Rational numbers (positive and negative)
Q: Set of functions from {0, 1} to N
R: Set of functions from N to {0, 1}
S: Set of finite subsets of N
Which of the above sets are countable? (GATE-2018) (2 Marks)
(A) Q and S only (B) P and S only
(C) P and R only (D) P, Q and S only
• Null set / empty set - Is the unique set having no elements. its size or cardinality is zero
i.e. |ɸ| = 0. It is denoted by a symbol ɸ or {}. A set with one element is called singleton
set.
• Universal set – if all the sets under investigation are subsets of a fixed set, i.e. the set
containing all objects, in venn diagram it is represented by a rectangle, and it is denoted
by U.
• Subset of a set – If every element of set A is also an element of set B i.e. ∀x(x ∈ A → x ∈
B), then A is called subset of B and is written as A ⊑ B. B is called the superset of A. E.g. A
= {1,2,3,4,5,6} B = {4,5,6}
• Note that to show that A is not a subset of B we need only find one element x ϵ A with x
∉B
• To show that A ⊑ B, show that if x ϵ A, then x ϵ B.

• ɸ ⊑ A Empty set ɸ is a subset for every set

• A ⊑ U every set is a subset of Universal set U
• A ⊑ A every set is a subset of itself.
• Proper subset – if A is a subset of B and A ≠ B, then A is said to be a proper subset of B,
i.e. there is at least one element in B which is not in A. denoted as A ⊂ B.
• Equality of sets – if two sets A and B have the same element and therefore every
element of A also belong to B and every element of B also belong to A, then the set A
and B are said to be equal and written as A=B. i.e. if A ⊑ B and B ⊑ A, then A=B. ∀x(x ∈ A
↔ x ∈ B)
• Power set – let A be any set, then the set of all subsets of A is called power set of A and
it is denoted by P(A) or 2A. If A= {1,2,3}, then P(A) = {ɸ, {1}, {2}, {3}, [1,2}, {2,3}, {1,3},
{1,2,3}}
Cardinality of the power set of A is n, |P(A)|= 2n

• Sets can be represented graphically using Venn diagrams, named after the English
mathematician John Venn, who introduced their use in 1881. In Venn diagrams the
universal set U, which
• Contains all the objects under consideration, is represented by a rectangle. (Note that
the universal set varies depending on which objects are of interest.) Inside this
rectangle, circles or other geometrical figures are used to represent sets. Sometimes
points are used to represent the particular elements of the set. Venn diagrams are often
used to indicate the relationships between sets.

Q The cardinality of the power set of {0, 1, 2 . . ., 10} is _________. (GATE-2015) (1 Marks)
(A) 1024 (B) 1023 (C) 2048 (D) 2043

Q The number of elements in the power set P(S) of the set S= {{∅},1, {2,3}} is: (GATE-1995)
(1 Mark)
a) 2 b) 4 c) 8 d) None of the above

Q The power set of the set {Ф} is: (NET-Dec-2012)

a) {Ф} b) {Ф, {Ф}} c) {0} d) {0, Ф, {Ф}}

Q If ɸ is an empty set. Then | P(P(P(ɸ))) | =______?

a) 1 b) 2 c) 4 d) none of above

Q Which of the following are true?

1) ɸ ϵ A 2) ɸ ⊑ A 3) ɸ ϵ 2A 4) ɸ ⊑ 2A 5) A ϵ 2A 6) A ⊑ 2A

Q For a set A, the power set of A is denoted by 2A. If A = {5, {6}, {7}}, which of the following
options are True. (GATE-2015) (1 Marks)
I) ɸ ∈ 2A II) ɸ ⊑ 2A III) {5, {6}} ∈ 2A IV) {5, {6}} ⊑ 2A
(A) I and III only (B) II and III only (C) I, II and III only (D) I, II and IV only

Q Let P(S) denotes the power set of set S. Which of the following is always true? (GATE-
2000) (2 Marks)
(a) P(P(S)) = P(S) (b) P(S) ∩P(P(S)) = {φ}
(c) P(S) ∩S = P(S) (d) S ∉P(S)
Q let A be a set with n elements. Let C be a collection of distinct subsets of A such that for
any two subsets S1 and S2 in C, either S1 is subset of S2 or S2 is subset of S1. What is the
maximum cardinality of C? (GATE-2005) (2 Marks)
a) n b) n+1 c)2n-1+1 d) n!
 Operation on sets
• Complement of set – set of all x such that x ∉ A, but x ϵ U. Ac = {x | x ∉ A & x ϵ U}
• Union of sets – union of two sets A and B is a set of all those elements which either
belong to A or B or both, it is denoted by A U B. A U B = {x| x ϵ A or x ϵ B}

• Intersection of sets -- intersection of two sets A and B is a set of all those elements
which belong to both A and B, and is denoted by A ⋂ B. A ⋂ B = {x| x ϵ A and x ϵ B}

• Disjoint sets -- Two sets are said to be disjoint if they do not have a common element,
i.e. no element in A is in B and no element in B is in A. A ⋂ B = ɸ

Q The power set of A U B, where A = {2, 3, 5, 7} and B = {2, 5, 8, 9} is (NET-Dec-2012)

a) 256 b) 64 c) 16 d) 4

Q Let S be an infinite set S1, S2…………, Sn be Sets such that S1 U S2 U …U Sn = S Then, (GATE-
1993) (1 Marks)
(a) at least one of the set Si is a finite set
(b) not more than one of the set Si can be finite
(c) at least one of the sets Si is an infinite set
(d) not more than one of the sets Si can be infinite
Q if Ai = {-i, …. -2, -1, 0, 1, 2, ….. i} (NET-July-2018)
then ⋃∞ 𝑖=1 𝐴𝑖 is
a) Z b) Q c) R d) C

Q Consider the following statements?

a) Finite union of finite sets is ________(finite/infinite)
b) Finite union of Infinite sets is ________(finite/infinite)
c) Infinite union of finite sets is ________(finite/infinite)
d) if after finite number of union result is infinite set, then at least of the input set is infinite
(T / F)
e) if after finite number of union result is infinite set, then all of the input set is infinite (T /
F)
f) Finite intersection of finite sets is ________(finite/infinite)
g) Finite intersection of Infinite sets is ________(finite/infinite)
h) Finite union of Infinite sets is ________(finite/infinite)
i) If after finite number of intersection result is infinite set, then at least of the input set is
infinite (T / F)
j) If after finite number of intersection result is infinite set, then all of the input set is infinite
(T / F)
• Set difference – the set difference of two sets A and B, is the set of all the elements
which belongs to A but do not belong to B. (A – B) / (A\B = {x| x ϵ A and x ∉ B}

• Symmetric difference – the symmetric difference of two sets A and B is the set of all the
elements that are in A or in B but not in both, denoted as.
o A ⨁ B = {A U B} -- {A ⋂ B}
o A ⨁ B = {x| (x ϵ A and x ∉ B) or (x ϵ B and x ∉ A)}
o A ⨁ B = {A - B} U {B - A}

Q which of the following is not true?

a) A - B = A ⋂ Bc b) A - (A - B) = A ⋂ B
c) A - (A ⋂ B) = A - B d) A - (A - B) = B

Q If A ⊂ B, then which of the following is not true?

(a) A U B = B (b) A ⋂ B = A
C C
(c) B ⊂ A (d) B – A = ɸ

Q Which the following in not true?

a) If A ⊑ ɸ, then A = ɸ
b) (A ⋂ BC) U (A ⋂ B) = A
c) B U (A ⋂ B) = B
d) (A ⋂ BC) U (A ⋂ B) U (AC ⋂ B) U (AC ⋂ BC) = A ⋂ B

Q Which of the following is true?

(i) (A - B) – C = A – (C – B)
(ii) (A – B) – C = (A - C) – B
(iii) (A - B) – C = A – (B ⋂ C)
(iv) (A ⋂ B) – (B ⋂ C) = {A – (A⋂C)} – (A – B)
a) i & iii b) ii & iv c) i, ii, iv d) ii & iii
Q Let A, B and C be non-empty sets and let X = (A−B) −C and Y=(A−C) −(B−C). Which one of
the following is TRUE? (GATE-2005) (1 Marks)
a) X=Y b) X⊂Y c) Y⊂X d) None of these

Q Let A and B be sets and let Ac and Bc denote the complements of the sets A and B. the set
(a – b) ∪ (b - a) ∪ (a ∩ b) is equal to. (GATE- 1996) (1 Mark)
(a) A ∪ B (b) Ac ∪ bc (c) A ∩ B (d) Ac ∩ bc

Q If P, Q, R are subsets of the universal set U, then (GATE-2008) (1 Marks)

(P ⋂ Q ⋂ R) U (PC ⋂ Q ⋂ R) U QC U RC
(A) Qc U Rc (B) P U Qc U Rc
(C) Pc U Qc U Rc (D) U

Q let p, q and r be sets let @ denotes the symmetric difference operator defined as
P @ q = (p U q) – (p ∩ q)? (GATE-2006) (2 Mark)
I) p @ (q ∩ r) = (p @ q) ∩ (P @ q)
II) p∩ (q @ r) = (p ∩ q) @ (p @ r)
a) I only b) II only c) neither I nor II d) both I and II

Q Let E, F and G be finite sets.

Let X = (E ∩ F) – (F ∩ G) and Y = (E – (E ∩ G)) – (E – F).
Which one of the following is true? (GATE-2006) (2 Mark)
(A) X ⊂ Y (B) X ⊃ Y (C) X = Y (D) X – Y ≠ φ and Y – X ≠ φ

Q Let A and B be sets in a finite universal set U. Given the following: |A – B|, |A ⊕ B|, |A| +
|B| and |A ∪ B| Which of the following is in order of increasing size? (NET-Dec-2016)
a) |A – B| < |A ⊕ B| < |A| + |B| < |A ∪ B|
b) |A ⊕ B| < |A – B| < |A ∪ B| < |A| + |B|
c) |A ⊕ B| < |A| + |B| < |A – B| < |A ∪ B|
d) |A – B| < |A ⊕ B| < |A ∪ B| < |A| + |B|
Q In a class of 200 students, 125 students have taken Programming Language course, 85
students have taken Data Structures course, 65 students have taken Computer Organization
course; 50 students have taken both Programming Language and Data Structures, 35
students have taken both Data Structures and Computer Organization; 30 students have
taken both Programming Language and Computer Organization, 15 students have taken all
the three courses. How many students have not taken any of the three courses? (GATE-2004)
(1 Mark)
(A) 15 (B) 20 (C) 25 (D) 35

Q How many multiples of 6 are there between the following pairs of numbers? (NET-Jan-
2017)
0 and 100 and –6 and 34
a) 16 and 6 b) 17 and 6 c) 17 and 7 d) 16 and 7

Q Consider a set A= {1,2, 3, ……...,1000}. How many members of A shall be divisible by 3 or

by 5 or by both 3 and 5? (NET-Dec-2014)
a) 533 b) 599 c) 467 d) 66

Q The number of integers between 1 and 500 (both inclusive) that are divisible by 3 or 5 or
7 is ______. (GATE-2017) (1 Marks)

Q what is the cardinality of the set of integers X defined below (GATE-2006) (2 Mark)
X = {n| 1<=n<=123, n is not divisible by 2,3 or 5}?
a)28 b)33 c)37 d)44

Q In a college, there are three student clubs, Sixty students are only in the Drama club, 80
students are only in the Dance club, 30 students are only in Maths club, 40 students are in
both Drama and Dance clubs, 12 students are in both Dance and Maths clubs, 7 students
are in both Drama and Maths clubs, and 2 students are in all clubs. If 75% of the students in
the college are not in any of these clubs, then the total number of students in the college is
_____________. (GATE-2019) (2 Mark)
Q Suppose U is the power set of the set S = {1,2,3,4,5,6}. For any T ∈ U, let |T| denote the
number of elements in T and T′ denote the complement of T. For any T, R ∈ U, let T\R be
the set of all elements in T which are not in R. (GATE-2015) (2 Marks)
Which one of the following is true?
A) ∀X∈U, (|X|=|X′|) B) ∃X∈U, ∃Y∈U, (|X|=5, |Y|=5 and X∩Y=ϕ)
C) ∀X∈U, ∀Y∈U, (|X|=2, |Y|=3 and X∖Y=ϕ) D) ∀X∈U, ∀Y∈U, (X ∖ Y= Y′ ∖ X′)

Q Consider the following relation on subsets of the set S of integers between 1 and 2014.
For two distinct subsets U and V of S we say U < V if the minimum element in the symmetric
difference of the two sets is in U. Consider the following two statements: (GATE-2014) (2
Marks)
S1: There is a subset of S that is larger than every other subset.
S2: There is a subset of S that is smaller than every other subset.
Which one of the following is CORRECT?
(A) Both S1 and S2 are true (B) S1 is true and S2 is false
(C) S2 is true and S1 is false (D) Neither S1 nor S2 is true

Q The bit string for the sets, A = {1,3,5,7,9} and B = {1,2,3,4,5} are 1010101010 and
1111100000 respectively. If the universal set is U = {1, 2….,10} is represented 1111111111
which of the following is false?
a) A U B = 1111111010 b) A ⋂ B = 1010100000
c) A – B= 0000001010 d) AC = 0000011111

Q Consider the following statements:

S1: There exists infinite sets A, B, C such that A∩(B∪C) is finite.
S2: There exists two irrational numbers x and y such that (x + y) is rational.
Which of the following is true about S1 and S2? (GATE-2001) (2 Mark)
(a) Only S1 is correct (b) Only S2 is correct
(c) Both S1 and S2 are correct (d) None of S1 and S2 is correct
• Idempotent law
o AUA=A
o A⋂A=A

• Associative law
o (A U B) U C = A U (B U C)
o (A ⋂ B) ⋂ C= A ⋂ (B ⋂ C)

• Commutative law
o AUB=BUA
o A⋂B=B⋂A

• Distributive law
o A U (B ⋂ C) = (A U B) ⋂ (A U C)
o A ⋂ (B U C) = (A ⋂ B) U (A ⋂ C)

• De Morgan’s law
o (A U B) C = AC ⋂ BC
o (A ⋂ B) C = AC U BC

• Identity law
o AUɸ=A
o A⋂ɸ=ɸ
o AUU=U
o A⋂U=A

• Complement law
o A U AC = U
o A ⋂ AC = ɸ
o UC = ɸ
o ɸC = U

• Involution law
o ((A)C) C = A