• Support PF! Buy your school textbooks, materials and every day products Here!

Proving algebraic numbers are countable?

  • Thread starter SMA_01
  • Start date
  • #1
218
0

Homework Statement



Let n a positive number, and let An be the algebraic numbers obtained as roots of polynomials with integer coefficients that have degree n. Using the fact that every polynomial has a finite number of roots, show that An is countable.

Homework Equations



Hint: For each positive number m, consider polynomials

[itex]\sum[/itex] aixi from i=0 to n that satisfy

[itex]\sum[/itex] lail ≤ m.

The Attempt at a Solution



I want to prove this using induction, but I don't fully understand how to use the hint. How would I partition with algebraic numbers using it?

Starting using A1, which are the roots of polynomials, I know that these algebraic numbers are countable because

a1x1+a0=0 are the rational numbers, which are countable. What does the hint have to do with this?
 

Answers and Replies

  • #2
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,394
180
It suffices to show that for each [itex]n[/itex], there are only countably many polynomials of degree [itex]n[/itex] with integer coefficients. The hint is suggesting a way to count these polynomials.
 
  • #3
218
0
For the induction proof, I assume that An is countable, how would I use the hint to prove that An+1 is countable? I still don't fully understand it...
 
  • #4
Dick
Science Advisor
Homework Helper
26,258
618
It suffices to show that for each [itex]n[/itex], there are only countably many polynomials of degree [itex]n[/itex] with integer coefficients. The hint is suggesting a way to count these polynomials.
And probably not the easiest way. The condition [itex]|a_i|<m[/itex] (without the summation) would make an explicit count much easier and accomplish the same thing.
 
  • #5
218
0
And probably not the easiest way. The condition [itex]|a_i|<m[/itex] (without the summation) would make an explicit count much easier and accomplish the same thing.
I'm still confused about how to apply the hint to my proof though.
 
  • #6
Dick
Science Advisor
Homework Helper
26,258
618
I'm still confused about how to apply the hint to my proof though.
I don't think you really want to use induction. Try proving directly that A_n is countable. Use that a countable union of countable (or in this case finite) sets is countable. Those are the lines you should be thinking along.
 
  • #7
218
0
And probably not the easiest way. The condition [itex]|a_i|<m[/itex] (without the summation) would make an explicit count much easier and accomplish the same thing.
I don't think you really want to use induction. Try proving directly that A_n is countable. Use that a countable union of countable (or in this case finite) sets is countable. Those are the lines you should be thinking along.
Would this be different than proving the set of all algebraic numbers is countable?
 
  • #8
Dick
Science Advisor
Homework Helper
26,258
618
Would this be different than proving the set of all algebraic numbers is countable?
Not really, its just the first step along the way. If you prove A_n is countable then the algebraic numbers are the union over all n of A_n.
 
  • #9
218
0
I'm just having trouble starting. Each polynomial has finitely many roots, so I visualize it as mapping these roots to the set of all positive integers, but i'm not sure if this is correct.
 
  • #10
Dick
Science Advisor
Homework Helper
26,258
618
I'm just having trouble starting. Each polynomial has finitely many roots, so I visualize it as mapping these roots to the set of all positive integers, but i'm not sure if this is correct.
Ok, since each integer polynomial of degree n has a finite number of roots, then if you could show the number of integer polynomials of degree n is countable, then you would be done. Agree with that?
 
  • #11
218
0
Ok, since each integer polynomial of degree n has a finite number of roots, then if you could show the number of integer polynomials of degree n is countable, then you would be done. Agree with that?

Yes, I see what you mean.
 
  • #12
Dick
Science Advisor
Homework Helper
26,258
618
Yes, I see what you mean.
Ok, then the hint is suggesting you take a condition like |a_i|<m. Show the total number of roots of all those equations is finite. Then take the union over all m.
 
  • #13
218
0
Would I do this explicitly?
 
  • #14
