STUDYPIVOT.

COM
Example : If A = {2, 3, 5, 6} and B = {6, 5, 3, 2} . Then
Set Theory A = B, because each element of A is an element of B and vice-
Introduction versa.
(7) Universal set : A set that contains all sets in a given
A set is well defined class or collection of objects. context is called the universal set.
A set is often described in the following two ways. It should be noted that universal set is not unique. It may
(1) Roster method or Listing method : In this method a differ in problem to problem.
set is described by listing elements, separated by commas, within (8) Power set : If S is any set, then the family of all the
braces {}. The set of vowels of English alphabet may be described subsets of S is called the power set of S.
as {a, e, i, o, u}. The power set of S is denoted by P(S). Symbolically, P(S) =
(2) Set-builder method or Rule method : In this method, {T : T  S}. Obviously  and S are both elements of P(S).
a set is described by a characterizing property P(x) of its elements Example : Let S = {a, b, c}, then P(S) = {  , {a}, {b},
x. In such a case the set is described by {x : P(x) holds} or {x |
{c}, {a, b}, {a, c}, {b, c}, {a, b, c}}.
P(x) holds}, which is read as ‘the set of all x such that P(x) holds’.
Power set of a given set is always non-empty.
The symbol ‘|’ or ‘:’ is read as ‘such that’.
(9) Subsets (Set inclusion) : Let A and B be two sets. If
The set A = {0, 1, 4, 9, 16,....} can be written as
every element of A is an element of B, then A is called a subset of
A = {x 2 | x  Z} . B.
❑ Symbols If A is subset of B, we write A  B, which is read as “A is a
subset of B” or “A is contained in B”.
Symbol Meaning Thus, A  B  a  A  a  B.
 Implies Proper and improper subsets : If A is a subset of B and
 Belongs to A  B, then A is a proper subset of B. We write this as A  B .
AB A is a subset of B The null set  is subset of every set and every set is subset of
 Implies and is implied by
itself, i.e.,   A and A A for every set A. They are called
 Does not belong to
improper subsets of A. Thus every non-empty set has two
s.t.(: or |) Such that
improper subsets. It should be noted that  has only one subset
 For every
 which is improper.
 There exists
iff If and only if All other subsets of A are called its proper subsets. Thus, if
& And A  B, A  B , A   , then A is said to be proper subset of B.
a|b a is a divisor of b Example : Let A = {1, 2} . Then A has  ; {1}, {2}, {1, 2} as
N Set of natural numbers its subsets out of which  and {1, 2} are improper and {1} and
I or Z Set of integers {2} are proper subsets.
R Set of real numbers
C Set of complex numbers Venn-Euler diagrams
Q Set of rational numbers The combination of rectangles and circles are called Venn-
Types of sets Euler diagrams or simply Venn-diagrams.
If A and B are not equal but they have
(1) Null set or Empty set : The set which contains no element some common elements, then to represent U
at all is called the null set. This set is sometimes also called the ‘empty A and B we draw two intersecting circles. A
set’ or the ‘void set’. It is denoted by the symbol  or {}. Two disjoints sets are represented by two
(2) Singleton set : A set consisting of a single element is non-intersecting circles.
called a singleton set. The set {5} is a singleton set.
(3) Finite set : A set is called a finite set if it is either void set
Operations on sets
or its elements can be listed (counted, labelled) by natural number (1) Union of sets : Let A and B be two sets. The union of A
1, 2, 3, … and the process of listing terminates at a certain natural and B is the set of all elements which are in U
number n (say). set A or in B. We denote the union of A and
Cardinal number of a finite set : The number n in the B by A  B , which is usually read as “A AB

above definition is called the cardinal number or order of a finite union B”.
A B
set A and is denoted by n(A) or O(A). Symbolically,
(4) Infinite set : A set whose elements cannot be listed by A  B = {x : x  A or x  B}.
the natural numbers 1, 2, 3, …., n, for any natural number n is (2) Intersection of sets : Let A and B be two sets. The
called an infinite set. intersection of A and B is the set of all those
(5) Equivalent set : Two finite sets A and B are equivalent U
elements that belong to both A and B.
if their cardinal numbers are same i.e. n(A) = n(B). The intersection of A and B is denoted AB

Example : A = {1, 3, 5, 7} ; B = {10, 12, 14, 16} are by A  B (read as “A intersection B”).
A B
equivalent sets, [ O( A) = O(B) = 4] . Thus, A  B = {x : x  A and x  B}.
(6) Equal set : Two sets A and B are said to be equal iff (3) Disjoint sets : Two sets A and B are said to be disjoint,
every element of A is an element of B and also every element of B if A  B = . If A  B  , then A and B are said to be non-
is an element of A. Symbolically, A = B if x  A  x  B. intersecting or non-overlapping sets.
Example : Sets {1, 2}; {3, 4} are disjoint sets.
 STUDYPIVOT.COM
