GATE CS 2012 Q37 — Sets, Relations and Functions

To find the number of onto (surjective) functions from a domain set $A$ with $n$ elements to a codomain set $B$ with $2$ elements, we can use the principle of exclusion:

1. Total number of functions: Each of the $n$ elements in $A$ has $2$ choices in $B$. Therefore, the total number of possible functions is: $$2 \times 2 \times \dots \times 2 = 2^n$$
2. Non-onto functions: A function is not onto if its range does not cover the entire codomain $B = \{b_1, b_2\}$. Since $|B| = 2$, the only non-onto functions are those where all elements of $A$ map to a single element in $B$:
   • All elements map to $b_1$ (constant function 1)
   • All elements map to $b_2$ (constant function 2)
   Thus, there are exactly $2$ non-onto functions.

Subtracting the non-onto functions from the total functions gives the number of onto functions:

Hence, the correct option is C.