[Math] Show that the set of polynomials with rational coefficients is countable.

Question

Problem: Show that the set of polynomials with rational coefficients is countable.

Idea: We know that the set of rational numbers is denumerable. This implies that the set of rational numbers is countable. We also know that the degree that each polynomial can be is a natural number (I think, and I'm not sure how to word this.) Therefore, I think we can reason through this somehow, by showing that the plane $Q X N$ Is denumerable. I'm just not sure how to do this. Any ideas.

Note: this is for my introduction to proofs class study quide. So, I would prefer not to go to over the top.

Answer 1

Let us begin by stating that the set of rationals is countable, as Z² is countable and every rational number can be expressed as an ordered pair of integers.

Then we can enumerate the polynomials as follows:

1.Start with n=1
2.For every m on [1,n] list the next order-m polynomial
3.Increase n by 1 and return to step 2.

For a proper enumeration of each order of polynomials (which must exist as, Q being countable, Qⁿ is countable for all finite n and every order-n rational-coefficient polynomial can be expressed as an ordered n-tuple), every polynomial of rational coefficients will eventually appear exactly once.