How to tell if a set is countable just by looking at it

The concept of countable infinity is an elusive topic that confuses most people when they encounter it for the first time.

Normally, if you are learning about countable sets, you have just finished learning a bunch of technical definitions and facts about functions, and you might have only just learnt what the words injection, surjection and bijection mean.

The concept of countability then requires you to piece all of these concepts together, learn even more technical results about countable sets, and at the same time try to make sense of the idea that some sizes of infinity are larger than others.

With all this going on, it can be difficult to figure out where to start when you are trying to decide if a set is countably infinite or not.

I would like to convince you that it is easy to tell when a set is countable just by looking at it—all you have to know is the following heuristic:

A set is countable if each of its elements has a finite description.

What follows are some examples of how this heuristic can be used to determine if a set is countable, some examples of what goes wrong when you encounter an uncountable set, and finally, a precise mathematical statement of the heuristic and a sketch of the proof.

Examples of countable sets

To see this heuristic in action, let’s first look at some very familiar examples of countable sets.

The set $\mathbb{N}$ of natural numbers is countable because every natural number can be expressed as a finite string of digits, for example:
$$7, \quad 18, \quad 13542, \quad 7000001, \quad \dots$$

The set $\mathbb{Z}$ of integers is countable because every integer can be expressed as a finite string of digits, possibly modified by a $-$ sign, for example:
$$-29, \quad 18, \quad 13542, \quad -7000001, \quad \dots$$

The set $\mathbb{Q}$ of rational numbers is countable because every rational number can be expressed as two finite strings of digits (perhaps modified by a $-$ sign) separated by a symbol representing division, for example:
$$\frac{18}{27}, \quad -\frac{2}{109}, \quad \frac{8}{1}, \quad \dots$$

The set $\mathbb{Z} \times \mathbb{Z}$ of pairs of integers is countable because every pair of integers can be described by specifying two integers, each of which has a finite description, for example:
$$(-29,1), \quad (13,100), \quad (0,0), \quad \dots$$

It was fairly easy to see that these sets were countable, and in fact it is very possible to cook up (more-or-less) explicit bijections between $\mathbb{N}$ and each of the above sets. To see where the power of the heuristic comes into play, let’s have a look at a couple of more complicated examples.

Let $\mathcal{P}_{\mathsf{fin}}(\mathbb{N})$ be the set of all finite subsets of $\mathbb{N}$. Every finite subset of $\mathbb{N}$ can be expressed in list notation, for example: $$\{ 1, 75, 300, 412, 2018, 21128 \}$$ Since every finite subset of $\mathbb{N}$ has a finite description, the set $\mathcal{P}_{\mathsf{fin}}(\mathbb{N})$ is countable.

The set $\mathbb{A}$ of all algebraic numbers is defined to be the set of complex numbers which are roots of polynomials with rational coefficients. An element $\theta \in \mathbb{A}$ can be described by specifying the rational coefficients $a_0, a_1, \dots, a_n$ of a polynomial $$p(x) = a_0 + a_1 x + + \cdots + a_n x^n$$ for which $p(\theta)=0$ and then specifying a natural number $k$ such that $\theta$ is the $k^{\text{th}}$ root of $p(x)$ when listed in a particular order (e.g. in increasing order by modulus and then by argument). Since $\theta$ is described by the finite list $(a_0,a_1,\dots,a_n,k)$, and since the rational numbers $a_0, \dots, a_n$ and the natural number $k$ each have finite descriptions, it follows that $\mathbb{A}$ is countable.

Uncountable sets

Now that we’ve seen some examples of countable sets where the heuristic is successful, let’s see some examples of uncountable sets and discuss why the heuristic doesn’t apply to them.

The set $\mathbb{R}$ of real numbers is uncountable. Heuristically, this is because there is no way of describing each real number in a finite way. For example, we could describe a real number by specifying its decimal expansion, for example:
$$\pi = 3.14159265358979\dots$$
but decimal expansions are infinite, so this doesn’t work. We could describe a real number by specifying a Dedekind cut, but Dedekind cuts are infinite subsets of $\mathbb{Q}$, so this description isn’t finite. We could describe a real number $\alpha$ by specifying a sequence of rational numbers $(a_0,a_1,a_2,\dots)$ such that $(a_n) \to \alpha$ as $n \to \infty$, but again this is not a finite description since there are infinitely many terms in the sequence $(a_n)$.

The set $\mathcal{P}(\mathbb{N})$ of all subsets of $\mathbb{N}$ is uncountable. The ‘list the elements’ method that we used above to demonstrate that $\mathcal{P}_{\mathsf{fin}}(\mathbb{N})$ is countable doesn’t work here, since it is impossible to describe an infinite subset of $\mathbb{N}$ in a finite way by listing all of its elements.

Countable sets in disguise

The reason I am using the word heuristic rather than principle is that there are some sets which appear to be uncountably infinite, since their elements have infinite descriptions, but which are actually countably infinite. The reason for this dissonance is that their elements can be described in a finite way—it’s just that you wouldn’t necessarily think of the finite descriptions.

