# P_{n} set of all polynomials of degree n

• Jun 13th 2011, 05:22 PM
dwsmith
P_{n} set of all polynomials of degree n
$\displaystyle P_n$ is the set of all polynomials of degree n with integer coefficients.

Prove that $\displaystyle P_n$ is countable.

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

$\displaystyle 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 $\displaystyle f(n)=\begin{cases}2n-1, & n>0\\2n, & n\leq 0\end{cases}$

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

Prove P(k+1) is true
$\displaystyle 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.
• Jun 13th 2011, 06:38 PM
Also sprach Zarathustra
Re: P_{n} set of all polynomials of degree n
Quote:

Originally Posted by dwsmith
$\displaystyle P_n$ is the set of all polynomials of degree n with integer coefficients.

Prove that $\displaystyle P_n$ is countable.

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

$\displaystyle 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 $\displaystyle f(n)=\begin{cases}2n-1, & n>0\\2n, & n\leq 0\end{cases}$

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

Prove P(k+1) is true
$\displaystyle 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 $\displaystyle |P_n|=|\mathbb{Z} \setminus \{0\} \times \mathbb{Z}^n |=\aleph_0$ .
• Jun 13th 2011, 06:50 PM
dwsmith
Re: P_{n} set of all polynomials of degree n
Quote:

Originally Posted by Also sprach Zarathustra
Without induction:

Try to prove that $\displaystyle |P_n|=|\mathbb{Z} \setminus \{0\} \times \mathbb{Z}^n |=\aleph_0$ .

It is supposed to be with induction.
• Jun 14th 2011, 12:44 AM
emakarov
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 $\displaystyle \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.

Quote:

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

Quote:

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

First, this is not a good definition because $\displaystyle 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.