Results 1 to 4 of 4

Math Help - P_{n} set of all polynomials of degree n

  1. #1
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5

    P_{n} set of all polynomials of degree n

    P_n is the set of all polynomials of degree n with integer coefficients.

    Prove that P_n is countable.

    By induction: \forall n\in\mathbb{Z}, \ n\geq 0

    P_0: \ ax^0\Rightarrow a
    Since a is an integer, we can put the integers in a 1-1 correspondence with the naturals numbers. Namely, define f(n)=\begin{cases}2n-1, & n>0\\2n, & n\leq 0\end{cases}

    Assume P(k) is true for a fixed but arbitrary k\geq n, where P(k) is defined as
    a_kx^k+a_{k-1}x^{k-1}+\cdots a_1x^2+a_0x^0

    Prove P(k+1) is true
    P(k+1): \ a_{k+1}x^{k+1}+a_kx^k+a_{k-1}x^{k-1}\cdots a_1x^2+a_0x^0

    I need help in order to proceed.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1

    Re: P_{n} set of all polynomials of degree n

    Quote Originally Posted by dwsmith View Post
    P_n is the set of all polynomials of degree n with integer coefficients.

    Prove that P_n is countable.

    By induction: \forall n\in\mathbb{Z}, \ n\geq 0

    P_0: \ ax^0\Rightarrow a
    Since a is an integer, we can put the integers in a 1-1 correspondence with the naturals numbers. Namely, define f(n)=\begin{cases}2n-1, & n>0\\2n, & n\leq 0\end{cases}

    Assume P(k) is true for a fixed but arbitrary k\geq n, where P(k) is defined as
    a_kx^k+a_{k-1}x^{k-1}+\cdots a_1x^2+a_0x^0

    Prove P(k+1) is true
    P(k+1): \ a_{k+1}x^{k+1}+a_kx^k+a_{k-1}x^{k-1}\cdots a_1x^2+a_0x^0

    I need help in order to proceed.
    Without induction:

    Try to prove that  |P_n|=|\mathbb{Z} \setminus \{0\} \times \mathbb{Z}^n |=\aleph_0 .
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5

    Re: P_{n} set of all polynomials of degree n

    Quote Originally Posted by Also sprach Zarathustra View Post
    Without induction:

    Try to prove that  |P_n|=|\mathbb{Z} \setminus \{0\} \times \mathbb{Z}^n |=\aleph_0 .
    It is supposed to be with induction.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769

    Re: P_{n} set of all polynomials of degree n

    In the induction step, you need to show that the Cartesian product of two countable sets (the set of the new leading coefficients, which is \mathbb{Z}, and the set of polynomials of the previous degree, which is countable by the induction hypothesis) is countable. See this thread. It contains the exact formula for the bijection, but you may not need it.

    Assume P(k) is true for a fixed but arbitrary k\geq n
    What is n here?

    Quote Originally Posted by dwsmith View Post
    Assume P(k) is true for a fixed but arbitrary k\geq n, where P(k) is defined as a_kx^k+a_{k-1}x^{k-1}+\cdots a_1x^2+a_0x^0
    First, this is not a good definition because a_k,\dots,a_0 have not been defined before. Is P(k) a fixed polynomial or a set of polynomials? In either of those cases, P(k) cannot be true or false.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 7
    Last Post: April 7th 2011, 12:38 PM
  2. Polynomials of degree n over Zp
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: February 8th 2011, 08:23 AM
  3. Factoring 3rd degree polynomials
    Posted in the Pre-Calculus Forum
    Replies: 6
    Last Post: December 6th 2010, 12:24 PM
  4. third degree taylor polynomials
    Posted in the Calculus Forum
    Replies: 5
    Last Post: May 1st 2010, 05:19 AM
  5. Let p and q be polynomials of degree R[x].Define
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 20th 2008, 07:12 AM

Search Tags


/mathhelpforum @mathhelpforum