1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prove algebraic numbers are countable

  1. May 29, 2007 #1
    1. The problem statement, all variables and given/known data
    "A complex number z is said to algebraic if there are integers [itex]a_{0},...,a_{n}[/itex], not all zero, such that:

    [tex]a_{0} z^{n} + a_{1} z^{n-1} +...+ a_{n-1} z + a_{0} = 0[/tex].

    Prove that the set of all algebraic numbers is countable. Hint: For every positive integer N there are only finitely many equations with:

    [tex]n + |a_{0}| +...+ |a_{n}| = N[/tex].

    2. Relevant equations
    See above.

    3. The attempt at a solution
    I've constructed a proof by induction that goes as follows: Consider the set [itex]A_{1}[/itex] of algebraic numbers such that [itex]a_{0}z + a_{1} = 0[/itex]. It simply defines the rational numbers, and therefore is countable. Assume the set [itex]A_{n}[/itex] of algebraic numbers s.t. [itex]a_{0} z^{n} +...+ a_{n} = 0[/itex] is countable. Consider the set of algebraic numbers [itex]A_{n+1}[/itex] s.t. [itex]a_{0} z^{n+1} + a_{1} z^{n} +...+ a_{n+1} = 0[/itex]. Choose a fixed [itex]a_{0}=a[/itex]; then this subset of [itex]A_{n+1}[/itex] can be put in one-to-one correspondence with [itex]A_{n}[/itex] (and is therefore countable). Simply associate each element of this subset with the element of [itex]A_{n}[/itex] in which all of the coefficients are equal (excluding the leading term [itex]az^{n+1}[/itex]). For example, [itex]az^{n+1}+3z^{n}+4 = 0[/itex] is associated with [itex]3z^{n}+4 = 0[/itex]. [itex]A_{n+1}[/itex] is the union of all such subsets as a ranges through the integers--and as the union of a countable amount of countable sets, [itex]A_{n+1}[/itex] is countable.

    Edit: There's a special case when all the coefficients are equal to zero except a, in which case one cannot use the above method to put this subset in one-to-one correspondence with [itex]A_{n}[/itex]--however, this subset is also countable as it can easily be put in one-to-one correspondence with the integers. Thus [itex]A_{n+1}[/itex] is still countable.

    Thus by induction all such [itex]A_{n}[/itex] are countable. The set of all algebraic numbers is the union of all such [itex]A_{n}[/itex] as n ranges through the natural numbers, and thus is countable.

    My question then is not how to prove that the set of algebraic numbers is countable per se (though if there's an error in my proof please let me know), but rather how would one prove it using the given hint? I struggled for a while trying to figure it out that way before I gave up and tried my above approach.
    Last edited: May 29, 2007
  2. jcsd
  3. May 30, 2007 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    You have to use the hint to partition the algebraic numbers into countably many finite sets. Or rather partition the set of polynomials into countably many finite sets (which is strictly different, but implies the result).

    So, what should I let B_N be (suggestively using the notation of N as in your post).
  4. May 30, 2007 #3
    I think I see the gist of it. So, for example, [itex]B_{2}[/itex] would be the set of all polynomials such that [itex]n + |a_{0}| +...+ |a_{n}| = 2[/itex]. Since all the terms are positive and at least one coefficient is nonzero, 2-n must be an integer greater than or equal to 1 and less than 2 (which only leaves 1, which further implies n equals 1). Only two equations satisfy this, namely [itex]-x = 0[/itex] and [itex]x = 0[/itex]. Since each such [itex]B_{n}[/itex] has a finite number of elements, their union as n ranges through the natural numbers is countable.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Prove algebraic numbers are countable
  1. Prove is countable (Replies: 4)

  2. Prove set is countable (Replies: 2)