(4) Difference of sets : Let A and B be two sets. The (i) A  B = B  A (ii) A  B = B  A
difference of A and B written as A – B, is the set of all those (iii) AB = BA
elements of A which do not belong to B.
i.e., union, intersection and symmetric difference of two sets
U U are commutative.
A–B B–A
(iv) A − B  B − A (v) A  B  B  A
A B A B i.e., difference and cartesian product of two sets are not
commutative
Thus, A – B = {x : x  A and x  B}
Similarly, the difference B − A is the set of all those elements (4) Associative laws : If A, B and C are any three sets,
then
of B that do not belong to A i.e., B − A = {x  B : x  A} .
(i) (A  B)  C = A  (B  C) (ii) A  (B  C) = (A  B)  C
Example : Consider the sets A = {1, 2, 3} and B = {3, 4, 5} ,
(iii) ( AB)C = A(BC)
then A − B = {1, 2}; B − A = {4, 5} .
i.e., union, intersection and symmetric difference of two sets
(5) Symmetric difference of two sets : Let A and B be are associative.
two sets. The symmetric difference of sets A and B is the set
(iv) ( A − B) − C  A − (B − C) (v)
( A − B)  (B − A) and is denoted by AB . Thus, AB =
( A  B)  C  A  (B  C)
( A − B)  (B − A) = {x : x  A  B} .
i.e., difference and cartesian product of two sets are not
(6) Complement of a set : Let U be the universal set and associative.
let A be a set such that A  U. Then, the complement of A with
(5) Distributive law : If A, B and C are any three sets, then
respect to U is denoted by A or Ac or C(A) or U – A and is
(i) A  (B  C) = (A  B)  (A  C)
defined the set of all those elements of U which are not in A.
(ii) A  (B  C) = (A  B)  (A  C)
Thus, A = {x  U : x  A}. U
A i.e., union and intersection are distributive over intersection
Clearly, x  A  x  A A and union respectively.
Example : Consider U = {1, 2,......,10} (iii) A  (B  C) = ( A  B)  ( A  C)
and A = {1, 3, 5, 7, 9} . (iv) A  (B  C) = ( A  B)  ( A  C)

Then A = {2, 4, 6, 8, 10} (v) A  (B − C) = ( A  B) − ( A  C)

(6) De-Morgan’s law : If A, B and C are any three sets,
Some important results on number of elements then
in sets (i) (A  B) = A  B
(ii) (A  B) = A  B
If A, B and C are finite sets and U be the finite universal set,
(iii) A – (B  C) = (A – B)  (A – C)
then (1) n(A  B) = n(A) + n(B) – n(A  B)
(iv) A – (B  C) = (A – B)  (A – C)
(2) n(A  B) = n(A) + n(B)  A, B are disjoint non-void
(7) If A and B are any two sets, then
sets.
(i) A – B = A  B (ii) B – A = B  A
(3) n(A – B) = n(A) – n(A  B) i.e., n(A – B) + n(A  B) = n(A)
(iii) A – B = A  A  B =  (iv) (A – B)  B = A  B
(4) n(A  B) = Number of elements which belong to exactly
(v) (A – B)  B =  (vi) A  B  B  A
one of A or B = n((A – B)  (B – A)) = n (A – B) + n(B – A)
(vii) (A – B)  (B – A) = (A  B) – (A  B)
[ (A – B) and (B – A) are disjoint] (8) If A, B and C are any three sets, then
= n(A) – n(A  B) + n(B) – n(A  B) = n(A) + n(B) – 2n(A  B) (i) A  (B – C) = (A  B) – (A  C)
(5) n(A  B  C) = n(A) + n(B) + n(C) – n(A  B) – n(B  (ii) A  (B  C) = (A  B)  (A  C)
C) – n(A  C) + n(A  B  C)
Cartesian product of sets
(6) n (Number of elements in exactly two of the sets A, B, C)
= n(A  B) + n(B  C) + n(C  A) – 3n(ABC) Cartesian product of sets : Let A and B be any two non-
empty sets. The set of all ordered pairs (a, b) such that a  A and
(7) n(Number of elements in exactly one of the sets A, B, C) b  B is called the cartesian product of the sets A and B and is
= n(A) + n(B) + n(C)
denoted by A  B.
– 2n(A  B) – 2n(B  C) – 2n(A C) + 3n(A  B  C) Thus, A × B = [(a, b) : a  A and b  B]
(8) n(A  B) = n(A  B) = n(U) – n(A  B) If A =  or B = , then we define A × B = .
(9) n(A  B) = n(A  B) = n(U) – n(A  B) Example : Let A = {a, b, c} and B = {p, q}.
Then A × B = {(a, p), (a, q), (b, p), (b, q), (c, p), (c, q)}
Laws of algebra of sets Also B × A = {(p, a), (p, b), (p, c), (q, a), (q, b), (q, c)}
(1) Idempotent laws : For any set A, we have Important theorems on cartesian product of sets :
(i) A  A = A (ii) A  A = A Theorem 1 : For any three sets A, B, C
(2) Identity laws : For any set A, we have (i) A × (B  C) =(A × B)  (A × C)
(ii) A × (B  C) =(A × B)  (A × C)
(i) A=A (ii) A  U = A
Theorem 2 : For any three sets A, B, C
i.e.,  and U are identity elements for union and intersection
respectively. A × (B – C) = (A × B) – (A × C)
Theorem 3 : If A and B are any two non-empty sets, then
(3) Commutative laws : For any two sets A and B, we
have A×B=B×AA=B
 STUDYPIVOT.COM
Theorem 4 : If A  B, then A × A  (A × B)  (B × A) it should be noted that R is symmetric iff R−1 = R
Theorem 5 : If A  B, then A × C  B × C for any set C. The identity and the universal relations on a non-void set are
Theorem 6 : If A  B and C  D, then A × C  B × D symmetric relations.
Theorem 7 : For any sets A, B, C, D A reflexive relation on a set A is not necessarily symmetric.
(A × B)  (C  D) = (A  C) × (B  D) (3) Anti-symmetric relation : Let A be any set. A relation
Theorem 8 : For any three sets A, B, C R on set A is said to be an anti-symmetric relation iff (a, b)  R
(i) A × (B  C) = (A × B)  (A × C) and (b, a)  R  a = b for all a, b  A.
(ii) A × (B  C) = (A × B)  (A × C) Thus, if a  b then a may be related to b or b may be related
to a, but never both.
Relations (4) Transitive relation : Let A be any set. A relation R on
Definition set A is said to be a transitive relation iff
(a, b)  R and (b, c)  R  (a, c)  R for all a, b, c  A i.e.,
Let A and B be two non-empty sets, then every subset of
A × B defines a relation from A to B and every relation from A to aRb and bRc  aRc for all a, b, c  A.
B is a subset of A × B. Transitivity fails only when there exists a, b, c such that a R b,
Let R  A  B and (a, b)  R. Then we say that a is related b R c but a Rc.
to b by the relation R and write it as a R b . If (a, b)  R , we write Example : Consider the set A = {1, 2, 3} and the relations
it as a R b . R1 = {(1, 2), (1, 3)} ; R 2 = {(1, 2)}; R 3 = {(1, 1)};
(1) Total number of relations : Let A and B be two non- R 4 = {(1, 2), (2, 1), (1, 1)}
empty finite sets consisting of m and n elements respectively.
Then A × B consists of mn ordered pairs. So, total number of Then R1 , R 2 , R 3 are transitive while R 4 is not transitive
subset of A × B is 2mn. Since each subset of A × B defines since in R4 , (2, 1)  R4 ; (1, 2)  R4 but (2, 2)  R4 .
relation from A to B, so total number of relations from A to B is
The identity and the universal relations on a non-void sets
2mn. Among these 2mn relations the void relation  and the
are transitive.
universal relation A × B are trivial relations from A to B.
(5) Identity relation : Let A be a set. Then the relation IA =
(2) Domain and range of a relation : Let R be a relation
{(a, a) : a  A} on A is called the identity relation on A.
from a set A to a set B. Then the set of all first components or
coordinates of the ordered pairs belonging to R is called the In other words, a relation IA on A is called the identity relation
domain of R, while the set of all second components or if every element of A is related to itself only. Every identity relation
coordinates of the ordered pairs in R is called the range of R. will be reflexive, symmetric and transitive.
Thus, Dom (R) = {a : (a, b)  R} and Range (R) = {b : (a, Example : On the set = {1, 2, 3}, R = {(1, 1), (2, 2), (3,
b)  R}. 3)} is the identity relation on A .
It is interesting to note that every identity relation is reflexive
Inverse relation but every reflexive relation need not be an identity relation.
Let A, B be two sets and let R be a relation from a set A to a (6) Equivalence relation : A relation R on a set A is said to
set B. Then the inverse of R, denoted by R–1, is a relation from B be an equivalence relation on A iff
to A and is defined by R −1 = {(b, a) : (a, b)  R} (i) It is reflexive i.e. (a, a)  R for all a  A
Clearly (a, b)  R  (b, a)  R . Also, Dom (R) = Range
–1 (ii) It is symmetric i.e. (a, b)  R  (b, a)  R, for all a, b  A
(R ) and Range (R) = Dom (R −1 )
−1 (iii) It is transitive i.e. (a, b)  R and (b, c)  R  (a, c)  R
for all a, b, c  A.
Example : Let A = {a, b, c}, B = {1, 2, 3} and R = {(a,
1), (a, 3), (b, 3), (c, 3)}. Congruence modulo (m) : Let m be an arbitrary but fixed
integer. Two integers a and b are said to be congruence modulo
Then, (i) R–1 = {(1, a), (3, a), (3, b), (3, c)}
m if a − b is divisible by m and we write a  b (mod m).
(ii) Dom (R) = {a, b, c} = Range (R −1 ) Thus a  b (mod m)  a − b is divisible by m. For
(iii) Range (R) = {1, 3} = Dom (R )−1 example, 18  3 (mod 5) because 18 – 3 = 15 which is divisible
by 5. Similarly, 3  13 (mod 2) because 3 – 13 = –10 which is
Types of relations divisible by 2. But 25  2 (mod 4) because 4 is not a divisor of 25
– 3 = 22.
(1) Reflexive relation : A relation R on a set A is said to be The relation “Congruence modulo m” is an equivalence
reflexive if every element of A is related to itself. relation.
Thus, R is reflexive  (a, a)  R for all a  A.
Example : Let A = {1, 2, 3} and R = {(1, 1); (1, 3)} Equivalence classes of an equivalence relation
Then R is not reflexive since 3  A but (3, 3)  R Let R be equivalence relation in A(  ) . Let a  A . Then
A reflexive relation on A is not necessarily the identity the equivalence class of a, denoted by [a] or {a} is defined as the
relation on A. set of all those points of A which are related to a under the
The universal relation on a non-void set A is reflexive. relation R. Thus [a] = {x  A : x R a}.
(2) Symmetric relation : A relation R on a set A is said to It is easy to see that
be a symmetric relation iff (a, b)  R  (b, a)  R for all a, b  A (1) b  [a]  a  [b]
i.e., aRb  bRa for all a, b  A.
(2) b  [a]  [a] = [b]
 STUDYPIVOT.COM
(3) Two equivalence classes are either disjoint or identical.

Composition of relations
Let R and S be two relations from sets A to B and B to C
respectively. Then we can define a relation SoR from A to C such
that (a, c)  SoR   b  B such that (a, b)  R and (b, c)  S.
This relation is called the composition of R and S.
For example, if A = {1, 2, 3}, B = {a, b, c, d}, C={p, q, r,
s} be three sets such that R = {(1, a), (2, b), (1, c), (2, d)} is a
relation from A to B and S = {(a, s), (b, r), (c, r)} is a relation
from B to C. Then SoR is a relation from A to C given by SoR =
{(1, s) (2, r) (1, r)}
In this case RoS does not exist.
In general RoS  SoR. Also (SoR)–1 = R–1oS–1.

 Equal sets are always equivalent but equivalent sets may

need not be equal set.
 If A has n elements, then P(A) has 2n elements.
 The total number of subset of a finite set containing n
elements is 2n.
 If A1, A2,......, An is a finite family of sets, then their union
n
is denoted by  Ai or A1  A2  A3......  An .
i =1

 If A1, A2, A3 ......., An is a finite family of sets, then their

n
intersection is denoted by  Ai or A1  A2  A3  ........  An .
i =1
 R − Q is the set of all irrational numbers.
 Let A and B two non-empty sets having n elements in
common, then A × B and B × A have n2 elements in common.
 The identity relation on a set A is an anti-symmetric
relation.
 The universal relation on a set A studypivot.comcontaining
at least two elements is not anti-symmetric, because if a  b
are in A, then a is related to b and b is related to a under the
universal relation will imply that a = b but a  b.
 The set {(a, a) : a  A} = D is called the diagonal line of
A  A . Then “the relation R in A is antisymmetric iff
R  R−1  D ”.
 The relation ‘is congruent to’ on the set T of all triangles in
a plane is a transitive relation.
 If R and S are two equivalence relations on a set A , then
R  S is also an equivalence relation on A.
 The union of two equivalence relations on a set is not
necessarily an equivalence relation on the set.
 The inverse of an equivalence relation is an equivalence
relation.