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!
Best Answer
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$).