I understand that $f$ from $A$ to $B$ is called onto if for all $b$ in $B$ there is an $a$ in $A$ such that $f (a) = b$. All elements in $B$ are used.
Thus, the function $f (x) = 3x – 4$ is onto where $f:\mathbb{R}\rightarrow \mathbb{R}$. Here we can get all real values of $f(x)$ for real values of $x$. So, this function is an onto function.
For the function $f (x) = x^2 – 2$, $f:\mathbb{R}\rightarrow \mathbb{R}$, we can not get values of $f(x)$ smaller than -2. Here, even if we try with all real values of $x$, it is not possible to get all real values for $f(x)$. Hence, this function is not onto.
As you can see, the methods I am following in drawing a conclusion are
mostly empirical ones. Is there is fixed methodology I can follow when I am given an arbitrary function and I need to determine whether the given function is onto.
If I have failed to explain clearly, please think it this way, I am given a function and I need to put down an algorithm to find out whether this function is onto.
Best Answer
Since you asked for an "algorithm" that takes a function as input and tells you whether or not it is onto, let me answer this from a computability theory point-of-view.
As it is the case with problems with highly varied inputs, this problem turns out to be undecidable. That is, there is no algorithm that takes in (computable) functions and decides whether or not they are onto.
Proving this is not hard. The typical approach is via a reduction. That is, we show that if there were such an algorithm, we could use it to solve some other undecidable problem. There are many such problems we can choose for this. For this answer, we use the most famous one: the halting problem.
Assume that we do have an algorithm that tells us whether or not some arbitrary function is onto. Given a Turing Machine $M$ and an input $w$ to it, we define the following function $f:\mathbb{N}\rightarrow\{0,1\}$ such that:
$$f(i)=\begin{cases} 1 & \text{if }M \text{ halts with input } w \text{ in } i \text{ steps} \\ 0 & \text{otherwise} \\ \end{cases}$$
Note that $f$ is onto if and only if $M$ eventually halts given $w$ as input. Thus, if we had an algorithm for testing surjectivity, we could use it decide whether or not some Turing machine $M$ halts on input $w$.