- #1
JohnDuck
- 76
- 0
Homework Statement
"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].
Homework Equations
See above.
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: