Question

(a) For each n∈N, prove that the collection of all polynomials in x of degree less than or equal to n with rational coefficients is countable. Explain your answer in detail. (b) Prove that the set of all polynomials in x with rational coefficients is countable.

Answer 1

To prove that the collection of all polynomials in x of degree less than or equal to n with rational coefficients is countable, we can use the concept of bijection and establish a mapping between the set of polynomials and the set of n-tuples of rational numbers.

Step-by-step explanation:

To prove that the collection of all polynomials in x of degree less than or equal to n with rational coefficients is countable, we can use the concept of bijection. Let's define the set of all polynomials in x of degree less than or equal to n with rational coefficients as Pn.

Now, let's consider the set Q^n, which is the set of all n-tuples of rational numbers. We can establish a bijection between Pn and Q^n by mapping each polynomial in Pn to its corresponding coefficients in Q^n.

Since Q^n is countable (proved using the Cantor pairing function), and we have established a bijection between Pn and Q^n, we can conclude that Pn is countable as well.