Prove Countability: Algebraic Numbers

[quasar_4]

So in general, do I always need to use induction to prove that a set is countable?

I'm trying to prove that the set of algebraic numbers is countable, but not sure if I am supposed to do it by induction. I am not sure how else to do it.

 

[morphism]

You don't "need to" use induction, but in this case an inductive-type argument is very helpful. Algebraic numbers are roots of polynomials - so it might be a good idea to consider polynomials of degree n separately.

 

[quasar_4]

ok, so the induction would be done on the degree of the polynomial...

I was thinking maybe I could map each algebraic number to the polynomial(s) of which it is a root. Then use this definition of the "height" of the polynomial (in our book, it's the sum of the degree of the polynomial with the absolute value of the coefficients of the poly.). I think it is reasonable to say that since each polynomial of degree n has at most n roots, that the set of algebraic numbers corresponding to all the polynomials of height h is at most countable (I hope this is strong enough).

Then if I take the union of the sets of differing heights, I'd be taking the union of at most countable sets, which must also be at most countable...

where does the induction step fit in? I guess I'm not sure what to show.. that the idea holds for the polynomials of degree 1, then show n => n+1?

 

[morphism]

Why should there be an inductive step?

A key point that you might have missed is that algebraic numbers are roots of polynomials with rational coefficients. So for each n, the set P_n of polynomials with rational coefficients of degree <= n is countable. Each p in P_n has at most n roots. Let A_n denote the set of roots of all polynomials in P_n; this is a countable union of finite things, and is thus countable. Finally, the set of algebraic numbers is the union of the A_n's, and is thus countable (being also a countable union of countable sets).

This is pretty much your argument, and it's perfectly fine.

 

[quasar_4]

excellent! I think it is just a bit confusing at first to keep track of which sets are which, and what's being put in union with other things. I am hoping that these proofs get easier as the course goes by... :P