For example, the set $\mathcal{P}_{\mathsf{cof}}(\mathbb{N})$ of cofinite subsets of $\mathbb{N}$ consists of all subsets $U \subseteq \mathbb{N}$ which contain all but finitely many natural numbers. This set appears to be uncountable, since it is impossible to assemble the elements of a cofinite subset of $\mathbb{N}$ into a finite list. However, an element of $\mathcal{P}_{\mathsf{cof}}(\mathbb{N})$ can be described in a finite way by listing all of the natural numbers that are not elements of $U$.

This demonstrates that our heuristic is only good for determining that a countable set is countable—trying and failing several times to find finite descriptions of the elements of a set does not prove that the set is uncountable; it might just be that you haven’t found the right way of finitely describing its elements yet!

Why the heuristic works

Now that we’ve seen countable sets whose elements have finite descriptions, let’s prove that our heuristic is a valid way of establishing the countability of a set.

A finite description of the elements of a set $X$ is really just a finite string of symbols. These symbols can be pretty much anything you like: digits, arithmetic operators, commas, curly brackets, or even words of the English language (or emojis, if you’re that way inclined).

Importantly, though, the set $\Sigma$ of symbols that we may use in our finite descriptions must itself be countable (and possibly finite). Indeed, if $\Sigma$ is uncountable, then each symbol $\sigma$ in $\Sigma$ itself can be described in a finite way as a finite string of symbols from $\Sigma$: all you have to do is write “$\sigma$”!

To say that each $x \in X$ has a finite description using the symbols from $\Sigma$ is to say that there is a function $\mathsf{Desc} : X \to \Sigma^*$, where $\Sigma^*$ is the set of all finite strings (= finite sequences) from $\Sigma$. Thus for each $x \in X$, the value $\mathsf{Desc}(x)$ is the finite string of symbols from $\Sigma$ that describes the element $x$.

We can’t just take $\mathsf{Desc}$ to be any function. If two elements $x,y \in X$ have the same descriptions, then they should be equal—this is to say that $\mathsf{Desc}(x) =\mathsf{Desc}(y)$ implies $x=y$. In other words, $\mathsf{Desc}$ must be injective.

So now we have made precise what it means for the elements of a set $X$ to have finite descriptions: it means that for some countable set $\Sigma$ of symbols, there is an injective function $\mathsf{Desc} : X \to \Sigma^*$, where $\Sigma^*$ is the set of all finite strings of elements of $\Sigma$.

The heuristic that says that a set is countable if each of its elements has a finite description can now be stated precisely as the following theorem.

Theorem
Let $X$ be a set. If there exists a countable set $\Sigma$ and an injective function $X \to \Sigma^*$, then $X$ is countable.

Sketch of proof
The proof of this theorem is an exercise in piecing together lemmas about countable sets.

The set $\Sigma$ is countable by assumption.

For each $n \in \mathbb{N}$, the set $\Sigma^n$ of sequences of elements of $\Sigma$ of length $n$ is the $n$-fold cartesian product of $\Sigma$—that this is countable follows by a straightforward induction argument from the fact that the cartesian product of any two countable sets is countable.

The set $\Sigma^*$ is then simply the union $\bigcup_{n \in \mathbb{N}} \Sigma^n$, which is countable since it is a union of countably many countable sets.

The fact that $X$ is countable now follows from the fact that $\Sigma^*$ is countable and there is an injection $X \to \Sigma^*$. $\quad \Box$

And there you have it! Now you’re equipped to prove any set is countable (provided that it actually is countable).

Author: Clive

I'm a mathematics lecturer at Northwestern University. My research focus is category theory and mathematical logic. I got my PhD from Carnegie Mellon University in 2018.

4 thoughts on “How to tell if a set is countable just by looking at it”

  1. I like this a lot. It feels intuitively obvious that a finite description allows a finite number of permutations, and hence finitely many possible elements, but it’s nice to see it spelt out and formalised.
    Clearly the elements don’t all need to have the same method of finite description either—we can partition the set according to which description is used.
    That leads to another question though: for what I’ve just said to work, does the number of description formats need to be finite? My feeling is that it does, but I’ve not tried to prove it yet.

  2. A counterexample which tells me that the answer to the question in my previous comment is no: consider a set where for all n>0, there are n elements whose description requires a set of n symbols. There are infinitely many description formats, but the set is countable.

    1. Thanks for your comments. You’re right—there don’t have to be finitely many ‘description formats’, but there do have to be countably many. This boils down to defining injections $X_i \to \Sigma_i^*$ for some family $\{ X_i \mid i \in I \}$ of subsets of $X$ and some family $\{ \Sigma_i \mid i \in I \}$ of ‘alphabets’. But then this defines an injection $X = \bigcup_{i \in I} X_i \to \bigcup_{i \in I} \Sigma_i^{\star} \subseteq \left( \bigcup_{i \in I} \Sigma_i \right)^*$, so as long as $\bigcup_{i \in I} \Sigma_i$ is countable, then $X$ is countable. Or to put it slightly more concretely, if you have countably many ‘description formats’, then $X$ will be countable.

      1. (I’m not sure how to insert TeX commands here, so I’ll stick to plain text. Please edit them in if you want!)

        I’m fairly new to set theory and I think my book (Kolmogorov, /Introductory Real Analysis/) uses old terminology, but I followed that as ultimately making X a countable union of countable subsets, one for each “description format”.

        As described in my counterexample, it occurs to me that the description formats themselves might have a finite description (eg I could define the nth format as “an n-tuple of real numbers”), and then *that* becomes the finite description of the set elements.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.