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

Homework Help: 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

    CompuChip

    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

    Deveno

    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