P_{n} set of all polynomials of degree n

**dwsmith** · June 13th 2011, 05:22 PM

$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.

**Also sprach Zarathustra** · June 13th 2011, 06:38 PM

Originally Posted by dwsmith

$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$ .

**dwsmith** · June 13th 2011, 06:50 PM

Originally Posted by Also sprach Zarathustra

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.

**emakarov** · June 14th 2011, 12:44 AM

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?

Originally Posted by dwsmith

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.

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

LinkBack

Thread Tools

Display

P_{n} set of all polynomials of degree n

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

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

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

Similar Math Help Forum Discussions

Roots of 3rd degree polynomials and Characteristic Polynomials

Polynomials of degree n over Zp

Factoring 3rd degree polynomials

third degree taylor polynomials

Let p and q be polynomials of degree R[x].Define

Search Tags