1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proving that the natural numbers are countable, stuck.

  1. Sep 26, 2015 #1
    1. The problem statement, all variables and given/known data

    I'm working through a problem in Abott's Understanding Analysis, second edition, the statement of the problem being:

    "Fix a member n of the natural numbers and let An be the algebraic numbers obtained as roots of polynomials with integer coefficients that have degree n. Using the fact that every polynomial has a finite number of roots, show that An is countable."

    2. Relevant equations
    None given, but possibly helpful are:

    Theorem (given as 1.5.8): The union of a possibly infinite collection of countable sets is countable

    Definition: A set is countable if a bijection exists between the given set and the natural numbers.

    3. The attempt at a solution

    I've been struggling endlessly on this problem but I think I'm getting somewhere. My approach is that I first want to show that each configuration of n coefficients can be represented by an ordered n-tuple, and that each such n-tuple is related bijectively to only one set of roots.

    Then I want to show that the set of coefficient n-tuples is countable, and that's where I'm really stuck, I get the gist of it, that since each coefficient is an integer and therefore a member of a countable set, and there are as many possible coefficient n-tuples as there are n * the cardinality of Z, (which would therefore be countable) but I'm not sure how to make that into a proof. Could I use the theorem that we proved in an example problem in the chapter that for a collection of countable sets, their union is countable?

    Anyway, what I'm hoping that would result in is a bijection between N and the coefficient n-tuples and a bijection between the coefficient n-tuples and the roots of their corresponding polynomials (ie the algebraic numbers) and therefore composition of these two bijections would result in a function relating N to the algebraic numbers.

    Or am I just going about this completely the wrong way?
     
  2. jcsd
  3. Sep 26, 2015 #2

    Krylov

    User Avatar
    Science Advisor
    Education Advisor

    Here are some remarks.

    1. The title of this topic is a bit odd, because clearly the natural numbers are countable, by definition. In your text you discuss a different problem, on which I will focus now.
    2. The theorem you cite as 1.5.8 should be "The union of a countably infinite collection of countable sets is countable."
    3. I think you are making the proof more complicated than necessary. Are you allowed to use that the finite product of countable sets is countable? If so, you can write ##A_n## as a union over the index set ##\mathbb{Z}^{n+1}##. Which sets should appear in this union? Now use Theorem 1.5.8.

    Edit: Incidentally, if you now take the union over ##n \in \mathbb{N}## and use again Theorem 1.5.8, you may conclude that the set of algebraic numbers is countable. Since ##\mathbb{R}## is uncountable, this allows you to infer that there are uncountably many transcendental numbers.
     
    Last edited: Sep 26, 2015
  4. Sep 26, 2015 #3
    My bad, I meant the "algebraic" numbers. How do I change this?

    I actually just looked that up and realized that that was exactly what I was trying to do with my first approach to the problem before I came up with what I'm trying to do now. Thanks!

    Though now for curiosity's sake, I still would like to know whether the relationship between ordered sets of polynomial coefficients and roots is a bijection, because I feel like that might be useful to know.
     
  5. Sep 26, 2015 #4

    Krylov

    User Avatar
    Science Advisor
    Education Advisor

    If I understand you correctly, I don't think this is true without some additional constraints on the ##n##-tuples of coefficients, because if ##(a_0,a_1,\ldots,a_n) \in \mathbb{Z}^{n+1}## with ##a_n \neq 0## is such an ordered ##n##-tuple that gives rise to a polynomial of degree ##n \in \mathbb{N}##, then you can easily construct many more ##n##-tuples that give rise to a polynomial with the same roots. Do you see how? So the map from ##n##-tuples to sets of roots is many-to-one.
     
  6. Sep 26, 2015 #5

    Krylov

    User Avatar
    Science Advisor
    Education Advisor

    In fact, I think that it is easy to come up with such additional constraints when you allow complex roots, but I believe it is not so easy when you restrict yourself to real roots only.
     
  7. Sep 26, 2015 #6

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    If we allow complex roots, a necessary and (I'm pretty sure also )sufficient condition for it to be a bijection would be for the set of polynomials to only include polynomials for which the greatest common factor of their coefficients is 1.

    For real roots that doesn't work because the polynomials ##(x^2+1)(x-1)## and ##(x^2+2)(x-1)## have different coefficients but share the same, unique real root, which is 1.

    So for real roots, the condition is necessary but not sufficient. Something extra is needed.
     
  8. Sep 26, 2015 #7

    Krylov

    User Avatar
    Science Advisor
    Education Advisor

    Yes, when you allow complex roots, I agree. When you restrict yourself to real roots, it's different. Consider ##p(x) = x(x^2 + 1)## and ##q(x) = x(x^2 + 2)##. The greatest common factor of their coefficients equals one. Their only and common real root is zero. Of course this is not essential, but it shows that when OP defines his map from a subset of the ##n##-tuples to the collection of sets of roots, the field matters.
     
  9. Sep 26, 2015 #8

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

  10. Sep 26, 2015 #9
    Complex numbers can be algebraic (according to the Wikipedia, which has an amazingly trippy picture that is supposed to be generated by the algebraic numbers, somehow), and I'm not specifically told the roots must be real.

    OTOH, this might be overcomplicating things like you said. Your suggestion was much better than what I initially was trying to do.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Proving that the natural numbers are countable, stuck.
Loading...