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).

An international mathematical keyboard layout

Most mathematicians typeset their equations using LaTeX—even this website uses MathJax to allow me to use LaTeX commands to type things like the following formula without needing to type any special characters.

$$\forall \varepsilon > 0, ~ \exists \delta>0, ~ \forall x, ~ |x-a| < \delta \Rightarrow |f(x)-f(a)| < \varepsilon$$

However, this isn’t always possible, as anyone who has tried to communicate mathematics in an email will know. Instead, we must resort to some combination of the following:

  • Spell everything out in words (“for all epsilon > 0, there exists delta > 0, such that for all x, if |x-a| < delta then |f(x)-f(a)| < epsilon”);
  • Substitute a standard character for the special characters (“A e > 0, E d > 0, A x, |x-a| < d => |f(x)-f(a)| < e”);
  • Type out the LaTeX code and hope the reader understands LaTeX commands (“\forall \varepsilon > 0, \exists \delta>0, \forall x, |x-a| < \delta \Rightarrow |f(x)-f(a)| < \varepsilon”);
  • Use a character map or search engine to find, copy and paste each new symbol individually.

Frustrated by this, I decided to make my own keyboard layout containing most of the mathematical symbols I use on a day-to-day basis. Lo and behold, I am now able to type the above formula with no stress!

∀ε > 0, ∃δ > 0, ∀x, |x-a| < δ ⇒ |f(x)-f(a)| < ε

The layout

This keyboard layout modifies the standard US keyboard layout to add symbols accessible by pressing the [Alt R] key. It looks like this:

Each white square represents a key, and the four symbols are obtained by either pressing the key on its own (lower-left), pressing the key together with [Shift] (upper-left), pressing the key together with [Alt R] (lower-right) or pressing the key together with both [Shift] and [Alt R] (upper-right). For example:

  • Pressing [Alt R]+[C] types the symbol ∈ (element of)
  • Pressing [Shift]+[Alt R]+[C] types the symbol ∉ (not an element of)

The ten symbols in red represent dead keys, which gives a way of typing the same diacritic over different letters without necessitating different keys for each letter. In this case, you press the key combination for the desired diacritic, then release all keys and press the key for the desired letter. For example:

  • Pressing [Alt R]+[,] followed by [Shift]+[C] types the letter Ç (upper-case C with cedilla)
  • Pressing [Shift]+[Alt R]+[\] followed by [S] types the letter š (lower-case S with caron)
  • Pressing [Alt R]+[] followed by [Alt R]+[A] types the letter ǽ (lower-case AE ligature with acute accent)

The rationale

Some thought went into designing the keyboard layout, particularly which symbols should be included or excluded, where the symbols should be placed, and so on. Hopefully my reasoning behind most of the decisions I made is self-explanatory, but I feel that a few things deserve some justification.

First, there are some commonly used mathematical symbols that cannot be typed using this layout, most conspicuously ≤ (less than or equal to) and ≥ (greater than or equal to). I decided to prioritise other symbols because it is a well enough understood compromise to write <= and >= instead.

Second, I chose to prioritise diacritics over more mathematical symbols: mathematics is a very international subject and simply typing authors’ names can be challenging sometimes. Unfortunately I wasn’t able to cover all the bases, so a few letters remain untypable, including the Czech letter Ů (U with ring above) and the Polish letter Ł (L with bar).

Third, there is a certain bias towards symbols used in mathematical logic, which is why you see ⊢ (right tack) and ⊣ (left tack), for example. This is because, despite making the layout public, I made the keyboard layout for my own use.

Fourth (and finally), I made no changes to the standard US keyboard layout other than to add keys accessible with [Alt R]. This was to provide minimal disruption to the standard layout.

Installing the layout

The following instructions should work on most flavours of Linux, though I should admit that I use Linux Mint (with Cinnamon) and have not tried it on any other distributions. I have not yet made a version for Windows or Mac—that will have to wait for now, or if anyone reading this would like to volunteer to port it, I’d be glad to update this post to reflect your efforts.

Step 1. Download this file and move it to the directory /usr/lib/X11/xkb/symbols — make sure that the filename is mdc and not mdc.txt or anything else.

Step 2. Open /usr/share/X11/xkb/rules/evdev.xml and insert the following code immediately after the line containing the tag.

<layout>
  <configItem>
    <name>mdc</name>
    <shortDescription>mdc</shortDescription>
    <description>Math Dot Coffee</description>
    <languageList>
      <iso639Id>eng</iso639Id>
    </languageList>
    <variantList/>
  </configItem>
</layout>

Step 3. Download this image and move it to the directory /usr/share/iso-flag-png/ — make sure that the filename is mdc.png

Step 4. Navigate to the keyboard layout settings; the ‘language’ of the new layout will be listed as Math Dot Coffee. If it isn’t there, you might need to log out and log in again, or even restart your computer, before it will appear.

List of symbols

What follows is a comprehensive list of symbols together with their official Unicode names.

Each key is listed on its own row as it appears on the keyboard, with rows ordered from top to bottom and keys within each row ordered from left to right. This is done according to the keyboard set up as above—in particular, the [\] key is to the right of the []] key, and not to the left of the [Z] key or anywhere else.

