Results 1 to 3 of 3

Math Help - Inductive Proof of Countability of Algebraic Numbers

  1. #1
    Member
    Joined
    Jul 2009
    Posts
    152

    Inductive Proof of Countability of Algebraic Numbers

    Recall that a complex number is said to be algebraic provided that it is a root of a polynomial with rational coefficients. To each algebraic number, there is a corresponding minimal polynomial that is both irreducible and monic (that is, its leading coefficient is 1).

    It was shown by Cantor that the set of all algebraic numbers is countable. Every proof of this I have ever seen uses an "index" constructed to count the set of all minimal polynomials. This has always seemed sort of artificial to me. I propose the following inductive proof, and it is my hope that someone may be able to verify whether or not it is correct; for some reason, I've always wondered whether or not there is a logical error somewhere in it. Here goes:

    Since every algebraic number has a unique minimal polynomial, and to each minimal polynomial there corresponds a finite number of algebraic roots, it is sufficient to show that the set of all minimal polynomials is countable. We proceed by induction. All first degree minimal polynomials have the form x+r, where r\in\mathbb{Q}, and thus are clearly equivalent to \mathbb{Q}, and therefore countable. Suppose then that the set of all minimal polynomials having degree n or less is countable. Now the n+1-th degree minimal polynomials have the form x^{n+1} + sp(x), where p(x) is an n-th (or less) degree minimal polynomial, and s\in\mathbb{Q}. Hence as s ranges over the rational numbers, sp(x) yields countably many countable sets, and so the n+1-th degree minimal polynomials are countable. QED.

    Does that follow?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Failure's Avatar
    Joined
    Jul 2009
    From
    Zürich
    Posts
    555
    Quote Originally Posted by AlephZero View Post
    Recall that a complex number is said to be algebraic provided that it is a root of a polynomial with rational coefficients. To each algebraic number, there is a corresponding minimal polynomial that is both irreducible and monic (that is, its leading coefficient is 1).

    It was shown by Cantor that the set of all algebraic numbers is countable. Every proof of this I have ever seen uses an "index" constructed to count the set of all minimal polynomials. This has always seemed sort of artificial to me. I propose the following inductive proof, and it is my hope that someone may be able to verify whether or not it is correct; for some reason, I've always wondered whether or not there is a logical error somewhere in it. Here goes:

    Since every algebraic number has a unique minimal polynomial, and to each minimal polynomial there corresponds a finite number of algebraic roots, it is sufficient to show that the set of all minimal polynomials is countable. We proceed by induction. All first degree minimal polynomials have the form x+r, where r\in\mathbb{Q}, and thus are clearly equivalent to \mathbb{Q}, and therefore countable. Suppose then that the set of all minimal polynomials having degree n or less is countable. Now the n+1-th degree minimal polynomials have the form x^{n+1} + sp(x), where p(x) is an n-th (or less) degree minimal polynomial, and s\in\mathbb{Q}. Hence as s ranges over the rational numbers, sp(x) yields countably many countable sets, and so the n+1-th degree minimal polynomials are countable. QED.

    Does that follow?
    Probably. But you should, in my opinion, for the sake of clarity at least mention two things: that an n+1 degree polynomial has at most n+1 roots and that your argument shows that the algebraic real numbers are a countable union of countable sets - and therefore countable.

    The more typical argument for the countability of the algebraic numbers seems to go like this: first, we may limit ourselves to showing that there are only countable polynomials with integer coefficients. Second, we count polynomials p(x)=a_nx^2+a_{n-1}x^{n-1}+\cdots a_0 with a_n,a_{n-1},\ldots, a_0\in \mathbb{Z} in this way: let m := \mathrm{deg}(p)+\sum_{k=0}^{\mathrm{deg}(p)}|a_k|. Starting with m=1 and increasing by +1 we count the number of polynomials (and roots) we get (at most) for this value of m. Answer: always only a finite number. So the algebraic numbers are the countable union of finite sets, thus countable.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jul 2009
    Posts
    152
    Quote Originally Posted by Failure View Post
    Probably. But you should, in my opinion, for the sake of clarity at least mention two things: that an n+1 degree polynomial has at most n+1 roots and that your argument shows that the algebraic real numbers are a countable union of countable sets - and therefore countable.

    The more typical argument for the countability of the algebraic numbers seems to go like this: first, we may limit ourselves to showing that there are only countable polynomials with integer coefficients. Second, we count polynomials p(x)=a_nx^2+a_{n-1}x^{n-1}+\cdots a_0 with a_n,a_{n-1},\ldots, a_0\in \mathbb{Z} in this way: let m := \mathrm{deg}(p)+\sum_{k=0}^{\mathrm{deg}(p)}|a_k|. Starting with m=1 and increasing by +1 we count the number of polynomials (and roots) we get (at most) for this value of m. Answer: always only a finite number. So the algebraic numbers are the countable union of finite sets, thus countable.
    Thanks! On your first two points: I believe the fact that the minimal polynomials of a given degree will produce a finite number of roots is covered by my initial argument that a suitable enumeration of the minimal polynomials will produce a suitable enumeration of the algebraic numbers, but of course I may be wrong about that...? Your second point is well-taken; the argument about countable unions of countable sets is implied, but I should have made it explicit.

    On your third point: you've given the "index" proof that I mentioned, which is the only one I've ever seen. I've never cared for it—it seems, as I say, "artificial" to me somehow in that it counts the polynomials in a way that I find inelegant... I formulated the inductive proof because I felt it counted the polys. in a more straight-forward way....

    In any event, thanks for looking it over, and providing such a clear and thoughtful answer.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Algebraic Numbers Proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 10th 2011, 02:47 PM
  2. Proof: All rational numbers are algebraic numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 5th 2010, 10:26 AM
  3. Countability Proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: January 21st 2009, 08:56 AM
  4. Countability of the irrational numbers
    Posted in the Advanced Math Topics Forum
    Replies: 10
    Last Post: November 16th 2008, 12:42 AM
  5. Proof of countability
    Posted in the Advanced Algebra Forum
    Replies: 7
    Last Post: February 15th 2007, 07:35 PM

Search Tags


/mathhelpforum @mathhelpforum