Let $P_n$ be the set of all polynomials with integer coefficients and of degree $n$. I am trying to prove that this set is countable, and I have recently read the following argument:
Because $\mathbb{Z}$ is countable, there are countably many choices for each of the coefficients of a polynomial, and because there are finitely many choices to make, $P_n$ is countable.
I'm not sure how this works—why can we say that a combination of countably many choices results in countably many outcomes?
We say that a set $A$ is countable if $A\simeq \mathbb N$. Furthermore by the Cantor-Schroeder-Bernstein Theorem and the uniqueness of prime decomposition we know that $\mathbb N^n\simeq \mathbb N$ for any finite $n$.
This argument is saying that there is a bijection between $\mathbb Z^n$ and your set of polynomials, and because $\mathbb Z\simeq \mathbb N$ by the C-S-B Theorem too, and bijections are transitive, it follows that the set of all polynomials of degree $n$ is countable.
