- #1

- 4

- 0

## Main Question or Discussion Point

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 ?

- Thread starter cghost
- Start date

- #1

- 4

- 0

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 ?

- #2

- 22,097

- 3,280

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

Let [tex]A_0=\mathbb{Q}[/tex]. This is clearly countable.

Let [tex]A_1=\{a+bx~\vert~a,b\in \mathbb{Q}\}[/tex], this is countable since it has the same cardinality of [tex]\mathbb{Q}\times \mathbb{Q}[/tex].

Let [tex]A_2=\{a+bx+cx^2~\vert~a,b,c\in \mathbb{Q}\}[/tex], this is countable since it has the same cardinality of [tex]\mathbb{Q}\times\mathbb{Q}\times\mathbb{Q}[/tex].

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

- #3

- 4

- 0

You proved here that there is a bijection from N to Q[x], but how can i write that function down ?

Let [tex]A_0=\mathbb{Q}[/tex]. This is clearly countable.

Let [tex]A_1=\{a+bx~\vert~a,b\in \mathbb{Q}\}[/tex], this is countable since it has the same cardinality of [tex]\mathbb{Q}\times \mathbb{Q}[/tex].

Let [tex]A_2=\{a+bx+cx^2~\vert~a,b,c\in \mathbb{Q}\}[/tex], this is countable since it has the same cardinality of [tex]\mathbb{Q}\times\mathbb{Q}\times\mathbb{Q}[/tex].

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

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.

- #4

- 22,097

- 3,280

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 [tex]\mathbb{N}[/tex] and [tex]\mathbb{Q}[/tex] is hard and ugly to write down...

- #5

- 4

- 0

Thanks for helping me

- Last Post

- Replies
- 5

- Views
- 8K

- Last Post

- Replies
- 10

- Views
- 2K

- Last Post

- Replies
- 18

- Views
- 6K

- Last Post

- Replies
- 4

- Views
- 2K

- Last Post

- Replies
- 6

- Views
- 5K

- Last Post

- Replies
- 2

- Views
- 2K

- Last Post

- Replies
- 8

- Views
- 2K

- Last Post

- Replies
- 5

- Views
- 6K

- Last Post

- Replies
- 2

- Views
- 1K

- Last Post

- Replies
- 2

- Views
- 2K