P_{n} set of all polynomials of degree n

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

Prove that is countable.

By induction:

Since a is an integer, we can put the integers in a 1-1 correspondence with the naturals numbers. Namely, define

Assume P(k) is true for a fixed but arbitrary , where P(k) is defined as

Prove P(k+1) is true

I need help in order to proceed.

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

Quote:

Originally Posted by

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

Prove that

is countable.

By induction:

Since a is an integer, we can put the integers in a 1-1 correspondence with the naturals numbers. Namely, define

Assume P(k) is true for a fixed but arbitrary

, where P(k) is defined as

Prove P(k+1) is true

I need help in order to proceed.

Without induction:

Try to prove that .

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

Quote:

Originally Posted by

**Also sprach Zarathustra** Without induction:

Try to prove that

.

It is supposed to be with induction.

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 , 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

What is n here?

Quote:

Originally Posted by

**dwsmith** Assume P(k) is true for a fixed but arbitrary

, where P(k) is defined as

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