Elementary mathematics –Set, Relations and Functions

NDA
Set - well-defined collection of objects

Representation of a Set

 Descriptive form - In descriptive form, a set is described in words

 Set Builder form or ruler form - In set builder form, all the elements are
described by a rule.
 Roster or Tabular form - A set can be described by listing all the elements of
the set.

Types of Sets
 Empty of Null Set
A set consisting of no element is called the empty set or null set or void set.
Symbol - ∅ or { }.
Important Notes of Empty Set
 Empty Set is also a Finite Set

 Singleton Set
A set which has only one element

 Finite and Infinite Set

A set with finite number of elements
A set which is not finite is infinite

 Equivalent Sets (A ≈ B )
Two finite sets A and B are said to be equivalent if they contain the same number of
elements.
If A and B are equivalent sets , then n(A) = n(B)
Condition for a equivalent Set: n(A) = n(B)

 Equal and Unequal Set

Two sets are said to be equal ( A = B ) if they contain exactly the same elements,
otherwise they are said to be unequal ( A ≠ B ).

Important Note for equivalent and equal sets

 Equal sets are equivalent sets but equivalent sets need not be equal sets.
 Elementary mathematics –Set, Relations and Functions
NDA
 Universal set (U)
A set which contains all the elements of all the sets under consideration of a another set

 Subset A ⊆ B
If every element of A is also an element of B, then A is called a subset of B then, A ⊆ B.
Condition for the two sets A and B is to be a Subset: n(A) ≤ n(B)

Important Note for the subset of a two set

 If A ⊆ B and B ⊆ A, then A=B.
 Empty set is a subset of every set
 Every set is a subset of itself

 Proper Subset A ⊂ B
If A is a subset of B and A≠B, then A is called a proper subset of B and we write A ⊂ B

 Disjoint Set - A ∩ B = ∅

 Power Set - The set of all subsets of a set A

Important Notes for the power set of a set
 n(A) ≤ n[P(A)]
 If n(A) = m, then n[P(A)] = 2m
 The number of proper subsets of a set A is n[P(A)]–1 = 2m – 1.

Important Notes for different types of Set

 Empty Set is also a Finite Set

 Equal sets are equivalent sets but equivalent sets need not be equal sets.
 If A ⊆ B and B ⊆ A, then A=B.
 Empty set is a subset of every set
 Every set is a subset of itself
 (A) ≤ n[P(A)]
 If n(A) = m, then n[P(A)] = 2m
 The number of proper subsets of a set A is n[P(A)]–1 = 2m – 1.
 Elementary mathematics –Set, Relations and Functions
NDA
Operations on a set

Basic Properties of operations on a Set;

 Addition: A ∪ B = B ∪ A and A ∩ B = B ∩ A
 Commutative Property

 Subtraction: not commutative

 Addition: A ∪ (B ∪ C) = (A ∪ B) ∪ C and A ∩ (B ∩ C) = (A ∩ B) ∩ C
 Associative Property

 Subtraction: not Associative

 A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) [Intersection over union]

 Distributive Property

 A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) [Union over intersection]

---------------------------------------
 Complement of a set
Important Facts;

 U′ = ∅
 (A′)′ = A

 ∅′ = U

 Union of a Set

 A∪ A = A
Important Facts;

 A∪ ∅ = A
 A ∪ U = U where A is any subset of universal set U
 A ⊆ A ∪ B and B ⊆ A ∪ B
A ∪ B = B ∪ A (union of two sets is commutative)

 Intersection of a set
Important Facts;

 A∩∅ = ∅
 A∩A = A

 A ∩ B ⊆ A and A ∩ B ⊆ B
 A ∩ U = A where A is any subset of universal set U

 A∩ B = B ∩ A (Intersection of two sets is commutative)

 Difference of Set
Important Facts;
 A′ = U – A

 A–A=∅
 A – B = A ∩ B′
 Elementary mathematics –Set, Relations and Functions
NDA
 A–∅=A

A – B = A and B – A = B if A ∩ B = ∅
 A–B=B–A +A=B


 Symmetric Difference of Set

 AΔA=∅
Important Facts;

 A Δ B = {x : x ∈ A ∪ B and x ∉ A ∩ B}
 AΔB = BΔA

 A Δ B = (A ∪ B) – (A ∩ B)

 B ⊂ A, then A ∪ B = A and A ∩ B = B
 Common facts of a Set

 If A = B then, A ∪ B = A ∩ B
 Let n(A) = p and n(B) = q then
 Minimum of n(A∪B) = max {p, q}
 Maximum of n(A∪B) = p + q
 Minimum of n(A∩B) = 0
 Maximum of n(A∩B) = min{p, q}

---------------------------------------
De Morgan’s Laws of Difference
 A – (B ∪ C) = (A – B) ∩ (A – C)
 A – (B ∩ C) = (A – B) ∪ (A – C)

 (A ∪ B)’ = A’ ∪ B’
