We just learnt this today in Discrete Math, and now I'm trying to review from the textbook. However unfortunately during this lecture I was completely lost with no idea what was going on.
I know that for one-to-one, every $x$ has an unique $y$ and for onto, for all $y$ there exists an $x$ such that $f(x)=y$.
I've provided two questions to use as examples from my textbook.
Suppose $f \colon \Bbb N \to \Bbb N$ has the rule $f(n) = 4n + 1$. Function $f$ is one-to-one.
Suppose $f \colon \Bbb Z \to \Bbb Z$ has the rule $f(n) = 3n - 1$. Function $f$ is onto $\Bbb Z$.
Answer one or both or give a hint, I would just love any explanation to what is going on! Thanks!
$\endgroup$ 73 Answers
$\begingroup$1) Let's show this function is $1-1$. To do this, we suppose $f(n_1) = f(n_2)$ and show that this forces $n_1 = n_2$.
So, if it's true that $f(n_1) = f(n_2)$, then this means that
$$4n_1 + 1 = 4n_2 + 1 \\ \Rightarrow 4n_1 = 4n_2 \\ \Rightarrow n_1 = n_2 $$
and we have demonstrated what is required. Thus, $f$ is $1-1$.
2) Let's see if the function is onto (it might not be). If it is, we should be able to choose any $m \in \mathbb{Z}$ and show that there is some $n \in \mathbb{Z}$ such that $f(n) = 3n - 1 = m$.
If this is true, then we will need $n = \dfrac{1}{3}(m + 1)$. The problem is that this might not be an integer! For example, if $m = 1$, then $n$ would need to be $\dfrac{2}{3}$, which is not an integer. Thus, there is no $n \in \mathbb{Z}$ such that $f(n) = 1$ and so the function is not onto.
EDIT: For fun, let's see if the function in 1) is onto. If so, then for every $m \in \mathbb{N}$, there is $n$ so that $4n + 1 = m$. For basically the same reasons as in part 2), you can argue that this function is not onto.
For a more subtle example, let's examine
3) $f : \mathbb{N} \to \mathbb{N}$ has the rule $f(n) = n + 2$. If it is onto, then, for every natural number $m$, there is an $n$ such that $n + 2 = m$; i.e. that $n = m - 2$. Now, we don't have the same problem as we did before, that is, we don't have to divide by anything to solve for $n$. Thus there is always an integer $n$ so that $n + 2 = m$.
BUT! If $m = 1$ (for example), then $n$ would have to be $1 - 2 = -1$ which is not a natural number, so this function is not onto either.
The point of all this is, we have to look closely at both the domain and codomain to answer these kinds of questions.
$\endgroup$ 5 $\begingroup$If you want to show that a function, say $f$, is 1-to-1, then you typically consider two values $x_1,x_2$ in the domain of $f$ such that $f(x_1)=f(x_2)$. From this, if you can derive that $x_1=x_2$, then your function is 1-to-1.
Let's consider your first example. We would have $f(x_1)=4x_1+1=4x_2+1=f(x_2)$. We can then simplify to obtain $x_1=x_2$. Hence $f$ is 1-to-1.
To show that a function $f$ is not 1-to-1, it suffices to find $x_1,x_2$ in the domain of $f$ such that $x_1\neq x_2$, but $f(x_1)=f(x_2)$.
If you want to show that a function $f$ is onto, then for any $y$ in the image/range of $f$, you must find $x$ in the domain such that $f(x)=y$.
To show that a function $f$ is not onto, just find $y$ in the target set of $f$ (that is, the set at the end of your arrow $f:X\to Y$; we call it the codomain) such that there is no $x$ in the domain such that $f(x)=y$.
As Baron pointed out, the function in your second example is not onto... we'll show this as an example that something is not onto. Consider any $y\in\mathbb Z$. In order for $f$ to be onto, there must be an $x$ such that $f(x)=3x-1=y$, or $$ x = \frac{y+1}{3}. $$ Now, we can see that $x$ is not an integer (as required) for some values of $y$. Namely, if $y=1,3,4,6,$etc., then there is no $x$ such that $f(x)=y$. Thus $f$ cannot be onto.
$\endgroup$ $\begingroup$- Another option: decompose $f$ into simpler functions that are easier to check as being one-to-one. Let $g(n)=n+1$ and $h(n)=4n$. Both $g$ and $h$ are linear functions with nonzero leading coefficient; and linear functions are one-to-one. Then $f= g\circ h$, both $g$ and $h$ are one-to-one, and a composition of one-to-one functions is also one-to-one. So $f$ is one-to-one.
