Inductive Proof of Countability of Algebraic Numbers

**AlephZero** · August 5th 2009, 08:21 AM

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?

**Failure** · August 5th 2009, 08:53 AM

Originally Posted by AlephZero

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.

**AlephZero** · August 5th 2009, 09:04 AM

Originally Posted by Failure

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.

Thread: Inductive Proof of Countability of Algebraic Numbers

LinkBack

Thread Tools

Display

Inductive Proof of Countability of Algebraic Numbers

Similar Math Help Forum Discussions

Algebraic Numbers Proof

Proof: All rational numbers are algebraic numbers

Countability Proof

Countability of the irrational numbers

Proof of countability

Search Tags