Prove that the set of all algebraic numbers is a countable set

[s3a]

Homework Statement

Prove that the set of all algebraic numbers is a countable set.

Solution:
Algebraic numbers are solutions to polynomial equations of the form a_0 x^n + a_1 x^(n – 1) + . . . + a_n = 0 where a_0, a_1, . . . , a_n are integers.

Let P = |a_0| + |a_1| + . . . + |a_n| + n
. For any given value of P there are only a finite number of possible polynomial equations and thus only a finite number of possible algebraic numbers. Write all algebraic numbers corresponding to P = 1, 2, 3, 4, . . . , avoiding repetitions. Thus, all algebraic numbers can be placed into 1-1 correspondence with the natural numbers and so are countable.

The problem along with the solution are also given in the TheProblemAndSolution.jpg file attached.

Homework Equations

P = |a_0| + |a_1| + . . . + |a_n| + n
a_0 x^n + a_1 x^(n – 1) + . . . + a_n = 0

The Attempt at a Solution

I'm stuck at the part of the solution that says P = |a_0| + |a_1| + . . . + |a_n| + n. My problem is not just with the computation; I have no idea what P even represents. I'm assuming the letter P was chosen because it's the first letter of the word "polynomial", but then why is that equation different than that of the equation above it that equals zero?

If someone could please explain to me what is going on there, it would be GREATLY appreciated!

 

[Joffan]

P is just a characteristic number for that polynomial, not a solution for the polynomial. In general, there will be a lot of polynomials with the same characteristic number, but for any given P it will be a finite number of different polynomials that have that characteristic number. For example, some polynomials for P=3 are

$$\begin{align}
x+1 &=0 \\
-x+1 &=0 \\
x-1 &=0 \\
-x-1 &=0 \\
2x &=0 \\
-2 x &=0 \\
x^2 &=0 \\
-x^2 &=0 \end{align}$$

which is of course a very dull set of equations, but that's what happens when P is small. Still I hope you can see than there are only so many ways you can juggle the integer coefficients (and order) within anyone value of P. That means that eventually, as you allow P to increase, you will get to any desired polynomial by counting through the solutions.

I suggest you try writing the equations for P=4.

(Actually it strikes me that, without loss of generality, we could count zero as our first algebraic number, then we can require a positive a_n and of course at least one more non-zero coefficient - leaving only two of the above valid. But that is unnecessary for the proof, although the question does ask you to avoid repetitions.)

 

[s3a]

Thanks for your answer.

Tell me if I missed anything, but after having analyzed your post, I get the following.:
For P = 1:
0x = 0

For P = 2:
x = 0
–x = 0

For P = 4:
x + 2 = 0
–x + 2 = 0
x – 2 = 0
–x – 2 = 0
2x + 1 = 0
–2x + 1 = 0
2x – 1 = 0
–2x – 1 = 0
x^2 + 1 = 0
–x^2 + 1 = 0
x^2 – 1 = 0
–x^2 – 1 = 0
x^3 = 0
–x^3 = 0

Also, could you please elaborate on the term “characteristic number” because searching that term online yields too many different results, and I'm having trouble finding information that is specific to my situation.

 

[D H]

For P = 1:
0x = 0

That's not right. The leading coefficient has to be non-zero. Otherwise this characteristic number P is not well defined. For example, allowing leading zeros means x+1=0 (P=3) can also be written as 0x^2+x+1=0 (P=4), or 0x^3+0x^2+x+1=0 (P=5), etc.

The number of polynomials with a coefficient P=1 is 0.

For P = 4:
x + 2 = 0
...

You missed some, s3a. For example, you missed 2x^2 (there are others).

Also, could you please elaborate on the term “characteristic number” because searching that term online yields too many different results, and I'm having trouble finding information that is specific to my situation.

A "characteristic" is just some mechanism for categorizing something. This particular characteristic isn't of much use other than showing that the set of algebraic numbers is countable.

 

[D H]

