# Proof of Polynomial Countability

1. Feb 9, 2012

### Shaikhob

1. The problem statement, all variables and given/known data
Let P(n) be the set of all polynomial of degree n with integer coefficients. Prove that P(n) is countable, then show that all polynomials with integer coefficients is a countable set.

2. The attempt at a solution
For this problem the book gives me a hint that using induction is one way to prove this. So by going off this I say that P(0) is countable since it is the set of all constants. After this I say that P(1) is countable since P(1) = ax + P(0) in which a ε A and A = {z: z ε Z, z ≠ 0}. Now my problem is that I do not know how to make the jump from P(1) to P(n) and then to P(n+1). For the second part of the question I know that all polynomials with integer coefficients are countable since if we were to take a union of all the sets they would be countable since the union of countable sets are countable.

2. Feb 9, 2012

### CompuChip

Hi, welcome to PF.

Looks like you already got all the components in place for a proof by induction.
Suppose that you have proven that P(n) is countable... can you write P(n + 1) in terms of P(n)?

3. Feb 9, 2012

### Deveno

hint: which terms are in P(n+1) that AREN'T in P(n)?

can you think of a way to write p(x) in P(n+1) as:

"something" + q(x), where q(x) is in P(n)?

maybe the "somethings" might be countable....