Recognising countable sets

As may be obvious from the sudden increase in my posting rate (which I don’t expect to be able to keep up) The Princeton Companion to Mathematics is now off my hands, which gives me the chance to devote a bit of attention to other projects, of which the Tricks Wiki is one. So in this post I’m going to discuss a relatively elementary piece of university mathematics, and will do so in the form of a sample article for that site. I’ll be a little careful about predicting when the site itself will be up and running, but let me just say that I’ve put some work into it recently and I don’t want to waste that work.

In what follows, I shall adhere to what I hope will be the basic format of an article on the site. The most important elements of that format are that there is a brief description, or “slogan”, that encapsulates the basic idea, and a general discussion of the idea that is illustrated by several clearly delineated examples.

Actually, I think I’ll give the discussion in the form of two sample articles, since it really contains two separate ideas.

The first one originates in a recent change of mind that I’ve had when teaching countability. I always used to stress that the main tool for this was the lemma that a countable union of countable sets is countable. But I now think that that is not in fact the best thing to stress (though it can of course be useful), because there’s another, much simpler, lemma that tends to lead to proofs that I prefer.

Article 1.  A basic lemma for proving that a set is countable. 

Prerequisites: The definition of a countable set, function-related notions such as injections and surjections.

Quick description: If you can find a function from A to \mathbb{N} such that every n has finitely many preimages, then A is countable.

General discussion:  Here is a quick informal account of a standard proof that the set \mathbb{N}\times\mathbb{N} is countable: we can list its elements in the order (1,1), (2,1), (1,2), (3,1), (2,2), (1,3), (4,1), and so on. (This is informal because I have talked about “lists” and have not actually defined how the sequence continues.) We can view this proof geometrically as follows: in order to count through the set \mathbb{N}\times\mathbb{N}, which forms an infinite grid in the plane, we note that each downward-sloping diagonal (that is, a set of pairs of positive integers with constant sum) is finite, and then we count through each of these sets in turn.

Here, we are making use of the very simple principle that a countable union of finite sets is countable. To put this more formally, if A is a set that can be written as a union \bigcup_{n=1}^\infty A_n for some collection A_1,A_2,\dots of finite sets, then A is countable.

This is very easy to see informally: one just counts through each A_n in turn (leaving out elements that have already been counted). It is not important for this article, but for completeness let us briefly see how we might prove it more formally. We could write each set A_n as \{a_{n1},\dots,a_{nk_n}\}, where k_n is the size of A_n. And then we could define an ordering on all pairs (n,m) with m\leq k_n by taking (n,m)<(r,s) if and only if either (i) n<r or (ii) n=r and m<s. And then we would define a function f:A\rightarrow\mathbb{N} by the following procedure. We would repeatedly choose the element a_{ij} with minimal index (i,j) for which f(a_{ij}) was not yet defined, and we would define it to be the minimal integer that was not yet assigned as a value of f. It is not hard to check that one ends up assigning a value to all elements of A and we never assign the same value twice. Thus, f is an injection and A is countable.

In particular, a set A is countable if there is a function f:A\rightarrow\mathbb{N} such that every n\in\mathbb{N} has finitely many preimages. (This means that for every n\in\mathbb{N} there are only finitely many a\in A with f(a)=n.) This follows because we can define A_n to be \{a\in A:f(a)=n\}, and then we have expressed A as a countable union of finite sets.

This observation is not particularly interesting as a theoretical statement, but as a tool for giving quick proofs of countability it is extremely useful. Here are some examples.

Example 1.  To prove that the rational numbers form a countable set, define a function f that takes each rational number p/q (which we assume to be written in its lowest terms, with q>0) to the positive integer |p|+|q|. The number of preimages of n is certainly no more than (2n+1)^2, so we are done.

As another aside, it was a bit irritating to have to worry about the lowest terms there. For some reason many mathematicians are afraid of multifunctions (that is, things that are like functions except that each element in the domain can map to several elements in the range) and sweep them under the carpet. But for the rationals it is convenient to have them. We define a multifunction f from \mathbb{Q} to \mathbb{N} by mapping p/q to |p|+|q|. This looks as though it isn’t well-defined, which as a function it isn’t, but if we think of it as a multifunction, then for instance the rational number 2/3 maps to all possible values of |p|+|q| for which 3p=2q. (If you really don’t like this, then you could rephrase it in terms of bipartite graphs or something like that.) Each positive integer n still has only finitely many preimages (defined to be any rational number that has at least one image equal to n), and this proves the result since any multifunction with that property can clearly be restricted to a function with that property (just select, for each element of the domain, one of its images).

