1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proving algebraic numbers are countable?

  1. Sep 30, 2012 #1
    1. The problem statement, all variables and given/known data

    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.

    2. Relevant 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.

    3. 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?
     
  2. jcsd
  3. Sep 30, 2012 #2

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
  4. Sep 30, 2012 #3
    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...
     
  5. Sep 30, 2012 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  6. Sep 30, 2012 #5
    I'm still confused about how to apply the hint to my proof though.
     
  7. Sep 30, 2012 #6

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  8. Sep 30, 2012 #7
    Would this be different than proving the set of all algebraic numbers is countable?
     
  9. Sep 30, 2012 #8

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  10. Sep 30, 2012 #9
    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.
     
  11. Sep 30, 2012 #10

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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?
     
  12. Sep 30, 2012 #11

    Yes, I see what you mean.
     
  13. Sep 30, 2012 #12

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  14. Sep 30, 2012 #13
    Would I do this explicitly?
     
  15. Sep 30, 2012 #14

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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?
     
  16. Sep 30, 2012 #15
    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?
     
  17. Sep 30, 2012 #16

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  18. Sep 30, 2012 #17
    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?
     
  19. Sep 30, 2012 #18

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    You can't 'automatically' say anything without giving a reason. Give a reason.
     
  20. Sep 30, 2012 #19
    Well because for an integer polynomial of degree n, there are at most n roots.
     
  21. Sep 30, 2012 #20

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Proving algebraic numbers are countable?
  1. Prove is countable (Replies: 4)

  2. Prove set is countable (Replies: 2)

Loading...