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

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}+...+a_n$$ and this is the part I get lost at, let $$h = n+ a_0 + [a_1] + [a_2]+...+[a_n]$$

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

• It is trivial to prove that $P_n$ is not finite: it contains the constant function $p(x)=n$ for each $n\in\Bbb Z$, which is infinite. What is confusing you here? If it is countable and not finite, it must be in bijection with $\Bbb N$ by the Schröder–Bernstein theorem. – Mario Carneiro Sep 28 '15 at 21:43