What Is a Countable Set?

A random variable is discrete if the set of values it might take, $S$, is countable.

Roughly, a set being countable means that we can arrange all of its elements into a list. If the set is infinite, this looks like

$$a_1,a_2,a_3,\dots$$

Each element of the set must occupy a fixed position in the list, with no repetitions and nothing left out.

Examples of countable sets include

$$\mathbb{N},\qquad\mathbb{Z},\qquad\mathbb{Q}.$$

More formally, a set $S$ is countable if it is either finite or countably infinite.

A countably infinite set is one for which there is a bijection between $S$ and the natural numbers $\mathbb{N}$. In terms of our list, each natural number gives a “position number”, and corresponds to exactly one element of $S$.

For example, although the integers stretch infinitely far in both directions, we can still list all of them:

$$0,1,-1,2,-2,3,-3,\dots$$

So $\mathbb{Z}$ is countably infinite.

Not Every Infinite Set Is Countable

Some infinite sets cannot be listed in this way.

A famous example is the interval

$$[0,1].$$

Georg Cantor was among the first to distinguish systematically between different kinds of infinite sets. His celebrated diagonal argument shows that there are simply too many real numbers in the interval $[0,1]$ to arrange into a list.

We present this particularly striking argument below.

Cantor’s Diagonal Argument

Suppose, for the sake of argument, that we can list every real number in $[0,1]$.

The beginning of our list might look something like this:

$$0.14414331\dots$$

$$0.12313452\dots$$

$$0.51543141\dots$$

$$0.66161244\dots$$

$$0.63141514\dots$$

Now look at the first digit of the first number, the second digit of the second number, the third digit of the third number, and so on:

$$0.\textcolor{red}{1}4414331\dots$$

$$0.1\textcolor{red}{2}313452\dots$$

$$0.51\textcolor{red}{5}43141\dots$$

$$0.661\textcolor{red}{6}1244\dots$$

$$0.6314\textcolor{red}{1}514\dots$$

We now construct a new number by deliberately making it different from every number on the list.

Let the $n^{th}$ digit of our new number be $5$, unless the $n^{th}$ digit of the $n^{th}$ number on the list is itself $5$. In that case, make the new digit $6$.

For the list above, this gives

$$x=0.55655\dots$$

Now consider any number on our original list.

The new number differs from the first number in its first decimal place.

It differs from the second number in its second decimal place.

It differs from the third number in its third decimal place.

And so on.

More generally, for every $n$, our new number differs from the $n^{th}$ number on the list in its $n^{th}$ decimal place.

So $x$ cannot be equal to any number on the list.

But the same construction could be carried out for any proposed list of all the numbers in $[0,1]$.

Therefore, no such list can contain them all.

The interval $[0,1]$ is uncountable.

It follows that, if

$$X\sim\mathcal{U}[0,1],$$

then it is not a discrete random variable.

A Couple of Technicalities

There is one small technical detail in Cantor’s argument. Some numbers have two decimal expansions: for example,

$$0.043=0.042999\dots$$

To avoid this ambiguity, we can simply agree always to use the decimal expansion which does not end in recurring $9$s.

Finally, making the idea of the “values $X$ might take” completely precise requires measure theory. For our purposes here, countability captures the distinction we need.

Background:

• Discrete Random Variables