MODULE
SET THEORY, RELATIONS AND FUNCTIONS
SYLLABUS: SET THEORY-Set theory concepts, set operations , characteristic functions, Fuzzy set
theory basics .RELATIONS –Operations on relations, equivalence relations and partitions, partial
orders and ordered sets. Warshalls algorithm. Functions and recursion
Set Theory Origin
George Cantor (1845-1918), a German mathematician, initiated the concept ‘Theory of sets’ or ‘Set
Theory’. While working on “Problems on Trigonometric Series”, he encountered sets, that have
become one of the most fundamental concepts in mathematics. Without understanding sets, it will
be difficult to explain the other concepts such as relations, functions, sequences, probability,
geometry, etc.
Definition of Sets: Set is a well-defined collection of objects or people. The objects in a set are
referred to as elements or members of the set. A set can have finite or infinite elements.
Representation of Sets
Sets can be represented in two ways:
Roster Form or Tabular form
Set Builder Form
Roster Form
In roster form, all the elements of the set are listed, separated by commas and enclosed between
curly braces { }.
Example: If the set A set represents all the leap years between the year 1995 and 2015, then it
would be described using Roster form as: A = {1996, 2000 ,2004, 2008,2012}
Set Builder Form
In set builder form, all the elements have a common property. This property is not applicable to the
objects that do not belong to the set.
Example: If set S has all the elements which are even prime numbers, it is represented as:
S={ x : x is an even prime number} ,where ‘x’ is a symbolic representation that is used to describe the
element.‘:’ means ‘such that’.‘{}’ means ‘the set of all’
So, S = { x :x is an even prime number } is read as ‘the set of all x such that x is an even prime
number’. The roster form for this set S would be S = {2}
Another Example:
F = {p: p is a set of two-digit perfect square numbers}
1
,F = {16, 25, 36, 49, 64, 81}
We can see, in the above example, 16 is a square of 4, 25 is square of 5, 36 is square of 6, 49 is
square of 7, 64 is square of 8 and 81 is a square of 9}. Even though, 4, 9, 121, etc., are also perfect
squares, but they are not elements of the set F, because the it is limited to only two-digit perfect
square.
NOTE
There is no order for elements in the set
In a set the elements are not being repeated
. E.g. If L represents a set that contains all the letters in the word ADDRESS, the proper Roster form
representation would be
L ={A,D,R,E,S }= {S,E,D,A,R} and L≠ {A,D,D,R,E,S,S}
SUBSET
Set A is said to be a subset of Set B if all the elements of Set A are also present in Set B. In other
words, set A is contained inside Set B.
Example: If set A has {X, Y} and set B has {X, Y, Z}, then A is the subset of B because elements of A are
also present in set B.
Subset Symbol: In set theory, a subset is denoted by the symbol ⊆ and read as ‘is a subset of’.
A ⊆ B; which means Set A is a subset of Set B.
Note: A subset can be equal to the set. That is, a subset can contain all the elements that are present
in the set.
Types of Subsets: Subsets are classified as
• Proper Subset • Improper Subsets
A proper subset is one that contains a few elements of the original set whereas an improper subset ,
contains every element of the original set along with the null set.
For example, if set A = {2, 4, 6}, then,
Number of subsets: {2}, {4}, {6}, {2,4}, {4,6}, {2,6}, {2,4,6} and Φ or {}.
Proper Subsets: {}, {2}, {4}, {6}, {2,4}, {4,6}, {2,6}, Improper Subset: {2,4,6}
UNIVERSAL SET
Universal set is a set which contains all the elements or objects of other sets, including its own
elements. It is usually denoted by the symbol ‘U’.
EG: Set A consists of all even numbers such that, A = {2, 4, 6, 8,10 ,…} and set B consists of all odd
numbers, such that, B = {1, 3, 5, 7, 9, …}. The universal set U consists of all natural numbers, such
that, U = {1, 2, 3, 4, 5, 6, 7, 8, 9,10 ,….}.
2
, POWER SET
In set theory, the power set (or power set) of a Set A is defined as the set of all subsets of the Set A
including the Set itself and the null or empty set. It is denoted by P (A). Basically, this set is the
combination of all subsets including null set, of a given set.
NOTE: f the given set has n elements, then its Power Set will contain 2 n elements. It also represents
the cardinality of the power set.
Example: Set A = { a, b, c }
Number of elements: 3
Therefore, the subsets of the set are:
{ } which is the null or the empty set
{ a },{ b },{ c },{ a, b },{ b, c },{ c, a },{ a, b, c }
The power set P(A) = { { } , { a }, { b }, { c }, { a, b }, { b, c }, { c, a }, { a, b, c } }
Now, the Power Set has 23 = 8 elements.
CARTESIAN PRODUCT
Given two non-empty sets P and Q. The Cartesian product P × Q is the set of all ordered pairs of
elements from P and Q, i.e.,
P × Q = {(p, q): p ∈ P, q ∈ Q}
If either P or Q is the null set, then P × Q will also be an empty set, i.e., P × Q = φ
Example 1: A = {1, 2, 3} B = {3, 4}
The Cartesian product of A and B = A × B = {1, 2, 3} × {3, 4} = {(1, 3), (1, 4), (2, 3), (2, 4), (3, 3), (3, 4)}
OTHER TYPE OF SETS
The sets are further categorised into different types, based on elements or types of elements. These
different types of sets in basic set theory are:
Finite set: The number of elements is finite
Infinite set: The number of elements are infinite
Empty set: It has no elements
Singleton set: It has one only element
Equal set: Two sets are equal if they have same elements
Equivalent set: Two sets are equivalent if they have same number of elements
Power set: A set of every possible subset.
Universal set: Any set that contains all the sets under consideration.
3
SET THEORY, RELATIONS AND FUNCTIONS
SYLLABUS: SET THEORY-Set theory concepts, set operations , characteristic functions, Fuzzy set
theory basics .RELATIONS –Operations on relations, equivalence relations and partitions, partial
orders and ordered sets. Warshalls algorithm. Functions and recursion
Set Theory Origin
George Cantor (1845-1918), a German mathematician, initiated the concept ‘Theory of sets’ or ‘Set
Theory’. While working on “Problems on Trigonometric Series”, he encountered sets, that have
become one of the most fundamental concepts in mathematics. Without understanding sets, it will
be difficult to explain the other concepts such as relations, functions, sequences, probability,
geometry, etc.
Definition of Sets: Set is a well-defined collection of objects or people. The objects in a set are
referred to as elements or members of the set. A set can have finite or infinite elements.
Representation of Sets
Sets can be represented in two ways:
Roster Form or Tabular form
Set Builder Form
Roster Form
In roster form, all the elements of the set are listed, separated by commas and enclosed between
curly braces { }.
Example: If the set A set represents all the leap years between the year 1995 and 2015, then it
would be described using Roster form as: A = {1996, 2000 ,2004, 2008,2012}
Set Builder Form
In set builder form, all the elements have a common property. This property is not applicable to the
objects that do not belong to the set.
Example: If set S has all the elements which are even prime numbers, it is represented as:
S={ x : x is an even prime number} ,where ‘x’ is a symbolic representation that is used to describe the
element.‘:’ means ‘such that’.‘{}’ means ‘the set of all’
So, S = { x :x is an even prime number } is read as ‘the set of all x such that x is an even prime
number’. The roster form for this set S would be S = {2}
Another Example:
F = {p: p is a set of two-digit perfect square numbers}
1
,F = {16, 25, 36, 49, 64, 81}
We can see, in the above example, 16 is a square of 4, 25 is square of 5, 36 is square of 6, 49 is
square of 7, 64 is square of 8 and 81 is a square of 9}. Even though, 4, 9, 121, etc., are also perfect
squares, but they are not elements of the set F, because the it is limited to only two-digit perfect
square.
NOTE
There is no order for elements in the set
In a set the elements are not being repeated
. E.g. If L represents a set that contains all the letters in the word ADDRESS, the proper Roster form
representation would be
L ={A,D,R,E,S }= {S,E,D,A,R} and L≠ {A,D,D,R,E,S,S}
SUBSET
Set A is said to be a subset of Set B if all the elements of Set A are also present in Set B. In other
words, set A is contained inside Set B.
Example: If set A has {X, Y} and set B has {X, Y, Z}, then A is the subset of B because elements of A are
also present in set B.
Subset Symbol: In set theory, a subset is denoted by the symbol ⊆ and read as ‘is a subset of’.
A ⊆ B; which means Set A is a subset of Set B.
Note: A subset can be equal to the set. That is, a subset can contain all the elements that are present
in the set.
Types of Subsets: Subsets are classified as
• Proper Subset • Improper Subsets
A proper subset is one that contains a few elements of the original set whereas an improper subset ,
contains every element of the original set along with the null set.
For example, if set A = {2, 4, 6}, then,
Number of subsets: {2}, {4}, {6}, {2,4}, {4,6}, {2,6}, {2,4,6} and Φ or {}.
Proper Subsets: {}, {2}, {4}, {6}, {2,4}, {4,6}, {2,6}, Improper Subset: {2,4,6}
UNIVERSAL SET
Universal set is a set which contains all the elements or objects of other sets, including its own
elements. It is usually denoted by the symbol ‘U’.
EG: Set A consists of all even numbers such that, A = {2, 4, 6, 8,10 ,…} and set B consists of all odd
numbers, such that, B = {1, 3, 5, 7, 9, …}. The universal set U consists of all natural numbers, such
that, U = {1, 2, 3, 4, 5, 6, 7, 8, 9,10 ,….}.
2
, POWER SET
In set theory, the power set (or power set) of a Set A is defined as the set of all subsets of the Set A
including the Set itself and the null or empty set. It is denoted by P (A). Basically, this set is the
combination of all subsets including null set, of a given set.
NOTE: f the given set has n elements, then its Power Set will contain 2 n elements. It also represents
the cardinality of the power set.
Example: Set A = { a, b, c }
Number of elements: 3
Therefore, the subsets of the set are:
{ } which is the null or the empty set
{ a },{ b },{ c },{ a, b },{ b, c },{ c, a },{ a, b, c }
The power set P(A) = { { } , { a }, { b }, { c }, { a, b }, { b, c }, { c, a }, { a, b, c } }
Now, the Power Set has 23 = 8 elements.
CARTESIAN PRODUCT
Given two non-empty sets P and Q. The Cartesian product P × Q is the set of all ordered pairs of
elements from P and Q, i.e.,
P × Q = {(p, q): p ∈ P, q ∈ Q}
If either P or Q is the null set, then P × Q will also be an empty set, i.e., P × Q = φ
Example 1: A = {1, 2, 3} B = {3, 4}
The Cartesian product of A and B = A × B = {1, 2, 3} × {3, 4} = {(1, 3), (1, 4), (2, 3), (2, 4), (3, 3), (3, 4)}
OTHER TYPE OF SETS
The sets are further categorised into different types, based on elements or types of elements. These
different types of sets in basic set theory are:
Finite set: The number of elements is finite
Infinite set: The number of elements are infinite
Empty set: It has no elements
Singleton set: It has one only element
Equal set: Two sets are equal if they have same elements
Equivalent set: Two sets are equivalent if they have same number of elements
Power set: A set of every possible subset.
Universal set: Any set that contains all the sets under consideration.
3
