3

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.

(These two [A, B] do not really answer my question.)

Masroor
  • 1,811
  • 2
    The fastest way in most cases is unfortunately qualified guessing as to a counter example (there is no $x$ so that $x^2-2=-3$, and here's why...), or a concrete construction of an $a$ for a general $b$ otherwise ($a=(b +4)/3$ for your linear function). – Arthur Dec 04 '13 at 13:19
  • 1
    If it's possible, a plot of the function is very helpful. – Steven Alexis Gregory Jul 05 '16 at 12:38

4 Answers4

8

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$.

mursalin
  • 461
6

It might help to know that a function $f:A\rightarrow B$ is 'onto' (surjective) if and only if there is a function $g:B\rightarrow A$ such that the composition $f\circ g:B\rightarrow B$ equals the identity function $1_{B}:B\rightarrow B$.

So if you have $f\left(g\left(b\right)\right)=b$ for every $b\in B$.

Edit:

This almost a rephrase of the definition of surjective, but it helps if in some situation you can easily get hold on such a function $g$. In essence you just must have a good look at your function $f$.

drhab
  • 151,093
3

You usually do generally the same thing. Take any given element in $B$ and see if you can find $a\in A$ such that $f(a)=b$. The element you find need not be an inverse; for example $f:\Bbb R\to\Bbb Z$ s.t. $f(x)=\lfloor x\rfloor$ is onto because for all $n\in\Bbb Z$, $f(n)=n$.

Edit: this is basically the same thing @drhab is saying.

Tim Ratigan
  • 7,247
2

As you wrote

Function $f \colon A \rightarrow B$ is onto if for all $b \in B$ there exists $a \in A$ such that $f(a)=b$.

We can write the solution of your 1st example in a bit more formal way:

$f(x)=3x-4$

Take $y \in \mathbb{R}$ then we want to find such $x \in \mathbb{R}$ that $f(x)=y$. Set $x:=\frac{1}{3}y + \frac{4}{3}$, then $f(\frac{1}{3}y + \frac{4}{3})=y$.

In your 2nd example to show the function is not onto, it is sufficient to find a courterexample so an element in the codomain of the function. Set $f(x):=x^2-2$. Take element e.g., $-6$, we can see that for any real $x$ we have that $f(x)\geq -2$, thus we won't find $x \in \mathbb{R}$ such that $f(x)=-6$. This function is not onto.

One of the methods is

A function $f \colon A \rightarrow B$ is onto if and only if there exists its right inverse, that is, a function $g \colon B \rightarrow A$ such that $f \circ g = \mathrm{id}_B$, where $\mathrm{id}_B(x)=x$ for all $x \in B$.

Deyton
  • 246
  • This does not address the question at all. – Clayton Dec 04 '13 at 13:22
  • 1
    @Deyton, OP was not asking whether those functions are onto. You'll notice he gave those results in the question. – Tim Ratigan Dec 04 '13 at 13:22
  • I thought that by writing it more formally he will get how to show whether the function is onto or not in different cases. – Deyton Dec 04 '13 at 13:25
  • @Deyton I know whether the functions are onto or not. I am looking for some generic, formal and methodical way to find out whether a function is onto or not. – Masroor Dec 04 '13 at 13:30
  • Ok, another method is: A function $f \colon A \rightarrow B$ is onto if and only if there exists its right inverse, that is, a function $g \colon B \rightarrow A$ such that $f \circ g = \mathrm{id}_B$, where $\mathrm{id}_B(x)=x$ for all $x \in B$. – Deyton Dec 04 '13 at 13:34