How can i find a bijection from N( natural numbers) to Q[X]

[cghost]

How can i find a bijection from N( natural numbers) to Q[X] ( polynomials with coefficient in rational numbers ). I can't find a solution for this. Can you please point me in the right direction ?

 

[micromass]

This is a standard trick. The proof is as follows:

Let $$A_0=\mathbb{Q}$$. This is clearly countable.
Let $$A_1=\{a+bx~\vert~a,b\in \mathbb{Q}\}$$, this is countable since it has the same cardinality of $$\mathbb{Q}\times \mathbb{Q}$$.
Let $$A_2=\{a+bx+cx^2~\vert~a,b,c\in \mathbb{Q}\}$$, this is countable since it has the same cardinality of $$\mathbb{Q}\times\mathbb{Q}\times\mathbb{Q}$$.

Continue with this process. Finally, we have $$\mathbb{Q}[x]=\bigcup_{n\in \mathbb{N}}{A_n}$$. This is countable as countable union of countable sets.

 

[cghost]

This is a standard trick. The proof is as follows:

Let $$A_0=\mathbb{Q}$$. This is clearly countable.
Let $$A_1=\{a+bx~\vert~a,b\in \mathbb{Q}\}$$, this is countable since it has the same cardinality of $$\mathbb{Q}\times \mathbb{Q}$$.
Let $$A_2=\{a+bx+cx^2~\vert~a,b,c\in \mathbb{Q}\}$$, this is countable since it has the same cardinality of $$\mathbb{Q}\times\mathbb{Q}\times\mathbb{Q}$$.

Continue with this process. Finally, we have $$\mathbb{Q}[x]=\bigcup_{n\in \mathbb{N}}{A_n}$$. This is countable as countable union of countable sets.

You proved here that there is a bijection from N to Q[x], but how can i write that function down ?
Or you can't exactly explicit the function f : N -> Q[x] , f(x) = ... ?
If it's a bijection, every natural number should point to a single polynom, is that right?
Or Q[X] is defined as a set of equivalence classes.

 

[micromass]

It's very hard to explicitely say what the bijection is. Most of the time people are happy with knowing that there exists a bijection.

Of course, if you examine all the steps I made, maybe you can make the bijection step-by-step. But this will be a very ugly thing. In fact, even a bijection between $$\mathbb{N}$$ and $$\mathbb{Q}$$ is hard and ugly to write down...

 

[cghost]

Thanks for helping me