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):


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?

  • $\begingroup$ Have you done the proof yet which shows that $\mathbb{Q}$ is countable (enumerable)? If yes, you can use that and some other theorem which says that a union of countable sets is countable. $\endgroup$ – Jeff Mar 10 '12 at 11:32
  • $\begingroup$ @Jeff Yes I have, but I don't see how the set B is the union of any other sets. $\endgroup$ – joaopaulolf Mar 10 '12 at 11:35
  • $\begingroup$ I think: If $\mathbb{Q}$ is countable, and $A_i \in \mathbb{Q}$, then $p_j$ is (not really) a union of $A_i$s (more like concatenatiing two sets), and $B$ is a concatenation of $p_i$s, then... I guess this breaks down because concatenation isn't quite a union. But still, it seems that if two countable $A$ and $B$ are made into a set of $(a \in A, b \in B)$, then the new set is countable, too. $\endgroup$ – Jeff Mar 10 '12 at 12:33

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
  • $\begingroup$ Thank you, now I see what is wrong in my argument, and your hints are really helpful. $\endgroup$ – joaopaulolf Mar 10 '12 at 11:42

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

  • $\begingroup$ Yes, now that I stop to think, there couldn't be a polynomial like that. $\endgroup$ – joaopaulolf Mar 10 '12 at 11:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.