-4
$\begingroup$

Can you give me examples for the following $f:\mathbb Z \to \mathbb Z$ (for integer functions)

  1. injective but not surjective
  2. surjective but not injective
  3. surjective and injective
  4. neither surjective nor injective
  • 4
    Is this homework? What have you tried?2012-02-22

3 Answers 3

5

A function $f$ is injective if it doesn’t send two things to the same place: in less informal language this means that if $m\ne n$, then $f(m)\ne f(n)$.

A function $f$ is surjective if it ‘hits’ everything in the target set; in your case the target set is $\mathbb{Z}$, so a surjective function is one that ‘hits’ every integer. In less informal language this means that if $n$ is any integer whatsoever, $n=f(m)$ for at least one integer $m$.

A function from $\mathbb{Z}$ to $\mathbb{Z}$ that is not injective must send two different integers to the same integer. There are many functions that do this, but one that you know well is the squaring function, $f(n)=n^2$: $f(1)=f(-1)=1$. Another is the absolute value function, $g(n)=|n|$: $g(1)=$ $g(-1)=1$. Or you can build one to order: $h(n)=\begin{cases}0,&\text{if }n=0\\0,&\text{if }n=1\\n,&\text{if }n\ne 0\text{ and }n\ne 1\end{cases}\;.$ Here $h(0)=h(1)=0$.

A function from $\mathbb{Z}$ to $\mathbb{Z}$ that is not surjective must fail to ‘hit’ at least one integer. None of the three functions described in the last paragraph is like that: the squaring and absolute value functions never ‘hit’ $-1$ (or any other negative integer), and $h(n)$ is never equal to $1$. Thus, all three are examples of functions from $\mathbb{Z}$ to $\mathbb{Z}$ that are neither injective nor surjective.

At the other extreme, the identity function $e:\mathbb{Z}\to\mathbb{Z}:n\mapsto n$ that sends every integer to itself is clearly both injective and surjective: it ‘hits’ every integer once (so it’s surjective) and only once (so it’s injective). You should check that if $k$ is any integer, the translation function $t(n)=n+k$ is both injective and surjective. (How can you tell whether it ‘hits’ every integer? Ask yourself what input would be required to get an output of $m$, say, where $m$ is any old integer.)

What about the mixed possibilities, injective but not surjective, and surjective but not injective. An easy example of the first is $d(n)=2n$, the doubling function: no two integers have the same double, so $d$ is injective, but $d$ ‘misses’ every odd integer, so it can’t be surjective. Or you could build another example to order: $k(n)=\begin{cases} n,&\text{if }n<0\\ n+1,&\text{if }n\ge 0\;. \end{cases}$

I’ll leave it to you to check that $k$ is injective but not surjective; what integer is not $k(n)$ for any $n$ whatsoever?

For a function that is surjective but not injective you need to make sure that everything gets ‘hit’, and something gets ‘hit more than once. A function built to order is easy: $c(n)=\begin{cases} n,&\text{if }n\le 0\\ n-1,&\text{if }n>0\;. \end{cases}$

Notice that $c(0)=c(1)=0$, so $c$ is definitely not injective, but you should have little trouble seeing that $c$ is surjective: every integer is $c(\text{some integer})$.

3

Injective not surjective: $x\mapsto 2x$

Surjective not injective $x \mapsto \lfloor x/2\rfloor$

Neither: $x\mapsto x^2$

surjective and injective: $x\mapsto x + 1$

  • 1
    @FortuonPaendrag - I think the poster meant $\lfloor \frac{x}{2} \rfloor$2012-02-22
1

Let us review the definitions:

Suppose $f\colon A\to B$.

  • $f$ is injective if $f(x)=f(y)$ implies $x=y$; alternatively we can say that if $x\neq y$ then $f(x)\neq f(y)$.
  • $f$ is surjective if for every $y\in B$ there is some $x\in A$ such that $f(x)=y$.

In our case $A=B=\mathbb Z$. We are looking, if so, for a function which gives different numbers different values (injective) or that they produce every possible value (surjective). Since $\mathbb Z$ is infinite we can "push" things around in a way which allows us to have only one of the properties.

  1. We need to choose a function which is injective, so two distinct numbers will produce distinct results, and to ensure that $f$ is not surjective we design it in a way that some number will surely not be in the range of the function.

    For example: $f(x)=2x$ would ensure that only even numbers are produced by $f$, so $f(x)=1$ is impossible. On the other hand, if $f(x)=f(y)$ then $2x=2y$, so we can divide by $2$ and have $x=y$. Therefore $f(x)=2x$ is injective but not surjective.

  2. We now look for a function which will produce every integer but at least two numbers will produce the same result. Such function can be dividing by $2$ all the even numbers, and keeping the odd numbers in place, that is: $f(x)=\begin{cases}\frac{x}2 & x\text{ even}\\ x & x\text{ odd}\end{cases}$

    To see that this is indeed surjective note that $x=f(2x)$ for every $x\in\mathbb Z$. However this is not injective since $1=f(1)=f(2)$.

  3. There are plenty of functions which are surjective and injective. For example $f(x)=x$, or $f(x)=x+2$ and even $f(x)=-x+42$. Try to prove for yourself why those functions are both injective and surjective.

    That is pick $x,y$ and show that if $x\neq y$ then $f(x)\neq f(y)$ (injectivity) and that for every $y\in\mathbb Z$ there is some $x\in\mathbb Z$ such that $f(x)=y$ (surjectivity).

  4. Lastly coming up with a function that is neither injective nor surjective should be relatively easy. Now we are looking for a function which has at least one number which is not produced by it, and at least two numbers producing the same output. (Hint: constant functions are like that).

I hope that now you have a better understanding of injectivity and surjectivity of functions.