Tricki
a repository of mathematical know-how

A quick way of recognising countable sets

Quick description

A set  A is countable if there is a way of giving a finite description to every element of  A.

Prerequisites

The definition of a countable set, the content of this article.

See also

A good way of proving that a set is countable

General discussion

It is not hard to prove that the set of all finite strings of symbols taken from a fixed finite alphabet is countable. Indeed, we can count in turn the strings of length 0, 1, 2, and so on. If the size of the alphabet is k then for each n there are k^n strings of length n, and in particular finitely many. Therefore, by the simple lemma discussed in this article, we are done (either by saying that we have expressed the set of all finite strings as a countable union of finite sets or by considering the function that takes each string to its length).

It follows from this that if A is any set, and if we can come up with a procedure for giving a finite description (in, say, the English language augmented by a few convenient mathematical symbols) to each of the elements of A, then A is countable. After all, the description takes the form of a finite string of symbols taken from some fixed "alphabet" of symbols, and there are only countably many of those.

This is significant because it often gives an easy way of recognising that a set is countable. It also gives proofs of countability, though these proofs are usually slightly "silly" and better replaced by simpler ones. But if you have ever known instinctively that a set is countable before you have actually come up with a proof, then it may well be something like this principle that is in the back of your mind.

Example 1

The rationals are countable because every rational has a description such as -35792/1293879861. Here, the alphabet is \{0,1,2,3,4,5,6,7,8,9,-,/\}.

Example 2

The set of all polynomials with integer coefficients is countable since (a very slight modification of) the normal way of writing down such a polynomial is a finite string of symbols taken from the alphabet \{0,1,2,3,4,5,6,7,8,9,+,-,x,\wedge\}. Here, the symbol \wedge is used instead of the normal notation for exponentiation, so for instance instead of writing x^3-3x+1 we would write x\wedge 3-3 x+1.

Example 3

The set of all algebraic numbers is countable, since each one is a root of a polynomial that can be described as above, and for any fixed polynomial we can specify which root we are talking about in terms of the ordering on \mathbb{R}. For example, we could describe (1+\sqrt{5})/2 as "the second root of x \wedge 2-x-1". If we allow complex numbers then we could choose an ordering of the roots by taking them in order of their modulus, and for roots of equal modulus we could order them by their arguments (defined to lie in the interval [0,2\pi)). For example, -i could be defined as "the second root of the polynomial x\wedge 2+1".

Alternatively, and more naturally, we could argue that since the set of polynomials with integer coefficients is countable and each such polynomial has finitely many roots, an easy deduction from the article A good way of proving that a set is countable shows that the algebraic numbers are countable.

Example 4

The set of all non-increasing functions from \mathbb{N} to \mathbb{N} is countable. This time the fact that there is a finite description relies on the well-ordering principle for the natural numbers, which implies that every non-increasing function from \mathbb{N} to \mathbb{N} is constant from some point on. So every such function will have a description such as "f(1)=23, f(2)=12, f(3)=f(4)=5 and f(n)=3 for every n\geq 5."

Example 5

The set of all finite subsets of \mathbb{N} is countable, since each one can be finitely described by simply writing it in the usual way using the symbols, \{, \}, the integers from 0 to 9, and commas.