The reasoning behind the following result is also sometimes known as the diagonal argument.

Proposition:

Let (X, d) be a complete metric space without isolated points (i.e. every ball contains a point other then the one it is centred on). Then X is uncountable.

Proof:

Suppose otherwise. X must be infinite, since otherwise every point would necessarily be isolated. Therefore there is a bijection f : x → N.

We now construct a sequence x0, x1, ... of points in X and a sequence r0, r1, ... of positive real numbers. Let x0 = f -1(0) and r0 = 1.

Given xk, rk the set B = {x ∈ X : d(x, xk) ≤ rk} \ {xk} is non-empty. Let xk+1 be the point in B which minimises f. Let rk+1 = min {rk/2, d(xk, xk+1)}.

The sequence xn is a Cauchy sequence, so since X is complete it converges to some limit x ∈ X. Inductively f(xk) ≥ k for all k. Hence x ≠ f -1(k) for any k, since xn lies in a closed ball not containing f -1(k) for n > k. This contradicts the bijectiveness of f.

Hence X is uncountable.


The reason why this is called the diagonal argument is that it is essentially an abstraction and generalisation of the proof for the uncountability of the reals given in the write-up above. We obtain a sequence by successively poking a point to ensure that it is distinct from each point of a given list, and then invoke completeness (this is implicit when we use decimal expansions) to show that the sequnce converges to a point not in the list.