Re: A question on countability proof
- From: magidin@xxxxxxxxxxxxxxxxx (Arturo Magidin)
- Date: Thu, 12 Oct 2006 22:48:14 +0000 (UTC)
In article <7ozXg.892$zf3.536@fed1read03>, vsgdp <spam@xxxxxxxx> wrote:
Show the set of all polynomials with integer coefficients is countable and
deduce that the set of algebraic numbers is also countable.
For the first part, I defined the map T to map a polynomial with integer
coefficients to its coordinate vector representation using the standard
polynomial basis. So T( a0 + a1 x + ... + an x^n ) --> (a0, a1, ..., an) in
Z^(n+1). To is one to one since T(p) = T(q) == > p = q. Since Z x Z
countable, so is Z^(n+1).
This proves that the set of all polynomials of degree at most n and
integer coefficients in countable.
Am I done? Or do I need to take n-->infinity? In which case I could quote
the theorem that a countable union of countable sets is countable?
Yes, you need to consider the union of all of these, and the theorem
you mention (which requires the Axiom of Choice) would imply that the
union is at most countable, giving the result.
Also, for the second part, do I just observe that any polynomial with
integer coefficients has finite solutions. And since the set of all such
polynomials is countable, the set of algebraic numbers is countable?
You have a countable union of finite sets (the finite sets are the
roots of the polynomials, indexed by the polynomials itself). If you
know that this is countable (e.g., the theorem above) you are done.
(You don't actually need the Axiom of Choice, to prove this, however;
you can come up with a more explicit counting, but you may not be
required to do so)
--
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes" by Bill Watterson)
======================================================================
Arturo Magidin
magidin-at-member-ams-org
.
- References:
- A question on countability proof
- From: vsgdp
- A question on countability proof
- Prev by Date: Re: Z(R)-Module
- Next by Date: Re: Linear Algebra
- Previous by thread: A question on countability proof
- Next by thread: another countable question,
- Index(es):
Relevant Pages
|
