1. Limited time only! Sign up for a free 30min personal 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!

Size of the Algebraic Numbers

  1. Sep 27, 2010 #1
    How would I show that the set of all algebraic reals is countable? Could I a just assume a function p(f(x)) maps a polynomial f(x) to a set containing it’s real roots? I’m not sure if I would need to argue p(x) exist, since the fundamental theorem of algebra seems to suggest it’s okay, but Abel-Ruffini Theorem seems to suggest I can’t.
     
  2. jcsd
  3. Sep 27, 2010 #2

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    p(x) isn't a function (one polynomial has more than one root), so that's kind of a problem. You need to be a little bit more clever than that, but you certainly have the right idea. Abel-Ruffini has nothing to do with this: that's a statement about finding a solution in terms of radicals, whereas p(x) is some horribly disfigured function that you probably hit with a sledgehammer to make it fit

    The proof that the rationals are countable might be a good place to draw inspiration from
     
  4. Sep 27, 2010 #3
    P(x) would be a function since it maps to a single set. That set would contain all of the roots.
     
  5. Sep 28, 2010 #4
    I think I got it, not very formal, but does this look good?

    Claim: Let A_n where n is a natural, be the set of all the roots of a nth degree polynomial. A_n is countable.

    Clearly this is true is n = 1 since this set would be the rational numbers.

    Suppose the claim holds for naturals less than or equal to n. Consider polynomials of degree n+1. They will be in the form of ax^n+1 + P_n. Where P_n is at most an nth degree polynomial and a is an integer. By the fundamental theorem of algebra each of these ax^n+1 + P_n polynomials have the less than or equal number, or one more root than P_n. Thus A_n+1 has to be less than P_n x {1,0}, which is countable. Thus the claim is true.

    The union of all A_n would be the algebraic numbers. Each A_n was just proved to be countable. Since n is a natural this a countable union of countable sets, which is countable.
     
    Last edited: Sep 28, 2010
  6. Oct 2, 2010 #5
    If you like a different but similar proof you could show the set of all polynomials with integer coefficients is countable. (For any n the set of all n-tuples of integers is countable, hence the union of these sets is countable. This shows the set of all the polynomials with integer coefficents is countable)
     
  7. Oct 4, 2010 #6
    I think you're overengineering the solution. The basic idea is pretty simple.

    We know that the polynomials are countable.

    We know that an n-degree polynomials have at most n roots.

    So we can write out a sequence:

    Polynomial #1, Smallest root
    Polynomial #1, 2nd Smallest root
    ...
    Polynomial #1, Biggest root
    Polynomial #2, Smallest root
    Polynomial #2, 2nd Smallest root
    ...
    Polynomial #2, Biggest root
    ...
    Polynomial #n, Some root
    ...

    We have a sequence of all the algebraic numbers. (And it's obviously countable). This sequence contains duplicates, though. If we remove all the duplicate entries, the list is still infinite. And an infinite subset of a countable set is countable.

    You can harden that into a formal proof, but that's the idea.
     
  8. Oct 6, 2010 #7
    This list doesn’t work, since it relies on the successor to an infinite amount of elements. For example, tell me what number in your list would (2)^1/5 be. There is no way you can do this, since 2^15 would come after all of the rational numbers.
     
    Last edited: Oct 6, 2010
  9. Oct 6, 2010 #8
    It does not rely on any successor function.

    The only thing it relies on is that the cartesian product of two countable sets is countable.

    Let's say, for illustration, the polynomial x^5 - 2 is the n-th polynomial in your favorite enumeration. And let's say k is the sum of the count of roots for polynomials 1, 2, 3, ..., n. (In most enumerations, k is probably going to be a very, very big number). And lastly, let's assume, for simplicity, that x^5 - 2 is the FIRST polynomial in the chosen enumeration with the root of 2^(1/5). Then the algebraic number 2^(1/5) has an index of k+1.

    With a minor tweak to the idea above, it works with any root. The index is always finite and is unique. Thus, we have defined a bijection to the integers, and the algebraic numbers are countable.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook