Prove that the set of integer coefficients polynomials is countable

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

Solution 1:

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$.

Solution 2:

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

Solution 3:

$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.