Surjective, Injective, Bijective Functions from $\mathbb Z$ to itself [closed]

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

closed as off-topic by Najib Idrissi, Daniel Fischer, Tunk-Fey, Hakim, Olivier BégassatJul 31 '14 at 10:59

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Najib Idrissi, Daniel Fischer, Tunk-Fey, Hakim, Olivier Bégassat
If this question can be reworded to fit the rules in the help center, please edit the question.

locked by user642796Nov 24 '14 at 16:25

This question exists because it has historical significance, but it is not considered a good, on-topic question for this site so please do not use it as evidence that you can ask similar questions here. This question and its answers are frozen and cannot be changed. See the help center for guidance on writing a good question.

• Is this homework? What have you tried? – Asaf Karagila Feb 22 '12 at 0:18

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

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$

• ⌊2x⌋ <--- what does this symbol means ? – Nikos Feb 22 '12 at 0:20
• yes its homework but im not sure how to recognise them :S – Nikos Feb 22 '12 at 0:24
• How is $x \mapsto \lfloor 2x\rfloor$ surjective? – Ravi Feb 22 '12 at 0:26
• @Nikos This should help en.wikipedia.org/wiki/Floor_and_ceiling_functions – Ravi Feb 22 '12 at 0:28
• @FortuonPaendrag - I think the poster meant $\lfloor \frac{x}{2} \rfloor$ – user22805 Feb 22 '12 at 0:28

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.