How can we show that the set of all polynomials with integer coefficients denumerable? Is the set of all polynomials with integer coefficients, denumerable?
I know that this set is countable but how can I show that it is denumerable as well.
 A: For completeness sake, I will write down two proofs of the fact that the set $\mathbb{Z}[x]$ of polynomials on integer coefficients is denumerable, meaning countable and infinite. As David Mitra points out in a comment, it is certainly of cardinality at least that of $\mathbb{Z}$, since one can easily present an injective function $f:\mathbb{Z}\rightarrow\mathbb{Z}[x]$: namely,
$$f(n)=n, \quad\text{for all}\quad n\in\mathbb{Z}.$$
One could then consider the set $\mathbb{Z}[x]_{m}$ of polynomials of degree at most $m$, which is easily seem to be equinumerous to $\mathbb{Z}^{m}$, which in turn has the same cardinality as that of $\mathbb{Z}$; then, by noticing that $\mathbb{Z}[x]=\bigcup_{m\in\mathbb{N}}\mathbb{Z}[x]_{m}$, one obtains $\mathbb{Z}[x]$ has at most as many elements as a denumrable union of denumerable sets, which is easily seem to be denumerable as well.
This proof is rather standard, but I like very much an alternative one: consider the map
$$g:\mathbb{Z}[x]\rightarrow\mathbb{Q}\setminus\{0\}$$
such that, for a polynomial $p(x)=m_{0}+m_{1}x+m_{2}x^{2}+\cdots+m_{k}x^{k}$, one has
$$g(p(x))=p_{0}^{m_{0}}\times p_{1}^{m_{1}}\times\cdots\times p_{k}^{m_{k}},$$
where $p_{i}$ is the $i$-th prime number. One can prove, without much work, that $g$ is, in fact, bijective, and since $\mathbb{Q}$ is denumerable, the desired result holds.
