Results 1 to 8 of 8

Math Help - Proof of countability

  1. #1
    Junior Member
    Joined
    Jul 2006
    Posts
    73

    Proof of countability

    I have no clue how to do this:

    A real number is said to be algebraic if it is a root of a polynomial equation

    AnX^n + ..... A1X + A0 = 0
    with integer coefficients. Note that algebraic numbers inclde the rationals and all roots of rationals (such as sqrt(2), cubert(5), ect.) If a number is not algebraic it is called transcendental.

    A) show that the set of polynomials with integer coefficients is countable.
    B) Show that the set of algebraic numbers is countable.
    c) are thermore algebraic numbers or transcendental numbers?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,964
    Thanks
    1784
    Awards
    1
    If you are in a course that requires you to understand the proof of part A, then it is absolutely improvement for YOU to find a proof for yourself. There are many ways to do this problem. Most of them require the following theorem: “A countable union of countable sets is countable”. One way I like to approach this problem is to prove this: “For each n, prove the set of all n-tuples of integers is countable”. For example any triple (3-tuple) of integers corresponds to a polynomial of degree of at most two with integer coefficients. Thus the set A is countable; there is a one-to-one correspondence between elements of set A and elements in set B; B is also one-to-one to C.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jul 2006
    Posts
    73
    I reaize there is multiple ways, I just dont know how to begin this problem
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,964
    Thanks
    1784
    Awards
    1
    Quote Originally Posted by luckyc1423 View Post
    I reaize there is multiple ways, I just dont know how to begin this problem
    Well O.K.!
    Start here: : “For each n, prove the set of all n-tuples of integers is countable”.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jul 2006
    Posts
    73
    I guess I jus dont have a clue...my professor said thiswas the hardestproblem out of the batch
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,964
    Thanks
    1784
    Awards
    1
    Quote Originally Posted by luckyc1423 View Post
    I guess I jus dont have a clue...my professor said thiswas the hardestproblem out of the batch
    O.K. Again.
    Can you prove that the set of integers is countable?
    If the answer is yes, we can continue.
    If the answer is no, then you need to seek "sit-down help" with a real person!
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by luckyc1423 View Post

    A) show that the set of polynomials with integer coefficients is countable.
    This is what Plato said. The set is some,
    A_0+A_1x+A_2x^2+....
    Meaning you can enumarate all the coefficientes.
    Yet the coefficietns are integers and hence countable.
    Thus in total we have a countable untion of countably many sets.
    Hence countable.
    B) Show that the set of algebraic numbers is countable.
    For each polynomial we have at most n solutions where n>0 is degree of the polynomial. And this time a finite union of countable many sets. Vice versa any algebraic number is contained in a polynomial. Thus we listed all algebraic numbers.
    c) are thermore algebraic numbers or transcendental numbers?
    Transcendental because otherwise their union (which is countable) will imply the countability of the reals, an impossibility.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Jul 2006
    Posts
    73
    Thanks so much! That was a great deal of help!!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Interval Countability proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 12th 2011, 05:29 PM
  2. Countability of Subsets proof
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: December 10th 2010, 08:19 AM
  3. Countability proof.
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: November 29th 2010, 10:14 AM
  4. Inductive Proof of Countability of Algebraic Numbers
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: August 5th 2009, 10:04 AM
  5. Countability Proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: January 21st 2009, 09:56 AM

Search Tags


/mathhelpforum @mathhelpforum