2.1. Countable Infinity

Examples 2.1.7(b):

The set of all polynomials that have integer coefficients and degree n is countable.
Let P(n) be the set of all polynomials with integer coefficients and degree n. Then a particular element of P(n) is
pn(x) = anxn + an - 1xn - 1 + an - 2xn - 2 + ... + a1x + a0
Define a function f as follows:
domain of f is P(n), range of f is Z x Z x ... x Z (n+1 times)
f(pn) = f( anxn + an - 1xn - 1 + ... a1x + a0) = (an, an - 1, ..., a1, a0)
Because all coefficients are integers, this functions is onto, and is clearly one-to-one. Hence it is a bijection between the domain and the range. But because the finite cross product of countable sets is countable, this implies that P(n) is also countable.
Next | Previous | Glossary | Map