Proof that algebraic numbers are countable

In summary: It follows that ##A_n##, the set of algebraic numbers obtained as roots of any polynomial (with integer coefficients) of degree ##n##, can be written as a countable union of finite sets: ##\displaystyle A_n = \bigcup_{m=1}^{\infty}P_{nm}##. It follows that ##A_n## is countable. Since the countable union of countable sets is countable, ##\displaystyle A = \bigcup_{n=1}^{\infty}A_{n}##, which is the set of all algebraic numbers, is countable.
  • #1
Mr Davis 97
1,462
44

Homework Statement


Fix ##n,m \in \mathbb{N}##. The set of polynomials of the form ##a_nx^n + a_{n-1}x^{n-1} + \cdots + a_1x + a_0##
satisfying ##|a_n| + |a_{n-1}| + \cdots + |a_0| \le m## is finite because there are only a finite
number of choices for each of the coefficients (given that they must be integers.)
If we let ##A_{nm}## be the set of all the roots of polynomials of this form, then because
each one of these polynomials has at most ##n## roots, the set ##A_{nm}## is finite. Thus
##A_n##, the set of algebraic numbers obtained as roots of any polynomial (with
integer coefficients) of degree ##n##, can be written as a countable union of finite
sets: ##\displaystyle A_n = \bigcup_{m=1}^{\infty}A_{nm}##. It follows that ##A_n## is countable. Since the countable union of countable sets is countable, ##\displaystyle A = \bigcup_{n=1}^{\infty}A_{n}##, which is the set of all algebraic numbers, is countable.

Homework Equations

The Attempt at a Solution


I generally understand this proof, but I just have a few questions. In the first part of the proof, is it okay if ##a_n = 0##? That is, do the roots contained in ##A_{nm}## necessarily have to come from an nth degree polynomial, or can they also come from polynomials of degree n or less? For example, is ##A_{12}## a subset of ##A_{22}##?

If this is not the case, should we stipulate in the beginning that ##a_n \ne 0## so that the roots can actually be of an nth degree polynomial?
 
Last edited:
Physics news on Phys.org
  • #2
Generally what is meant by saying that a polynomial has degree n is that the position of the highest-position, non-zero coefficient is n. Thus, by definition a n-th degree polynomial cannot have ##a_n=0##. In order not to disrupt this, the degree -1 is awarded to the zero polynomial (although that doesn't affect this case, as only polynomials of positive degree are used in the definition of the algebraic numbers). So ##A_{12}## is generally not a subset of ##A_{22}##.
 
  • Like
Likes Mr Davis 97
  • #3
andrewkirk said:
Generally what is meant by saying that a polynomial has degree n is that the position of the highest-position, non-zero coefficient is n. Thus, by definition a n-th degree polynomial cannot have ##a_n=0##. In order not to disrupt this, the degree -1 is awarded to the zero polynomial (although that doesn't affect this case, as only polynomials of positive degree are used in the definition of the algebraic numbers). So ##A_{12}## is generally not a subset of ##A_{22}##.
So is it implicit in the following statement that ##a_n \ne 0##, even though ##a_n=0## could possibly satisfy the inequality stated?

The set of polynomials of the form ##a_nx^n + a_{n-1}x^{n-1} + \cdots + a_1x + a_0## satisfying ##|a_n| + |a_{n-1}| + \cdots + |a_0| \le m##
 
  • #4
This depends alone on whether you consider the ##A_{n}## as all roots of polynomials of degree exactly ##n## or of degree at most ##n##. One is a graduation and the other one a filtration. The "exactly of degree ##n##" makes probably more sense here to avoid multiple counts, which means ##a_n \neq 0##.
 
  • Like
Likes Mr Davis 97
  • #5
So to make the proof better, or at least more obvious, should I write at the beginning:

The set of polynomials of the form ##a_nx^n + a_{n-1}x^{n-1} + \cdots + a_1x + a_0## satisfying ##|a_n| + |a_{n-1}| + \cdots + |a_0| \le m##, where ##a_n \ne 0## is finite because there are only a finite number of choices for each of the coefficients (given that they must be integers.)?
 
  • #6
I would do so, because this way you count all roots of polynomials of degree ##n##. To be exact you get an upper bound, as there are still double counts as for ##(x-a)^n##, but each one has at most ##n## different roots. If ##a_n=0## would be allowed, then you count all roots of polynomials of degree lesser than ##n## again and again.
 
  • #7
I noticed that the proof doesn't state anywhere directly that the coefficients must be integers. Rather, it makes a comment in parentheses that implies the statement has already been made, which it hasn't.

Another way to write the first piece, taking care of that issue and maybe shortening the expression a bit, be:

For positive integers ##m,n##, let ##P_{nm}## be the set of all polynomials of degree ##n## with integral coefficients, such that the sum of the absolute values of each polynomial's coefficients is less than ##m##, and let ##A_{nm}## be the set of all roots of polynomials in ##A_{nm}##.
 

Related to Proof that algebraic numbers are countable

1. What is an algebraic number?

An algebraic number is a number that is a root of a polynomial equation with integer coefficients. This means that it can be expressed as a finite combination of addition, subtraction, multiplication, and division of integers.

2. How do you prove that algebraic numbers are countable?

The proof involves showing that there exists a one-to-one correspondence between the set of algebraic numbers and the set of natural numbers. This can be done by ordering the algebraic numbers in a systematic way and showing that each number can be assigned a unique natural number.

3. Why is it important to show that algebraic numbers are countable?

Proving that algebraic numbers are countable has important implications in number theory and mathematics. It helps us understand the structure of the real numbers and provides a foundation for more advanced mathematical concepts such as transcendental numbers.

4. Are all algebraic numbers rational numbers?

No, not all algebraic numbers are rational numbers. While all rational numbers are algebraic, there are also algebraic numbers that are irrational, such as the square root of 2 or pi.

5. What is the significance of the concept of countability in mathematics?

The concept of countability is important in mathematics because it helps us classify and compare the size of infinite sets. It also allows us to understand the structure and patterns within different types of numbers and mathematical objects.

Similar threads

  • Calculus and Beyond Homework Help
Replies
7
Views
370
  • Calculus and Beyond Homework Help
Replies
1
Views
666
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
5
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
418
  • Calculus and Beyond Homework Help
Replies
24
Views
1K
  • Calculus and Beyond Homework Help
Replies
8
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
515
  • Calculus and Beyond Homework Help
Replies
3
Views
908
  • Calculus and Beyond Homework Help
Replies
6
Views
358
Back
Top