# Prove: set of the polynomials of degree $n$ with coefficients in $\Bbb Q$ is countable

Let $P_n =\{p(x)=a_n x^n+ a_{n-1} x^{n-1}+...+ a_1 x+a_0 |a_i \in \Bbb Q \}$ the set of the polynomials of degree $n$ with coefficients in $\Bbb Q$

Prove that $P_n$ is countable and tell why $P= \bigcup_{n=0}^\infty P_n$ the set of all the polynomials with coefficient in $\Bbb Q$ is countable.

How can I prove that $|P_n|=|Q|^{n+1}$ ?

• countable union of countable sets is countable – user265328 Sep 3 '15 at 17:55
• What theorems do you have? Do you know that the cartesian product of countable sets is countable? That there is a bijections $\mathbb{Z}\times \mathbb{Z}\to \mathbb{Z}$? This is probably where you should start. – Pax Kivimae Sep 3 '15 at 17:56
• Define a function $f: \mathbb{Q}^{n+1 }\to P_n$ given by $f(a_0,a_1,\cdots,a_n)=a_0 +a_1 x+ a_2 x^2 +\cdots+a_nx^n$, $x\in \mathbb{R}$. This is bijective function – Dr. Mohammad Alomari Sep 4 '15 at 9:22

Hint: Note that $\Bbb Q$ is countable and each coefficient (of which there are $n+1$) is from $\Bbb Q$. Now use the fact that a countable union of countable sets is countable.

It might help to note that each polynomial with coefficients in $\Bbb Q$ is equivalent to a polynomial with coefficients in $\Bbb Z$ (why?). If you can find an injection from $\Bbb Z\times\Bbb Z\to\Bbb Z$, you can try to extend the idea to $\Bbb Z\times\cdots\times\Bbb Z$, $(n+1)$-copies of $\Bbb Z$.

For $p_n(x)$, a n degree polynomial with coefficients in $\mathbb{Q}$, there are only n+1 coefficients ($a_i$'s). If these n+1 coefficients are fixed, the polynomial is fixed.

Now, total number of such $p_n (x)$ i.e. $|P_n|$ is $|\mathbb{Q}|^{n+1}$ (each coefficient could take any value in $\mathbb{Q}$), which is countable.

Hence, $|P_n|$ is countable.

We know that countable union of countable sets is countable $\implies |P|$ is countable

• That's what I thought, but How can I prove that $|P_n|=|Q|^{n+1}$? – Alex Turner Sep 4 '15 at 0:04
• Actually, we cannot say this. But with this kind of approach we can show that $|P_n|$ is countable. Use combinatorics. Similar example: How many 4 digits number are there? In a 4 digit number, we have 4 places to fill which can be filled by only ${0,1, \dots ,9}$. So, number of 4 digits number are 9*10*10*10 (since first place cannot be zero). Similarly, here you have n+1 places (coefficients) and $|\mathbb{Q}|$ ways to fill them – user265328 Sep 4 '15 at 4:56

Hint: you may use the Cantor-Bernstein theorem to prove that: $$\left| P_n \right| = \left|\mathbb{Q}^n\right| = \left|\mathbb{N}^n\right| = \left|\mathbb{N}\right| = \aleph_0.$$

• From this we can easily show that the set all algebraic numbers is countable but since the reals are uncountable, we deduce the existence of transcendental numbers without explicitly displaying one. – DanielWainfleet Sep 3 '15 at 19:54
• It seems to me that it's fairly straightforward to directly prove each of these sets has the same cardinality as the set of natural numbers (i.e. without invoking the "big hammer" Cantor-Bernstein theorem). – Dave L. Renfro Sep 3 '15 at 20:36