Using induction to prove that the infinite set of polynomials is countably infinite

Question

Let $P_n$ be the set of all polynomials of degree n with integer coefficients. Prove that $P_n$ is countable.

So I know to prove that $P_n$ is countable, it must be either infinitely countable or finite. Since we know it's not a finite set, it must be infinitely countable. Therefore, I need to prove that the set of all polynomials is equivalent to the set of natural numbers. This would imply that I need to use induction. My book provides a solution, but I don't really understand it. Can someone provide me with some insight on how to think about this problem?

The book says to set $$ P_n= n + a_0x^n + a_1x^{n-1} +a_2x^{n-2}+\cdots+a_n$$ and this is the part I get lost at, let $$h = n+ a_0 + [a_1] + [a_2]+\cdots+[a_n]$$

They then note $h\ge1$ and each $\lvert a_i \rvert \le h$

After that I'm absolutely confused how they use induction to provide a proof. Please help!

Answer 1

Note that $P_n$ is isomorphic to $\Bbb Z^{n+1}$ via the correspondence

$$(a_0,a_1,\dots,a_n)\in\Bbb Z^{n+1}\iff a_0+a_1x+\dots+a_nx^n\in P_n,$$

so it is sufficient to prove that $\Bbb Z^{n+1}$ is countably infinite. The easy way to do this is to find an injection from $\Bbb Z^{n+1}$ to $\Bbb N$, since $\Bbb Z^{n+1}$ is clearly not finite, and

$$f(a_0,a_1,\dots,a_n)=p_1^{g(a_0)}p_2^{g(a_1)}\dots p_{n+1}^{g(a_n)}$$

will do the trick (where $p_n$ is the $n$th prime, and $g(n)=2n^2+n$ is an injection $\Bbb Z\to\Bbb N$).

Answer 2

The trick is to see that

$h = n+ |a_0| + |a_1| + |a_2|+\cdots+|a_n|$ ($a_n \ne 0,$ $n \ge 1$)

yields a class of polynomial for each $h.$

$h = 2$ has the solutions: $ n =1$, $a_1 = 1$ which yields the polynomial $x$

$h=3$ has solutions:

$n =2$, $a_2 =\pm1 $ which yields the polynomials $x^2$ and $-x^2$

$n =1$, $a_1 =\pm$ which yields $2x$ and $-2x$,

$n =1$, $a_1 =\pm1$, $a_0 = \pm1$ which yields $x +1 $, $x -1$, $-x +1$, and $-x - 1$.

and so on.

For each $h,$ there are finite polynomials yield and for all $h$ all polynomials will be yielded. Thus we have a countable union of finite sets of polynomials. Thus there are countably many polynomials.