Aside: One way to deal the 1+x vs 1+x+0*x² problem is that the n in the definition of P is the degree of the leading term. With this, 1+x has a characteristic P of 3, as does 1+x+0*x².One thing I don't like about Rudin's proof is that it's a bit hand-wavy. It would be more rigorous if there was a way to map a polynomial p to an integer. Can such a mapping be found?

Just for grins, I wrote a program to count the number of polynomials in the set P_n, where P_n comprises all the polynomials p(x) with integer coefficients such that P(p)=n. The set P₀ is undefined; we need to start with n=1.

n=1 is also a bit problematic. There are two such polynomials whose characteristic is 1: 1 and -1. Neither of these has any solutions to p(x)=0. If we count only those polynomials that have a solution to p(x)=0 the set P₁ is empty and has a cardinality of 0. If we ignore this problem, P₁ has a cardinality of 2. This problem vanishes for all n>1. I'll denote the cardinality of P₁ with a question mark. With that, the sequence of cardinalities is {?,2,8,22,56,138,336,814,1968,4754,...}. Except for that uncertain leading elements, these are the even elements of Sloane's A098894 (link: https://oeis.org/A098894]).[/PLAIN] That smacks a bit too much of numerology.

Note that if a polynomial p is in the set P_n, then so is -p. We're double counting in a sense. Halving each element of the above sequence yields {?,1,4,11,28,69,168,407,984,2377,...}. This is Sloane's A005409 (link: [url=[PLAIN]https://oeis.org/A005409]).[/PLAIN] Sequence A005409 is the "number of polynomials of height n". This doesn't smack of numerology. This is more or less what we want.

Sloane's A005409 has a recursive expression: a(n) = 2a(n-1)+a(n-2)+2. This recursive expression has the closed form solution a(n)=((1+sqrt(2))^n - (1-sqrt(2))^n)/(2*sqrt(2))-1. This expression has a value of 0 for n=1. Note that Sloane's A005409 starts with 1 rather than 0; that sequence makes a(1) a special case.

This gives us the desired mapping. Doubling that closed form expression for a(n) brings us back to the original sequence of the cardinalities. To map a polynomial p(x) to a unique integer N,

• Find the characteristic P of the polynomial.
• Generate the set P_P via some fixed algorithm and find the index n of the polynomial p in this set, starting from 1.
• ##N = \sum_{i=1}^{P-1} 2a(i) + n-1##.

 

[s3a]

Thanks, D H.

Please confirm that the following update is correct (where the updated stuff are bolded).:
For P = 0:
The set of polynomials for which P = 0 is undefined. (Am I using correct terminology here?)

For P = 1:
The set of polynomials for which P = 1 is defined but empty. (Am I using correct terminology here?)

For P = 2:
x = 0
–x = 0

For P = 4:
x + 2 = 0
–x + 2 = 0
x – 2 = 0
–x – 2 = 0
2x + 1 = 0
–2x + 1 = 0
2x – 1 = 0
–2x – 1 = 0
x^2 + 1 = 0
–x^2 + 1 = 0
x^2 – 1 = 0
–x^2 – 1 = 0
x^3 = 0
–x^3 = 0
2x^2 = 0
–2x^2 = 0
3x = 0
–3x = 0

 

[D H]

Thanks, D H.

Please confirm that the following update is correct (where the updated stuff are bolded).:
For P = 0:
The set of polynomials for which P = 0 is undefined. (Am I using correct terminology here?)

That's what I used. If you allow leading zeros and count this as part of the polynomial, you'll run into a big problem with P=0. There's one such polynomial, 0. Here's the problem: 0=0 is a tautology. Pi and e are solutions to 0=0. All numbers, algebraic and non-algebraic, are solutions to 0=0.

The easy way around this problem is to say the leading coefficient must be non-zero. Whether you want to say {p|P(p)=0} is empty or undefined depends on how you look at things.

For P = 1:
The set of polynomials for which P = 1 is defined but empty. (Am I using correct terminology here?)

There's an issue here. The polynomials p(x)=1 and p(x)=-1 satisfy the condition P(p)=1. However, 1=0 and -1=0 are contradictions. If you're looking at things from the perspective of {p|P(p)=1}, the cardinality of that set is 2. If you're looking at things from the perspective of polynomials p(x) that do have solution to p(x)=1, the cardinality becomes zero.

For P = 2:
x = 0
–x = 0

Looks good.

For P = 4:
x + 2 = 0
–x + 2 = 0
x – 2 = 0
–x – 2 = 0
2x + 1 = 0
–2x + 1 = 0
2x – 1 = 0
–2x – 1 = 0
x^2 + 1 = 0
–x^2 + 1 = 0
x^2 – 1 = 0
–x^2 – 1 = 0
x^3 = 0
–x^3 = 0
2x^2 = 0
–2x^2 = 0
3x = 0
–3x = 0

There are only 18 polynomials there. You should have 22. You missed the four polynomials along the lines of x^2+x.

Note: My count of 22 excludes the polynomials p(x)=4 and p(x)=-4. Both of these do have a characteristic P=4, but setting p(x)=0 results in a contradiction. I didn't count those contradictions. There's no problem with counting them. You'll just get a different result. The end result will still be the same: You can map a polynomial to a unique integer. The set of polynomials is countable, and (with a bit more work), the set of algebraic numbers is countable.

It helps, a lot, to develop an algorithm to generate those polynomials. In fact, you don't have to generate all of them to count them. There are two polynomials of the form x^2: x^2 and -x^2. There are four of the form x^2+x: x^2+x, x^2-x, -x^2+x, and -x^2-x. Once you get to P=5, you'll start running into polynomials such as x^2+x+1. There are eight polynomials of this form. With P=7, you'll run into polynomials of the form x^3+x^2+x+1. There are 16 of these critters.

Rhetorical question: Do you need to generate all of them? The answer is no. You just need to know that x^2+x+1 represents eight polynomials. You don't even need to explicitly generate the polynomial x^2+x+1. All that's needed is the coefficient list, (1,1,1). It's much easier to come up with an algorithm when you cast away the x, x^2, x^3, etc and just work with the coefficient list.

 

[s3a]

Whether you want to say {p|P(p)=0} is empty or undefined depends on how you look at things.

There's an issue here. The polynomials p(x)=1 and p(x)=-1 satisfy the condition P(p)=1. However, 1=0 and -1=0 are contradictions. If you're looking at things from the perspective of {p|P(p)=1}, the cardinality of that set is 2. If you're looking at things from the perspective of polynomials p(x) that do have solution to p(x)=1, the cardinality becomes zero.

I'm looking at this from the perspective that the polynomials p(x) have a solution to p(x) = 0.

There are only 18 polynomials there. You should have 22. You missed the four polynomials along the lines of x^2+x.

Okay, so assuming that I'm looking at things from the perspective that polynomials p(x) have a solution to p(x) = 0, is the following correct? (Sorry for being so pedantic.):
For P = 0:
The set of polynomials for which P = 0 is undefined.

For P = 1:
The set of polynomials for which P = 1 is defined but empty.

For P = 2: (You already said this looks good, but I'm just including it for completeness of my work.)
x = 0
–x = 0

For P = 4:
x + 2 = 0
–x + 2 = 0
x – 2 = 0
–x – 2 = 0
2x + 1 = 0
–2x + 1 = 0
2x – 1 = 0
–2x – 1 = 0
x^2 + 1 = 0
–x^2 + 1 = 0
x^2 – 1 = 0
–x^2 – 1 = 0
x^3 = 0
–x^3 = 0
2x^2 = 0
–2x^2 = 0
3x = 0
–3x = 0
x^2 + x = 0
–x^2 + x = 0
x^2 – x = 0
–x^2 – x = 0

 

[bondsergey]

The main idea:
One needs an n in the formula of P since if we delete n in the formula of P we will have infinitely many polynomials for any P>2.
For example let P= |a_0| + |a_1| + . . . + |a_n|; For P=3 we will have infinitely many polynomials. For example of the form 2x^n-1=0 (n=1,2,3...up to infinity)