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

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