De Morgan’s Law of complementation

 (A ∩ B)’ = A’ ∩ B’

 n(A ∪ B) = n(A) + n(B) – n(A ∩ B)

Applications of Cardinality of Sets

 n(A ∩ B) = n(A) + n(B) – n(A ∪ B)

 n(A – B) = n(A) – n(A ∩ B)
 n(B – A) = n(B)– n(A ∩ B)
 n(A′) = n(U) – n(A)

 n(A ∪ B ∪ C) = n(A) + n(B) + n(C) – n(A ∩ B) – n(B ∩ C) – n(A ∩ C) +

 n(U) = n(A) + n(A′)

n(A ∪ B ∪ C)
 Elementary mathematics –Set, Relations and Functions
NDA

Cartesian Product of a Set

Cartesian Product (A × B)
Set of all possible ordered pairs between the elements of A and B such that the first
coordinate is an element of A and the second coordinate is an element of B. It is also
called Cross Product.

Important Properties of Cartesian product of Sets

 In general, A × B ≠ B × A , but n(A × B) = n(B × A)
 A×B= ∅ if and only if A = ∅ or B = ∅
 If n(A ) = p and n(B ) = q then n(A ×B) = p q
 Obeys Distributive property;
 A × (B ∪ C) = (A × B) ∪ (A × C)
 A × (B ∩ C) = (A × B) ∩ (A × C)
 In general if we join the Cartesian product of two non-empty sets provides a
shape in two dimensions and similarly Cartesian product of three non-empty sets
provide an object in three dimensions.
If A = {0,1}, B = {0,1} and C = {0,1} then, A × B = { (0 0, ),(0 1, ),(1 0, ),(1 1, ) } - (xy)
A × B × C = { (0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1) } - (xyz)
 Elementary mathematics –Set, Relations and Functions
NDA
Relations and Functions

Relation: A ‘relation’ R from A to B is a subset of A × B satisfying some specified

conditions. If x ∈ A is related to y ∈ B through R , then we write it as x R y. x Ry if
and only if ( x,y) ∈ R .

 Domain: R ={ x ∈ A | xRy, for some y ∈ B}

 Co-Domain: B
 Range: R ={ y ∈ B | xRy, for some x ∈ A }

Note;
 Domain of R ⊆ A
 Co-domain of R = B
 Range of R ⊆ B .
 f n(A ) = p , n(B) = q , then the total number of relations that exist from A to B is
2pq .

Null Relation: A relation which contains no element

Function: A relation f between two non-empty sets X and Y is called a function from X
to Y if, for each x ∈ X there exists only one y ∈ Y such that (x, y) ∈ f . That is,
f ={(x,y)| for all x ∈ X, y ∈Y }.

A function f from X to Y is written as f: X - Y

 Domain: X
 Co-Domain: Y
If f (a) = b, then b is called ‘image’ of a under f and a is called a ‘pre-image’ of b
 Range: The set of all images of the elements of X under the function

Note;
 f X: Y is a function only if , every element in the domain of f has an image and the
image is unique.
 If A and B are finite sets such that n(A) = p , n(B) = q then the total number of
functions that exist from A to B is q power p.

Important facts about the relations and the functions

 All the elements of a function should have images but, all the elements of a
relation is not necessary to have images like functions.
 Elementary mathematics –Set, Relations and Functions
NDA
Representation of a function
 Set of ordered Pairs - f (x) = { (x,y) | y = (f x), x ∈ A }
 Table Form

x 1 ……..

F(x) a ……..

 Arrow Diagram
 Graph

Types of Functions;
 One to One Function -
Distinct elements of A have distinct images in B. It is also called as Injection

 Many One Function -

Two or more elements of A have same image in B.

 Onto Function -
The range of f is equal to the co-domain of f. It is also called Surjection
Note: Range of f is its Co-domain ( = B) .
 Elementary mathematics –Set, Relations and Functions
NDA
 Into Function -
At least one of the element in B which is not the image of any element of A.
Note: Range of f is proper subset of co-domain (⊂ B)

A one – one and onto function is also called a one – one correspondence.

 Bijection -
If a function is both onto and one-one then, it is called Bijection
Condition: n(A) = n(B)

Special Cases of Functions

 Constant Function -
Range of f contains only one element.

 Identity Function -
The function f A: --- B, where B = A
Note: Identity function is a one to one function
 Elementary mathematics –Set, Relations and Functions
NDA
 Real Valued Function -
Range of f is a subset of the set of all real numbers ∈ R

Composition of Functions
Let, f A: B and g B: C be two functions then, the composition of f and g denoted by
g o f (x) = g ( f(x) ) x ∈ A

Composition of two Functions;

 g o f (x) = g ( f(x) )
 The Composition g o f (x) exists only when range of f is a subset of domain of g.
 Not Commutative

Composition of three Functions;

 f o ( g o h ) = ( f o g ) o h = f ( g(x) ) o h (x)
 It is Associative

Cryptography

Relation between the Cartesian product, Relation and Function of sets