One-to-one and onto functions

9,658

Solution 1

Onto functions are called surjective functions (i.e. cover all the function range set), and one-to-one functions are called injective functions (i.e. no two different values in function domain map to one value in function range). So for one-to-one but not onto (injective and not surjective) you could take $$f(n)=n+1$$ (value 1 is not taken). And for onto but not one-to-one function you could take $$f(n)=\begin{cases}1&&\text{for }n=1\\n-1&&\text{for }n>2\end{cases}$$ (1 and 2 map to 1).

Solution 2

For item a)

Let $f(n) = 2n , \ n \in N$. $f$ is one-to-one because :

$$ \text{if } f(n_1 ) = f(n_2) \text{ then } 2n_1 = 2n_2 \text{ and hence } n_1=n_2.$$

$f$ is not onto because, for example, there doesn't exist an $n \in N$ such that $f(n) = 3$

For item b)

Define $f(1) = 1 \text{ and if } n \geq 2$, $f(n) = n-1$ . Clearly $f$ is onto, but is not one-to-one because $f(1) = f(2) = 1$

Solution 3

To prove onto, you prove that every function value can occur.

To prove one-to-one, you prove that no function value can occur twice.

Two examples:

$\phi:n\mapsto n$ is onto, because every $n$ can be function value (just use $n$ as argument), and is one-to-one because no function value occurs twice (besides $n$ there's no other value which gives $n$).

$\phi:n\mapsto\cases{1 & if $n$ is odd\\0 & if $n$ is even}$ is not onto because you cannot get the function value $2$, and is not one-to-one because $\phi(1)=\phi(3)$.

Edit: I originally didn't want to directly give a solution because it looked too much like homework, but since now two other answers gave solutions anyway, I add mine. But I'll make it a bit more general, at least.

For $f$, take an arbitrary infinite proper subset $S$ of $\mathbb{N}$ (say, the set of natural numbers greater than $5$, the multiples of $4$, the primes, the powers of $2$, …). Then take for $f(n)$ the $n$-th smallest element of $S$. Since $S$ is proper, $f$ will not be onto. However it's one-to-one because the $n$-th smallest element cannot be the $m$-th smallest element if $n\neq m$.

For $g$, take again an arbitrary infinite proper subset $S\subsetneq\mathbb{N}$, but this time define $g(n)=k$ if the smallest element of $S$ which is not smaller than $n$ is the $k$-th element of $S$ when counting in order. This function is onto because for any $k$, $S$ has a $k$-th element (because it is infinite), and if $n$ equals that $k$-th element, then $g(n)=k$. But the function is not one-to-one because $S$ is proper, and for any $n\notin S$, $g(n)=g(n+1)$.

Share:
9,658

Related videos on Youtube

megan
Author by

megan

Updated on August 01, 2022

Comments

  • megan
    megan over 1 year

    Let $\mathbb{N}$ be the set of all positive integers.

    a). Define a function $f: \mathbb{N} \rightarrow \mathbb{N}$ that is one-to-one but not onto.

    b). Define a function $g: \mathbb{N} \rightarrow \mathbb{N}$ that is onto but not one-to one

    I'm not very sure how to prove onto and one-to-one problem. Thanks