A function that's injective but not surjective. I'm trying to think of functions that are injective but not surjective between various sets. I can think of $f(x) = e^x$ for $f: \mathbb{R} \rightarrow \mathbb{R}$ (since the range should be positive $\mathbb{R}$ for this to be surjective, but $\mathbb{R}^+$ is a subset of $\mathbb{R}$) and $f(a,b) = a^b$ for $f: \mathbb{Z}\times\mathbb{Z} \rightarrow \mathbb{R}$ (the range should be $\mathbb{Q}$ for this to be surjective, but $\mathbb{Q}$ is a subset of $\mathbb{R}$) but is there any such function (injective, not surjective) from $\mathbb{Z}\times\mathbb{Z} \rightarrow \mathbb{Z}$?
 A: Yes, there is such a function.  Define $f: \Bbb Z \times \Bbb Z \to \Bbb Z$ by $$f(m,n) = \begin{cases} 2^{m}3^{n} & m, n \geq 0 \\ 5^{-m}7^{-n} & m, n < 0 \\ 11^{m}13^{-n} & m > 0, n < 0 \\ 17^{-m}19^{n} & m < 0, n > 0   \end{cases}.$$  You should prove this is injective.  For it not being surjective: which pair of numbers is being sent to any negative integer?  The range of $f$ is a subset of the positive integers.
A: A somewhat unsatisfactory answer is that $\mathbb{Z}\times\mathbb{Z}$ is countable, so it is in bijection with the natural numbers, i.e. a proper subset of $\mathbb{Z}$. This bijection is then an injection but not a surjection from $\mathbb{Z}\times\mathbb{Z}$ into $\mathbb{Z}$.
A: Lots of examples.  In fact there is a bijection (injection+surjection) between $\mathbb Z\times \mathbb Z$ and any infinite subset of $\mathbb Z$: Let $I\subseteq \mathbb Z$ be infinite, and count off the members of $\mathbb Z \times \mathbb Z$ with $I$ using diagonalization.
A: Something in an ugly closed form:
$$ f(m,n) = 2^{a(m)}3^{a(n)}5^{|m|}7^{|n|}, $$
where $a(x)$ is zero if $x<0$ and $1$ otherwise. This is certainly always positive.
A more geometrical idea is to draw a spiral on $\mathbb{Z} \times \mathbb{Z}$ starting from $(0,0)$ (you can easily come up with an algorithm for doing this: just keep turning left when there's an uncovered pair there, and go straight on otherwise, and you'll cover each ordered pair only once). This is an entirely concrete injection $\mathbb{Z} \times \mathbb{Z} \to \mathbb{N}$. (and hence not surjective as a function to $\mathbb{Z}$).
A: Here is a solution which does not rely on prime factorisation... well maybe a little bit.
First consider
$$g:{\Bbb Z}\to{\Bbb Z}^+\ ,\quad g(n)=4n^2+2n+1\ .$$
This is injective because
$$\eqalign{g(m)=g(n)\quad
  &\Rightarrow\quad 2m^2+m=2n^2+n\cr
  &\Rightarrow\quad (m-n)(2m+2n+1)=0\cr
  &\Rightarrow\quad m=n\ .\cr}$$
Now define
$$f:{\Bbb Z}\times{\Bbb Z}\to{\Bbb Z}\ ,\quad f(m,n)=g(m)2^{g(n)}\ .$$
It's clearly not surjective as it only takes positive values.  And it's injective since any possible value can be expressed uniquely as an odd number times a power of $2$, which gives unique values of $m$ and $n$.
