How can we show that the set of all polynomials with integer coefficients denumerable?

Question

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.

Answer 1

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.