Can the Set of Algebraic Reals Be Shown to Be Countable?

[JonF]

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.

 

[Office_Shredder]

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

 

[JonF]

P(x) would be a function since it maps to a single set. That set would contain all of the roots.

 

[JonF]

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.

 

[deluks917]

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)

 

[Tac-Tics]

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.

 

[JonF]

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.

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.

 

[Tac-Tics]

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.

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.