As a Public Service to the general harassed students trying to understand what set theory means. Here’s a short note from my side.
————————-
Functions ka ek rule hota hai, every element in domain (X) can have only one corresponding value in codomain , matlab function plot karne pe, if you draw a straight vertical line parallel to Y axis, it must at most intersect the graph at one point only, for it to be a function in X.
However, it doesn’t matter how many times a horizontal line intersects the graph. This gives the function two properties:
(1) Injectivity: (Related to the nature of the relation)
One to one function (Injective) are those where every element in X will have a corresponding value in Y such that every Y will have at most one relation from X.
eg. If X has 7 elements and Y has 10, for a one to one function, we can choose 7 of the 10 elements in the range to match with the domain, and these 7 can be permuted amongst themselves. Hence, number of one to one functions = 10C7*7!
eg. If X has 10 elements and Y has 7 elements, we see that since range has less unique elements than domain, many to one function will exist. Hence, one-to-one = 0
(2) Surjectivity: (Related to nature of Range)
Onto function (Surjective) are those where the range = Codomain, ie every element in Y is related to one or more elements in X. Thus every element of Y is utilised. Into function is one in which range < codomain.
eg. If X has 5 elements, and Y has 7 elements, onto function = 0. Why? Because a function can have only one unique value of Y for each value of X. Hence there can be maximum of 5 unique values in Y related to X. Two elements get left out and hence it cannot be an onto function anymore
eg. X=7, Y= 3
By the formula, onto functions = sigma(r=1,n) (-1)^(n-r)*C(n,r)*r^m
= sigma(r=1,3)(-1)^(3-r)*C(3,r)*r^7
= 1806
Total number of functions = 3^7 = 2187
Number of into functions = 2187-1806 = 381
Injectivity and Surjuctivity are not mutually exclusive sets. A one to one onto function is called a bijective function.
One to one + Many to one = Into + Onto = Number of functions possible.
Depending on the function, the nature (injective,surjective) is determined. But for the given domain and co-domain, we can determine how many functions are possible. The nature of the function will then depend on the individual function.
Q. Set A has 5 elements, Set B has 2 elements.
Analyze the number of one-to-one, many-to-one, into, onto functions possible when
(A) A -> B (A is domain, B is codomain)
(B) B -> A
———————————
Some basic formulae:
Set A has m elements Set B has n elements.
(1)
If m>n One to One function =0
If n>m One to One function = P(n,m)
(2)
Number of functions = n^m
Number of relations = 2^(m*n)
(3)
No of Many to One functions = Number of func- Number of One to One=n^m -nPm
(4)
If n>m Number of Onto functions =0
If m>n Number of Onto functions= sigma ( r = 1 to n) (-1)^(n-r) *C(n,r)*r^m
———————-
There you go. That’s all, folks!
Ashish Pai 