Problem a Please count how many functions can be defined if

Problem (a) Please count how many functions can be defined if the domain D is a finite set with the cardinality IDI = n. (b) Can you find a bijection between the set of all such functions and the power set P(D)?

Solution

Cardinality of D =n

f is a function defined from D to [0,1]

Then any element in D can be mapped onto either 0 or 1

If all elements are mapped on to 0 then we have one funciton

All onto 1 another

if n-1 to 0 then we have n-1

On the whole no of functions = nC0+nC1+nC2+...+nCn = 2ⁿ

yes we can find a power set as no of elements

i.e. n p(D) = 2ⁿ and no of functions 2ⁿ

As cardinality is the same for both we can find a bijection.