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

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

Answers and Replies

  • #2
micromass
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
22,129
3,302


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
cghost
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
micromass
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
22,129
3,302


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
cghost
4
0


Thanks for helping me
 

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

  • Last Post
Replies
5
Views
9K
Replies
2
Views
1K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
5
Views
6K
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
6
Views
6K
  • Last Post
Replies
10
Views
3K
Replies
5
Views
2K
Replies
5
Views
3K
Top