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

  • Thread starter cghost
  • Start date
  • #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 ?
 

Answers and Replies

  • #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


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.
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.
 
  • #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
 

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

  • 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
Replies
2
Views
1K
  • Last Post
Replies
2
Views
2K
Top