Q4:

Find the number of all onto functions from the set $\{1, 2, 3,......, n\}$ to itself.

Step 1: Formal Definition of the Function

Let $A = \{1, 2, 3, \dots, n\}$. We are considering a function $f: A \to A$. For $f$ to be an onto function (surjective), every element in the codomain $A$ must have at least one pre-image in the domain $A$. [Per the Definition of Surjective Mapping].

Step 2: Analysis of Cardinality and Injectivity

Since the domain and codomain are the same finite set $A$ with $|A| = n$, a function $f: A \to A$ is onto if and only if it is also injective (one-to-one). [Per the Pigeonhole Principle for finite sets of equal cardinality]. A function that is both injective and surjective is defined as a bijective function or a permutation of the set $A$.

Step 3: Calculating the Permutations

To determine the number of onto functions, we must count the number of ways to map $n$ distinct elements of the domain to $n$ distinct elements of the codomain such that each element is used exactly once.

• The first element $1$ can be mapped to any of the $n$ elements in the codomain.
• The second element $2$ can be mapped to any of the remaining $(n-1)$ elements.
• The third element $3$ can be mapped to any of the remaining $(n-2)$ elements.
• Continuing this process, the $n$-th element has only $1$ remaining choice.

Step 4: Mathematical Formulation

The total number of onto functions is the product of the number of choices for each element, which is the definition of the factorial of $n$:

$N = n \times (n-1) \times (n-2) \times \dots \times 1 = n!$

Step 5: Theoretical Justification

The set of all bijections from a set of $n$ elements to itself is the Symmetric Group $S_n$. The order of this group, representing the number of permutations, is given by $n!$. Since every bijection is an onto function in this context, the total number of onto functions is exactly $n!$.

Final Solution: The number of onto functions is $n!$.