Example 2. To prove that the set of all finite subsets of \mathbb{N} is countable, how might we find a suitable function? An obvious function to consider is f(A)=|A|, but this doesn’t work since there are infinitely many sets of any given size. (OK, apart from size zero.) But there’s another very simple function that works: f(A)=\max A. Clearly, the number of sets with maximal element n is finite (in fact, it is 2^{n-1}), so we are done.

Example 3. To prove that the set of all polynomials with integer coefficients is countable is a similar exercise, but slightly more complicated. It is tempting to consider the sum of the absolute values of the coefficients, but then we notice that the polynomials 1, x, x^2, x^3, \dots all have coefficients with absolute values adding up to 1. So we need to restrict the degree somehow. But that is very easy indeed: given a polynomial P we define f(P) to be the degree of P plus the sum of the absolute values of the coefficients of P.

Example 4. To prove that the set of all algebraic numbers is countable, it helps to use the multifunction idea. Then we map each algebraic number \theta to every polynomial with integer coefficients that has \theta as a root, and compose that with the function defined in Example 3. It is easy to check (using the fact that every polynomial has finitely many roots) that for every integer n there are at most finitely many algebraic numbers that map to n, and we are done.

End of Article 1.


Note that the above article didn’t really describe a “trick” so much as a reasonably straightforward technique. That was deliberate: despite its name, the Tricks Wiki is not supposed to be exclusively for demonstrating mathematical sleight of hand, though there is a place for that. The main distinguishing feature of the articles is that they should tell you how to prove things rather than what is true. In that respect, the quick description was misleading, since I stated it as a lemma. But in this case I think it goes without saying that what I really meant was not the lemma itself but rather, “If you want to prove that a set A is countable, try to find a function f from A to \mathbb{N} such that the inverse image of every n is finite.”

The second article is meant to illustrate a principle that is less a proof technique (though it can in theory be used for that) and more a quickly-seeing-what-is-true technique.


Article 2. How to see easily that a given countable set is countable.

Prerequisites: The definition of a countable set, Article 1.

Quick description: A set A is countable if there is a way of giving a finite description to every element of A.

General discussion: It is not hard to prove that the set of all finite strings of symbols taken from a fixed finite alphabet is countable. Indeed, we can count in turn the strings of length 0, 1, 2, and so on. If the size of the alphabet is k then for each n there are k^n strings of length n, and in particular finitely many. Therefore, by the simple lemma discussed in Article 1, we are done (either by saying that we have expressed the set of all finite strings as a countable union of finite sets or by considering the function that takes each string to its length).

It follows from this that if A is any set, and if we can come up with a procedure for giving a finite description (in, say, the English language augmented by a few convenient mathematical symbols) to each of the elements of A, then A is countable. After all, the description takes the form of a finite string of symbols taken from some fixed “alphabet” of symbols, and there are only countably many of those.

This is significant because it often gives an easy way of recognising that a set is countable. It also gives proofs of countability, but these proofs are usually slightly “silly” and better replaced by simpler ones. But if you have ever known instinctively that a set is countable before you have actually come up with a proof, then it may well be something like this principle that is in the back of your mind.

Example 1. The rationals are countable because every rational has a description such as -35792/1293879861. Here, the alphabet is \{0,1,...,9,-,/\}.

Example 2. The set of all polynomials with integer coefficients is countable since (a very slight modification of) the normal way of writing down such a polynomial is a finite string of symbols taken from the alphabet \{0,1,\dots,9,+,-,x,\wedge\}. Here, the symbol \wedge is used instead of the normal notation for exponentiation, so for instance instead of writing x^3-3x+1 we would write x\wedge 3-3 x+1.

Example 3. The set of all algebraic numbers is countable, since each one is a root of a polynomial that can be described as above, and for any fixed polynomial we can specify which root we are talking about in terms of the ordering on \mathbb{R}. For example, we could describe (1+\sqrt{5})/2 as “the larger root of x \wedge 2-x-1”. If we allow complex numbers then we could choose an ordering of the roots by taking them in order of their modulus, and for roots of equal modulus we could order them by their arguments (defined to lie in the interval \null [0,2\pi)). For example, -i could be defined as “the second root of the polynomial x\wedge 2+1”. 

Alternatively, and more naturally, we could argue that since the set of polynomials with integer coefficients is countable and each such polynomial has finitely many roots, an easy deduction from the principle of Article 1 shows that the algebraic numbers are countable.

Example 4. The set of all non-increasing functions from \mathbb{N} to \mathbb{N} is countable. This time the fact that there is a finite description relies on the well-ordering principle for the natural numbers, which implies that every non-increasing function from \mathbb{N} to \mathbb{N} is constant from some point on. So every such function will have a description such as “f(1)=23, f(2)=12, f(3)=f(4)=5 and f(n)=3 for every n\geq 5.”

Example 5. The set of all finite subsets of \mathbb{N} is countable, since each one can be finitely described by simply writing it in the usual way using the symbols, \{, \}, the integers from 0 to 9, and commas.

Conclusion: I cannot think of any explicitly defined countable set that isn’t completely obviously countable by this criterion.

End of Article 2.

These articles have some features that will not be typical of Tricki articles, so to give a more balanced picture I plan to put up a few more samples over the next few weeks. Comments are welcome, both about their form and about their content.

9 Responses to “Recognising countable sets”

  1. Mark Meckes Says:

    I haven’t looked carefully at the content yet, but I think the basic prerequisites-quick description-general discussion-examples layout is great. I think it might be even better, though, to put the quick description before the prerequisites. That would seem to me to better reflect the way we often learn and use new tricks in math: first you figure out what you’d like to be able to do, and then you fill in whatever background you’re missing to understand how to do it.

    This suggestion may seem somewhat silly with regard to the sample articles above, given that you need the definition of countability to appreciate the titles themselves, but there will probably be many tricks that involve ideas that don’t appear explicitly in the title or even in the quick description.

  2. gowers Says:

    Mark, looking at what I wrote again, I find that I completely agree with you. But I think that on the site itself the layout will be different anyway. Probably there will be a little column on the side with information about things like prerequisites, the intended audience, the area(s) of mathematics to which the article is relevant, keywords, and so on.

  3. Mark Meckes Says:

    Tim, that sounds even better.

  4. davidspeyer Says:

    Regarding the claim “I cannot think of any explicitly defined countable set that isn’t completely obviously countable by this criterion.”: the set of zeros of the Riemann zeta function.

    This is countable by another standard trick: to prove that a subset of \mathbb{C} (or \mathbb{R}) is countable, show that it has no accumulation point. Indeed, the zeroes of any nonzero complex analytic function are countable for this reason.

  5. Per Vognsen Says:

    “If you can find a function from A to \mathbb{N} such that every n has finitely many preimages, then A is countable.”

    It seems beneficial to generalize this ever so slightly to say, if you can find a function from A to some countable set B (of which N is the prototype and exemplar) such that every x in B has finitely many preimages, then A is countable.

    To demonstrate:

    “To prove that the set of all polynomials with integer coefficients is countable is a similar exercise, but slightly more complicated.”

    In your proof, you are essentially composing together three smaller, simpler proofs and three individual functions:

    f : Z[x] -> N[x]

    This takes absolute values coefficient by coefficient. A polynomial of degree n in N[x] can have no more than 2^(n+1) preimages, for there is at most a two-choice sign ambiguity for each of the n+1 coefficients.

    g : N[x] -> NxN

    This takes a_0 + a_1 x + … + a_n x^n to (n, a_0 + a_1 + … + a_n). Actually, a simpler way would be to take the image as (n, max {a_0, a_1, …, a_n}), for then (x,y) is easily seen to have no more than (y+1)^x preimages.

    h : NxN -> N

    This takes (x,y) to x+y. This is the function you already used in your proof of NxN’s countability.

  6. A small countability question « Gowers’s Weblog Says:

    […] davidspeyer pointed out in an interesting comment on the previous countability post, there do exist explicitly definable sets that we can show are countable even though we cannot give […]

  7. elacaraq Says:

    “If you can find a function from A to \mathbb{N} such that every n has finitely many preimages, then A is countable.”

    Can we just say, if we can find a function from A to \mathbb{N} such that every n has countably many preimages, then A is countable? This way A is indeed a countable union of countable sets.

    Like the polynomial example, if we map each polynomial to the coefficient of its highest term, then every n have \mathbb{N} as its preimages, hence the set of all polynomials is countable.

  8. gowers Says:

    elacaraq, the stronger statement that A is countable if there’s a function to \mathbb{N} such that every n has countably many preimages is true too, and is another way of saying that a countable union of countable sets is countable. But I prefer to tie my hands behind my back and use just the weaker statement because I like the proofs that result.

    In the polynomials case, if you map each polynomial to the coefficient of its highest term, then it’s not all that easy to prove that the preimage of n is countable. Indeed, given any polynomial P of degree d, you can add the polynomial nx^{d+1} to it and obtain a polynomial with leading term n, so proving that the preimage of n is countable is precisely as hard as proving that the set of all polynomials with integer coefficients is countable, which is of course the problem we started with.

  9. elacaraq Says:

    Dear Gowers: Yes, I realized the problem in my polynomial example. What I had in mind was to map each polynomial to its degree. So for each n there are countablely many polynomials with degree n. However this needs proof too. I see that your weaker statement is actually more convincible.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: