Re: The Algebraic Set

On Sun, 31 Jul 2005, Narcoleptic Insomniac wrote:
> On Jul 31, 2005 4:00 AM, William Elliot wrote:
> > > >
> > > > > A number z is said to be algebraic if there are
> > > > > integers c_0,c_1,...,c_n, not all zero, such that
> > > > > c_0 z^n + c_1 z^(n-1) +...+ c_(n-1) z + c_n = 0.
> > > > >
> > > > > Given that any n'th degree polynomial has n
> > > > > (not necessarily distinct) roots, prove that the
> > > > > set of algebraic numbers is countably infinite.
> > > >
> > > > For all n in N, P_n = { p in Z[x] | deg p = n } is countable. \/_n
> > > > P_n is countable, ie there's only countably many polynomials.
> > > >
> > > > Now each polynomial has a finite number of roots but let's
> > > > increase this to each polynomials has countably many roots. Thus
> > > > over all an upper bound for the number of roots is countable times
> > > > countable = countable.
> > >
> > > Yes, I definitely should have said something about
> > > the cardinality of A_n (or similarly P_n).
> > >
> > > > > PROOF. Let A_n be the set of all distinct roots of all the n'th
> > > > > degree polynomials with integral coefficients. Then clearly
> > > > > {\/A_n : n = positive integers} is the set of algebraic numbers.
> > > >
> > > > No, \/{ A_n : n is positive integer }
> > >
> > > > You don't need to count distinct roots, only get an upper bound
> > > > for the number of roots that's not too large.
> > >
> > > This is why you chose P_n instead of A_n correct, since the A_n I
> > > used follows directly and naturally from P_n?
> > >
> > No, A_n is more complex than P_n. However |A_n| <= |P_n| , and that's
> > all that's needed. I chose P_n, as it's easier to 'count' and
> > provides for a sufficiently 'small' upper bound.
>
> Maybe I misunderstood something, why is the cardinality of A_n less than
> or equal to P_n?
>
Whoops, that was slick. Each polynomial in P_n has n or fewer distinct
roots. Thus |A_n| <= n |P_n| = |P_n|.

> If P_n is the set of n'th degree polynomials (with integral
> coefficients) and A_n is the set of roots of all n'th degree
> polynomials, wouldn't the cardinality of A_n be larger than or equal to
> the cardinality of P_n?
>
No, finite * (infinitely) countable = countable

> I mean, for each element of P_n (each polynomial of degree n) there are
> between 1 and n elements of A_n associated with that element of P_n.
> Granted both P_n and A_n become countably infinite as n --> oo, but to
> each element of P_n there is one or more elements of A_n. If not, I
> think I must have misunderstood the definition of P_n.
>
So what?
Let (k,i) be n infinite sequences
(1,1), (1,2), (1,3) ...
(2,1), (2,2), (2,3) ...
....
(n,1), (n,2), (n,3) ...

Map (k,i) to nk + i.
That map is a bijection from all those n sequences onto
the integers starting from n + 1.
Thus finite * countable = countable

> > We actually need to finish up with the observation
> > countable <= #distinct roots <= |Z[x]| <= countable
> > to conclude #distinct roots = #algebraics = countable.
> >
> > Thus the easy and necessary task of showing finite /=
> > #distinct roots, ie countable <= #distinct roots.
>
.

Relevant Pages

  • Re: A "How would you do this"-type of question. not Java-specific.
    ... a dot will appear on the map to indicate where that ZIP code ... coords and extrapolate those to x,y coords on your graphic map? ... arbitrary encoding -- some large-scale patterns are evident ... evaluating such high-degree polynomials with useful accuracy! ...
    (comp.lang.java.help)
  • Re: Fields and transcendentals
    ... homomorphism fails to be an isomorphism it's because t is ... since Kis formed by the inclusion of all polynomials in t, ... there be some elements of Kthat map to 0. ... and find a polynomial having t as a root. ...
    (sci.math)
  • Re: Question about "polynomial evaluations"
    ... polynomial functions as opposed to polynomials. ... the map eval cannot be one-to-one. ... you mean "the polynomials that map to the zero ... Fconsists exactly of all multiples of some particular ...
    (sci.math)
  • Re: A "How would you do this"-type of question. not Java-specific.
    ... Eric Sosman wrote: ... a dot will appear on the map to indicate where that ZIP code ... evaluating such high-degree polynomials with useful accuracy! ...
    (comp.lang.java.help)
  • Re: A question on countability proof
    ... I defined the map T to map a polynomial with integer ... coefficients to its coordinate vector representation using the standard ... polynomials is countable, the set of algebraic numbers is countable? ... You have a countable union of finite sets (the finite sets are the ...
    (sci.math)