Dick
Science Advisor
Homework Helper
26,258
618
Would I do this explicitly?
Count them (or at least give an upper bound)! How many integer polynomials of degree n can you have that satisfy |a_i|<m. How many roots can each polynomial have?
 
  • #15
218
0
They can have at most n roots.

"How many integer polynomials of degree n can you have that satisfy |a_i|<m."

What do you mean?
 
  • #16
Dick
Science Advisor
Homework Helper
26,258
618
They can have at most n roots.

"How many integer polynomials of degree n can you have that satisfy |a_i|<m."

What do you mean?
How many integer polynomials of the form ax+b satisfy |a|<m and |b|<m? An upper bound will do just fine. You just want to claim the number is finite. Now generalize to an polynomial of degree n.
 
  • #17
218
0
There are finitely many polynomials of degree n. So if I show that the number of polynomials is countable, I can automatically say the roots are countable?
 
  • #18
Dick
Science Advisor
Homework Helper
26,258
618
There are finitely many polynomials of degree n. So if I show that the number of polynomials is countable, I can automatically say the roots are countable?
You can't 'automatically' say anything without giving a reason. Give a reason.
 
  • #19
218
0
Well because for an integer polynomial of degree n, there are at most n roots.
 
  • #20
Dick
Science Advisor
Homework Helper
26,258
618
Well because for an integer polynomial of degree n, there are at most n roots.
That is certainly part of it. Nothing you are saying is wrong. I'm just not hearing the reason that the hint suggests you should be giving. Why is the number of integer polynomials of degree n countable (NOT finite)? You know it is. I know it is. Why is it?
 
  • #21
218
0
Is it because the sum of the absolute values of the integer coefficients, this sum will always correspond to a value in the set of all positive integers?
 
  • #22
Dick
Science Advisor
Homework Helper
26,258
618
Is it because the sum of the absolute values of the integer coefficients, this sum will always correspond to a value in the set of all positive integers?
No. That's not it at all. Take the polynomial ax+b with |a|<2 and |b|<2. Count them all. Really, how many are there? Give me a number. This is what the hint wants you to do.
 
  • #23
218
0
You have a polynomial of degree 1.
You have:
lal=1, lbl=0
lal=1, lbl=1
and you can't have lal=0.

So there are 2 polynomials?
 
  • #24
Dick
Science Advisor
Homework Helper
26,258
618
You have a polynomial of degree 1.
You have:
lal=1, lbl=0
lal=1, lbl=1
and you can't have lal=0.

So there are 2 polynomials?
Ok, we are getting somewhere. Actually a can be anything thing in {1,-1} and b can be anything in {1,0,-1} so I actually count 6=2*3 polynomials. The exact number isn't important. It just wants you to show the number is finite by giving an upper bound that is finite. I would say there are at most 3 choices for a and 3 choices for b and there is at most one root for each polynomial so the number of roots is definitely less than 3*3*1. Some of the polynomials I'm counting aren't degree 1 and some don't have roots and some have the same root, but its still an upper bound for the number of roots. Which is finite. What's an upper bound for a polynomial of degree n with |a_i|<m?
 
Last edited:
  • #25
218
0
Okay, I see how you did that. I'm not sure about the case of m, but I got that there are at most 2m-1 choices for each a_i, is that correct?

If it is, then there are n+1 coefficients, and each coefficient can have at most 2m-1 choices, so (2m-1)^(n+1) polynomials, and [(2m-1)^(n+1)]*n is an upper bound?

Edit: By a_i I took it as all the coefficients of the polynomial.
 
Last edited:

Related Threads on Proving algebraic numbers are countable?

  • Last Post
Replies
2
Views
17K
Replies
6
Views
1K
Replies
8
Views
1K
Replies
5
Views
749
  • Last Post
Replies
4
Views
5K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
11
Views
3K
  • Last Post
Replies
2
Views
991
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
5
Views
1K
Top