Originally Posted by

**dwsmith** $\displaystyle P_n$ is the set of all polynomials of degree n with integer coefficients.

Prove that $\displaystyle P_n$ is countable.

By induction: $\displaystyle \forall n\in\mathbb{Z}, \ n\geq 0$

$\displaystyle P_0: \ ax^0\Rightarrow a$

Since a is an integer, we can put the integers in a 1-1 correspondence with the naturals numbers. Namely, define $\displaystyle f(n)=\begin{cases}2n-1, & n>0\\2n, & n\leq 0\end{cases}$

Assume P(k) is true for a fixed but arbitrary $\displaystyle k\geq n$, where P(k) is defined as

$\displaystyle a_kx^k+a_{k-1}x^{k-1}+\cdots a_1x^2+a_0x^0$

Prove P(k+1) is true

$\displaystyle P(k+1): \ a_{k+1}x^{k+1}+a_kx^k+a_{k-1}x^{k-1}\cdots a_1x^2+a_0x^0$

I need help in order to proceed.