Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof of Polynomial Countability

  1. Feb 9, 2012 #1
    1. The problem statement, all variables and given/known data
    Let P(n) be the set of all polynomial of degree n with integer coefficients. Prove that P(n) is countable, then show that all polynomials with integer coefficients is a countable set.

    2. The attempt at a solution
    For this problem the book gives me a hint that using induction is one way to prove this. So by going off this I say that P(0) is countable since it is the set of all constants. After this I say that P(1) is countable since P(1) = ax + P(0) in which a ε A and A = {z: z ε Z, z ≠ 0}. Now my problem is that I do not know how to make the jump from P(1) to P(n) and then to P(n+1). For the second part of the question I know that all polynomials with integer coefficients are countable since if we were to take a union of all the sets they would be countable since the union of countable sets are countable.
  2. jcsd
  3. Feb 9, 2012 #2


    User Avatar
    Science Advisor
    Homework Helper

    Hi, welcome to PF.

    Looks like you already got all the components in place for a proof by induction.
    Suppose that you have proven that P(n) is countable... can you write P(n + 1) in terms of P(n)?
  4. Feb 9, 2012 #3


    User Avatar
    Science Advisor

    hint: which terms are in P(n+1) that AREN'T in P(n)?

    can you think of a way to write p(x) in P(n+1) as:

    "something" + q(x), where q(x) is in P(n)?

    maybe the "somethings" might be countable....
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook