Thread: Proof of countability

I have no clue how to do this:

A real number is said to be algebraic if it is a root of a polynomial equation

AnX^n + ..... A1X + A0 = 0
with integer coefficients. Note that algebraic numbers inclde the rationals and all roots of rationals (such as sqrt(2), cubert(5), ect.) If a number is not algebraic it is called transcendental.

A) show that the set of polynomials with integer coefficients is countable.
B) Show that the set of algebraic numbers is countable.
c) are thermore algebraic numbers or transcendental numbers?

If you are in a course that requires you to understand the proof of part A, then it is absolutely improvement for YOU to find a proof for yourself. There are many ways to do this problem. Most of them require the following theorem: “A countable union of countable sets is countable”. One way I like to approach this problem is to prove this: “For each n, prove the set of all n-tuples of integers is countable”. For example any triple (3-tuple) of integers corresponds to a polynomial of degree of at most two with integer coefficients. Thus the set A is countable; there is a one-to-one correspondence between elements of set A and elements in set B; B is also one-to-one to C.

I reaize there is multiple ways, I just dont know how to begin this problem

Originally Posted by luckyc1423

I reaize there is multiple ways, I just dont know how to begin this problem

Well O.K.!
Start here: : “For each n, prove the set of all n-tuples of integers is countable”.

I guess I jus dont have a clue...my professor said thiswas the hardestproblem out of the batch

Originally Posted by luckyc1423

I guess I jus dont have a clue...my professor said thiswas the hardestproblem out of the batch

O.K. Again.
Can you prove that the set of integers is countable?
If the answer is yes, we can continue.
If the answer is no, then you need to seek "sit-down help" with a real person!

Originally Posted by luckyc1423

A) show that the set of polynomials with integer coefficients is countable.

This is what Plato said. The set is some,
A_0+A_1x+A_2x^2+....
Meaning you can enumarate all the coefficientes.
Yet the coefficietns are integers and hence countable.
Thus in total we have a countable untion of countably many sets.
Hence countable.

B) Show that the set of algebraic numbers is countable.

For each polynomial we have at most n solutions where n>0 is degree of the polynomial. And this time a finite union of countable many sets. Vice versa any algebraic number is contained in a polynomial. Thus we listed all algebraic numbers.

c) are thermore algebraic numbers or transcendental numbers?

Transcendental because otherwise their union (which is countable) will imply the countability of the reals, an impossibility.

Thanks so much! That was a great deal of help!!