Thread by @wtgowers

This is the first of at least two, but possibly more, threads about small sets of real numbers. When they are done, I'll link them into a 2D super-thread.

What is a small set of real numbers? It turns out that there are several good answers to that question. 1/

The best known is to say that a set of real numbers is small if it is countable, where we say that a set A is countable if its elements can put in a (finite or infinite) list a_1,a_2,a_3,...

A non-obvious example of a countable set is the set of all rational numbers, 2/

which can't be listed in increasing order of size, but can be listed in increasing order of "complexity". For instance, let us define the complexity of a fraction to be the larger out of the size of its numerator and the size of its denominator. By this definition, 3/

the complexity of -5/7 is 7 and the complexity of 10/3 is 10. It's obvious that (i) the complexity is a positive integer and (ii) there are only finitely many fractions of any given complexity. So we can list the fractions of complexity 1, then those of complexity 2, etc. 4/

Cantor's famous diagonal argument shows that the set of real numbers is not countable. The version most often presented uses decimal expansions, but I prefer his original proof, which goes as follows. Suppose you have a sequence a_1,a_2,a_3... of real numbers. 5/

We'd like to find a real number that doesn't belong to the sequence. To do this we find a closed interval [u_1,v_1] (with u<v) that doesn't contain a_1. Inside that we find a closed interval [u_2,v_2] that doesn't contain a_2. We continue like this and then take a number 6/

(in fact, the only number) that belongs to all the closed intervals, and by construction it isn't equal to any of the numbers a_n. 7/

A fundamental fact about countable sets is that a union of countably many countable sets is countable. That is, if A_1,A_2,A_3,... are all countable sets, then so is the union of all those sets. The proof is similar to the one about rationals. Suppose we have listed 8/

all the elements of all the sets. Then let us say that the mth element of the nth set has complexity max{m,n}. For instance, the complexity of the 103rd element of the 87th set is 103 and the complexity of the 14th element of the 1000th set is 1000. Then again there are 9/

finitely many elements of any given complexity, which allows us to list them all. (If the sets are not disjoint, we can just assign the smallest possible complexity to each element.) 10/

What is so important about this fact? It's that it allows us to regard countable sets as "small". If we do so, we have the great property that a union of countably many small sets is still small, and thanks to Cantor we know that the set of all real numbers isn't small. 11/

This allowed Cantor to give a cheeky proof of the existence of transcendental numbers -- that is, numbers that are not solutions of polynomial equations with integer coefficients. Let's see how this works. We'll start with a very basic statement: the set of all polynomials 12/

of degree zero (that is, constants) and integer coefficients is small. That's because we can list them 0, 1, -1, 2, -2, 3, -3, etc. Now let's do linear polynomials. Here we can say that for each coefficient of x there are countably many possible constant terms, 13/

so we get a countable union of countable sets ... done! And we can carry on in that way.

A shorter proof uses a complexity notion again. Let's define the complexity of a polynomial to be the maximum of (i) its degree and (ii) the sizes of any of its coefficients. 14/

As ever, there are only finitely many polynomials of any given complexity, so we are done.

We then argue that since each polynomial has only finitely many roots, the set of possible roots is countable (as it's a union of countably many finite sets, one for each polynomial).15/

But since the reals are not countable, there must be a real that isn't a root of a polynomial with integer coefficients.

I said that there are other useful notions of smallness, but since this thread is threatening to spiral out of control, I shall save those for 16/

further instalments of this super-thread. I'll finish with the teaser that the culmination of the super-thread will be one of my favourite surprises in mathematics (and part way through there will be another extremely cool fact). 17/17