Show that the set of polynomials with rational coefficients is countable.

Question

Problem: Show that the set of polynomials with rational coefficients is countable.

Idea: We know that the set of rational numbers is denumerable. This implies that the set of rational numbers is countable. We also know that the degree that each polynomial can be is a natural number (I think, and I'm not sure how to word this.) Therefore, I think we can reason through this somehow, by showing that the plane $Q X N$ Is denumerable. I'm just not sure how to do this. Any ideas.

Note: this is for my introduction to proofs class study quide. So, I would prefer not to go to over the top.

Answer 1

Let us begin by stating that the set of rationals is countable, as Z² is countable and every rational number can be expressed as an ordered pair of integers.

Then we can enumerate the polynomials as follows:

1.Start with n=1
2.For every m on [1,n] list the next order-m polynomial
3.Increase n by 1 and return to step 2.

For a proper enumeration of each order of polynomials (which must exist as, Q being countable, Qⁿ is countable for all finite n and every order-n rational-coefficient polynomial can be expressed as an ordered n-tuple), every polynomial of rational coefficients will eventually appear exactly once.

Answer 2

Write $\Bbb N_0=\Bbb N\cup\{0\}$

Theorem: Let $X\subset\Bbb C$ be a countable set. Then the set $$X[z]=\left\{\sum_{j=0}^{n}a_jz^j:n\in\Bbb N_0,a_j\in X\right\}$$ is countable.

Proof: Since $X$ is countable, so is $\mu(z)=\{az:a\in X\}$. Thus the sets $$S_n(z)=\prod_{k=0}^{n}\mu(z^k)=\left\{(a_0,a_1z,a_2z^2,..,a_nz^n): (a_0,a_1,...,a_n)\in X^{n+1}\right\}$$ are countable for all $n\in\Bbb N_0$, because they are each a finite product of countable sets. Then for any $p=(p_1,...,p_n)\in\Bbb C^n$, write $\phi_n(p)=\sum_{k=1}^{n}p_k$. We then have that every set of degree-$n$ polynomials with coefficients in $X$, given by $$X_n[z]=\{\phi_n(p):p\in S_n(z)\},$$ is countable. And since $$X[z]=\bigcup_{n\in\Bbb N_0}X_n[z]$$ is a countable union of countable sets, it must also be countable. $\square$

Since $\Bbb Q$ is a countable subset of $\Bbb C$, we get that $\Bbb Q[x]$ is countable via the theorem.