prove that the set of all algebraic numbers is countable
Answers
The problem though, is that I did not use the hint provided in the text, so maybe this proof is invalid or that there is an alternate (simpler) proof? Please help me out here. Thanks in advance.
Proof:
The set of integers is countable, we have this following theorem:
Let A be a countable set, and let Bn be the set of all n-tuples (a1,...,an), where ak∈A,k=1,...,n, and the elements a1,...,an need not be distinct. Then Bn is countable.
So by this theorem, the set of all (k+1)-tuples (a0,a1,...,ak) with a0≠0 is also countable.
Let this set be represented by Zk. For each a a∈Zk consider the polynomial a0zk+a1zk−1+...+ak=0.
From the fundamental theorem of algebra, we know that there are exactly k complex roots for this polynomial.
We now have a series of nested sets that encompass every possible root for every possible polynomial with integer coefficients. More specifically, we have a countable number of Zks, each containing a countable number of (k+1)-tuples, each of which corresponds with k roots of a k-degree polynomial. So our set of complex roots (call it R) is a countable union of countable unions of finite sets. This only tells us that R is at most countable: it is either countable or finite.
To show that R is not finite, consider the roots for 2-tuples in Z1. Each 2-tuple of the form (−1,n) corresponds with the polynomial −z+n=0 whose solution is z=n. There is clearly a unique solution for each n∈Z, so R is an infinite set. Because R is also at most countable, this proves that R is countable.The problem though, is that I did not use the hint provided in the text, so maybe this proof is invalid or that there is an alternate (simpler) proof? Please help me out here. Thanks in advance.
Proof:
The set of integers is countable, we have this following theorem:
Let A be a countable set, and let Bn be the set of all n-tuples (a1,...,an), where ak∈A,k=1,...,n, and the elements a1,...,an need not be distinct. Then Bn is countable.
So by this theorem, the set of all (k+1)-tuples (a0,a1,...,ak) with a0≠0 is also countable.
Let this set be represented by Zk. For each a a∈Zk consider the polynomial a0zk+a1zk−1+...+ak=0.
From the fundamental theorem of algebra, we know that there are exactly k complex roots for this polynomial.
We now have a series of nested sets that encompass every possible root for every possible polynomial with integer coefficients. More specifically, we have a countable number of Zks, each containing a countable number of (k+1)-tuples, each of which corresponds with k roots of a k-degree polynomial. So our set of complex roots (call it R) is a countable union of countable unions of finite sets. This only tells us that R is at most countable: it is either countable or finite.
To show that R is not finite, consider the roots for 2-tuples in Z1. Each 2-tuple of the form (−1,n) corresponds with the polynomial −z+n=0 whose solution is z=n. There is clearly a unique solution for each n∈Z, so R is an infinite set. Because R is also at most countable, this proves that R is countable.