Thread by @wtgowers

I'm experiencing a small esprit d'escalier about the countability thread, so here is a shorter second thread to supplement it, before I get on to other notions of smallness for sets of real numbers. 1/

First, here's a general-purpose and very widely applicable method of showing that an explicitly defined set is countable. All you have to do is find a way of specifying each element of that set using a description of finite length. 2/

Some examples of such sets.

1. The rationals work because each rational number can be written as something like 67108864/32769, which is a finite string of symbols, each of which is either a numerical digit, a forward slash, or a minus sign. 3/

2. The finite sets of integers work, because each one has a description such as {34, 35, 49, 77, 108, 2256}, which is made out of digits, set-theoretic brackets, commas and spaces.

3. The definable real numbers (once you have specified what constitutes a ... 4/

definition and how it is to be interpreted) work, since each one is (by definition of "definition") a finite string of symbols from some finite alphabet. Note that this implies that there are undefinable real numbers! Obviously I can't define one, but ... 5/

given any definition method, I can specify one by using Cantor's diagonal argument. (That means I have defined it, but not using the original definition method. I don't want to go any further down this rabbit hole though.) 6/

Why are all these sets countable? Once again we can use the "complexity" idea, measuring complexity by the number of symbols (including spaces) used in the description. Since there are finitely many objects of any given complexity, we can list them in order of complexity. 7/

For a bit more flexibility, we can observe that we don't actually have to specify individual elements. All we need is to give properties of those elements such that (i) each property is satisfied by only finitely many elements and (ii) each element satisfies one of them. 8/

An example where this is useful is the algebraic numbers: we can use properties like "is a root of x^3-x+22" and not bother saying which root we are talking about. The fact that each polynomial has finitely many roots is enough to give us countability. 9/

Does this method always work? I said it worked for explicitly defined sets, but sometimes we want to deduce that a set is countable from the fact that it has some other property. For instance, if X is a set of reals and for every element x there is some positive ... 10/

number a_x such that X contains no number in the open interval (x, x+a_x), then X is countable. A slick proof is that for each x there must be a rational number q in that open interval, and different xs must have different qs. So I suppose you could argue that we ... 11/

can finitely specify x by specifying that rational, but that is more like a theoretical argument that a specification exists than an actual specification. 12/

The main point of all this: if you're given a concrete set and asked to prove that it is countable, there is almost always a trivial proof of that fact. 13/13