# Prove that the set of integer coefficients polynomials is countable

How to prove that the set of integer coefficient polynomials is countable?

• See this question: math.stackexchange.com/questions/118518/… – Avi Steiner Mar 26 '13 at 3:29
• When you receive helpful answers, we encourage you to (a) upvote them, and (b) accept one answer (you can accept one answer per question). To accept an answer, just click on the $\checkmark$ to the left of the answer you'd like to accept. Bonus: you get two reputation points each time you accept an answer to a question! – Namaste Mar 27 '13 at 1:24

Hints:

1) Prove that for each $n\ge$ 1 the set $\mathbb Z^n$ is countable. This can be done by induction.

2) Prove (or be aware of the fact) that a countable union of countable sets is countable.

Now, write the set of all polynomials with integer coefficients as a countable union $\bigcup_n P_n$, where $P_n$ is the set of all polynomials with integer coefficients and of degree smaller than $n$.

Prove that each $P_n$ is countable by establishing a bijection between $P_n$ and $\mathbb Z^n$.

Hint: You can show there is a bijection to $\mathbb{Z}\times\cdots\times\mathbb{Z}$.

• A bijection between what and what precisely? – Ittay Weiss Mar 26 '13 at 3:29

$1$. Prove that the set $S_n$ consisting of polynomials of degree $n$ with integer coefficients is countable. Show this by constructing a bijection between $S_n$ and $\underbrace{\mathbb{Z} \times \mathbb{Z} \times \cdots \times \mathbb{Z}}_{n \text{ times}}$.

$2$. Now the set you are interested in is $S = \bigcup_{n \in \mathbb{N}} S_n$. Show that $S$ is countable by proving that a countable union of countable sets is again countable.