For each key [Key], the symbols are listed in the following order: first [Key], then [Shift]+[Key], then [Alt R]+[Key], and finally [Shift]+[Alt R]+[Key].

Row 1:

  • ` (grave accent); ~ (tilde); (right tack); (left tack).
  • 1 (digit one); ! (exclamation mark); ¹ (superscript one); ¡ (inverted exclamation mark).
  • 2 (digit two); @ (commercial at); ² (superscript two); ½ (vulgar fraction one half).
  • 3 (digit three); # (number sign); ³ (superscript three); £ (pound sign).
  • 4 (digit four); $ (dollar sign); (superscript four); (euro sign).
  • 5 (digit five); % (percent sign); (superscript five); · (middle dot).
  • 6 (digit six); ^ (circumflex accent); (superscript six); (square root).
  • 7 (digit seven); & (ampersand); (superscript seven); § (section sign).
  • 8 (digit eight); * (asterisk); (superscript eight); (infinity).
  • 9 (digit nine); ( (left parenthesis); (superscript nine);  (superscript minus).
  • 0 (digit zero); ) (right parenthesis); (superscript zero); ° (degree sign).
  • (hyphen-minus); _ (low line); (en dash); (em dash).
  • = (equals sign); + (plus sign); × (multiplication sign); ÷ (division sign).

Row 2:

  • q (Latin small letter Q); Q (Latin capital letter Q); (for all); (there exists).
  • w (Latin small letter W); W (Latin capital letter W); ω (Greek small letter Omega); Ω (Greek capital letter Omega).
  • e (Latin small letter E); E (Latin capital letter E); (identical to); (almost equal to).
  • r (Latin small letter R); R (Latin capital letter R); ρ (Greek small letter Rho); ε (Greek small letter Epsilon).
  • t (Latin small letter T); T (Latin capital letter T); þ (Latin small letter Thorn); Þ (Latin capital letter Thorn).
  • y (Latin small letter Y); Y (Latin capital letter Y); (leftwards arrow); (leftwards double arrow).
  • u (Latin small letter U); U (Latin capital letter U); (left right arrow); (left right double arrow).
  • i (Latin small letter I); I (Latin capital letter I); (rightwards arrow); (rightwards double arrow).
  • o (Latin small letter O); O (Latin capital letter O); œ (Latin small ligature OE); Œ (Latin capital ligature OE).
  • p (Latin small letter P); P (Latin capital letter P); π (Greek small letter Pi); Π (Greek capital letter Pi).
  • [ (left square bracket); { (left curly bracket); (mathematical left angle bracket); « (left-pointing double angle quotation mark).
  • ] (right square bracket); } (right curly bracket); (mathematical right angle bracket); » (right-pointing double angle quotation mark).
  • \ (reverse solidus); | (vertical line); ê (circumflex accent dead key); ě (caron dead key).

Row 3:

  • a (Latin small letter A); A (Latin capital letter A); æ (Latin small letter AE); Æ (Latin capital letter AE).
  • s (Latin small letter S); S (Latin capital letter S); σ (Greek small letter Sigma); Σ (Greek capital letter Sigma).
  • d (Latin small letter D); D (Latin capital letter D); ð (Latin small letter Eth); Ð (Latin capital letter Eth).
  • f (Latin small letter F); F (Latin capital letter F); δ (Greek small letter Delta); Δ (Greek capital letter Delta).
  • g (Latin small letter G); G (Latin capital letter G); (partial differential); (nabla).
  • h (Latin small letter H); H (Latin capital letter H); θ (Greek small letter Theta); Θ (Greek capital letter Theta).
  • j (Latin small letter J); J (Latin capital letter J); (integral); ı (Latin small letter dotless I).
  • k (Latin small letter K); K (Latin capital letter K); ø (Latin small letter O with stroke); Ø (Latin capital letter O with stroke).
  • l (Latin small letter L); L (Latin capital letter L); λ (Greek small letter Lambda); Λ (Greek capital letter Lambda).
  • ; (semicolon); : (colon); ë (diaeresis dead key); (tilde dead key).
  • (apostrophe); (quotation mark); á (acute accent dead key); à (grave accent dead key).

Row 4:

  • z (Latin small letter Z); Z (Latin capital letter Z); (intersection); (logical and).
  • x (Latin small letter X); X (Latin capital letter X); (union); (logical or).
  • c (Latin small letter C); C (Latin capital letter C); (element of); (not an element of).
  • v (Latin small letter V); V (Latin capital letter V); (subset of or equal to); (neither a subset of nor equal to).
  • b (Latin small letter B); B (Latin capital letter B); (asymptotically equal to); (approximately equal to).
  • n (Latin small letter N); N (Latin capital letter N); (not equal to); (empty set).
  • m (Latin small letter M); M (Latin capital letter M); μ (Greek small letter Mu); µ (micro sign).
  • , (comma); < (less-than sign); ȩ (cedilla dead key); ę (ogonek dead key).
  • . (full stop); > (greater-than sign); ė (dot above dead key); ē (macron dead key).
  • / (solidus); ? (question mark); ¬ (not sign); ¿ (inverted question mark).