Is the set of polynomial with coefficients on $\mathbb{Q}$ enumerable?

Using the definition of enumerability of sets:

A non-empty set B is enumerable iff there is a bijection $f:\mathbb{N}\supset L \rightarrow B$.

So, I have to prove that the set of polynomial of one variable with coefficients on $\mathbb{Q}$ is enumerable. What I thought is that I can write every polynomial $p_0=A_0^0+A_1^0X+\dots +A_n^0X^n$ as

$$p_0=(A_0^0,A_1^0,\dots ,A_n^0,\dots ),$$

where the $A_i's$ are 0 except for a finite number of them. To say that this set is enumerable is the same that to say (denoting this set by B):

$$B=\{p_1,p_2,\dots\}$$

Now define the polynomial

$$ p=(x_0 \neq A_0^0, x_1 \neq A_1^1, \dots), $$

where every $x_i \neq A_i^i$. This polynomial is obviously not in the list B.

My question is: my approach is right to conclude that the set B is non-enumerable?

Solution 1:

First note that enumerable usually means can be effectively enumerated, where as you seem to ask if it is countable (or denumerable).

The conclusion is wrong, so the approach cannot be right. The set is countable. As for the approach, note that you are defining a polynomial with infinitely many non-zero coefficients, which is therefore not a polynomial.

Otherwise the argument would be reduced to an even worse state: a misinterpretation of the Cantor diagonal argument. That is, you are listing the polynomials and then finding something not on that concrete list; whereas the actual argument is "given any enumeration, we can find something not on the list".

To see that the polynomials are countable first note that $\mathbb Q$ is countable. This means that if we show that polynomials whose coefficients are in $\mathbb N$ give a countable set, we can use the bijection between $\mathbb Q$ and $\mathbb N$ to prove that the polynomials over $\mathbb Q$ are countable.

Now to see that, first we can (as you did) identify the polynomial with finite sequences, then we can find explicit bijections between $\mathbb N$ and the set of finite sequences, for example:

$$\langle a_0,\ldots,a_n\rangle\mapsto p_0^{a_0}\cdot\ldots\cdot p_n^{a_n}-1$$

Where $p_i$ is the $i$-th prime number.

Of course that if you are allowed to rely on the fact that countable unions of countable sets are countable, you can take the approach which avoids the explicit bijection:

• $\mathbb N\times\mathbb N$ is countable;
• By induction if $\mathbb N^k$ is countable then $\mathbb N^{k+1}$ is countable.

The set of all finite sequences is equal to $\bigcup_{n\in\mathbb N}\mathbb N^n$, and therefore is a countable union of countable sets.

Further reading:

1. The cartesian product $\mathbb{N} \times \mathbb{N}$ is countable
2. Cartesian Product of Two Countable Sets is Countable
3. Proving $\mathbb{N}^k$ is countable

Solution 2:

No, because in fact $B$ is enumerable.

Your argument fails because each $p_k$ has only finitely many non-zero coefficients. It turns out that the ‘polynomial’ that you construct by this diagonal argument isn’t actually a polynomial at all, but an infinite series: it has infinitely many non-zero coefficients.

Since $B$ is enumerable, you should instead be looking for a proof of this. One approach is to divide $B$ up into more manageable pieces: for each $n\in\Bbb N$ let $B_n$ be the set of polynomials of degree at most $n$. Presumably you already know that $\Bbb Q$ is enumerable, so it’s easy to see that $B_0$ is enumerable. Can you see how to find a bijection between $\Bbb{Q}^{n+1}$ and $B_n$?