A look at a few Tripos questions VII

The obligatory question on countability/uncountability.

5C. Define what is meant by the term countable. Show directly from your definition that if X is countable, then so is any subset of X.

Show that \mathbb{N}\times\mathbb{N} is countable. Hence or otherwise, show that a countable union of countable sets is countable. Show also that for any n\geq 1, \mathbb{N}^n is countable.

A function f:\mathbb{Z}\to\mathbb{N} is periodic if there exists a positive integer m such that, for every x\in\mathbb{Z}, f(x+m)=f(x). Show that the set of periodic functions f:\mathbb{Z}\to\mathbb{N} is countable.

If you’ve got countability straight in your head — by which I mean that you have learnt the statements and proofs of about four key facts, as well, of course, of knowing the precise definitions of countable and uncountable — then you should find this question very quick and easy. (My impression is that all these 2003 questions are easier than average, which has unfortunately made them not as good an illustration as I had hoped of how to get through an exam.)

If you read the whole of the first paragraph, you will see a slight implication that you have a choice, since the question says “your definition” rather than “the definition”. And indeed you do.

To begin with, there is the annoying question of whether “countable” implies “infinite”. There is no universally agreed standard about this. I myself prefer to say that finite sets are countable, but it is possible that your lecturer used the opposite convention. (The reason I like mine is that I think of countability as a kind of smallness, so I don’t want to insist that my countable sets are also large in some way. Also, there are just too many circumstances where one has to say “finite or countable” if you insist that countable sets are infinite. However, I do sometimes find myself having to say “countably infinite”. It’s a bit like the debate about what the symbol \subset means. For me it means “is a subset of” rather than “is a proper subset of”, because I don’t often have to worry about proper subsets, so I’d rather occasionally write \subsetneq for proper subsets than always write \subseteq for arbitrary subsets.)

I’m going to assume that “countable” was defined in your lectures in such a way that finite sets are countable. Even if we grant this, however, you still have a choice, because the following three statements are equivalent (at least for non-empty sets).

1. There is an injection from X to \mathbb{N}.

2. There is a surjection from \mathbb{N} to X.

3. X is finite or there is a bijection from X to \mathbb{N}.

I think it is really the awkwardness of the third definition that tempts people to require countable sets to be infinite — then one can simply say that a set is countable if there is a bijection between that set and \mathbb{N}.

But is that a good argument? Let’s have a look at the first thing we’re asked to do. OK, I’ve just noticed that the question doesn’t even allow the definition that requires a set to be infinite, since then it wouldn’t be true that a subset of a countable set is countable. So it’s clear what the Cambridge convention was in 2003 at least. (I have a funny feeling the lecturer was … er … me that year. But I didn’t set the question.)

Let’s think briefly about which of the three possible definitions will lead to the smoothest proof that a subset of a countable set is countable. And we quickly see that either of the first two definitions works just fine, though the first is slightly easier because you don’t have to argue separately for the empty set (which is problematic because there is no surjection from \mathbb{N} to \emptyset), while the third definition is a bit of a nightmare. Moral: go for the first definition. More general moral: in a situation like this, don’t just write down the first definition that occurs to you.

Yet another moral, specific to countability, is this: use the formal definitions, and not some intuitive notion of “putting the elements in a list”. After all that, let me deal with the first paragraph of the question.

A set X is countable if there is an injection from X to \mathbb{N}. Suppose that X is countable and Y\subset X, and let f:X\to\mathbb{N} be an injection. Define a map g:Y\to\mathbb{N} by setting g(y)=f(y) for every y\in Y. Then g is an injection, so Y is countable.

I might well be tempted by the briefer answer where the last two sentences are replaced by “Then the restriction of f to Y is an injection, so Y is countable.”

There are all sorts of ways of showing that \mathbb{N}\times\mathbb{N} is countable. A quick one would be this.

By the fundamental theorem of arithmetic, the function (m,n)\to 2^m3^n is an injection. Therefore, \mathbb{N}\times\mathbb{N} is countable.

Now we get a “hence or otherwise”. This is a case where the “otherwise” is perfectly OK, but the “hence” is quicker, which is why the examiner is (implicitly) recommending it. If we’ve got our countable collection of countable sets, we have an injection from each of those countable sets into \mathbb{N}. We can then put all those injections together to get an injection from the union into \mathbb{N}^2, and composing that with the injection we had from \mathbb{N}^2 to \mathbb{N} gives us an injection to \mathbb{N}. Here’s what I’d actually write.

Let X_1,X_2,\dots be countable sets. (If there are only finitely many of them, the proof is similar but easier.) For each n, let f_n:X_n\to\mathbb{N} be an injection.

A quick pause here, to confess that I was about to write something wrong. What I was about to write was this.

Define a function f:\bigcup_nX_n\to\mathbb{N}\times\mathbb{N} as follows. If x\in X_n, then f(x)=(n,f_n(x)).

The trouble is that x could be in more than one X_n. To sort this out, we instead write the following.

Define a function f:\bigcup_nX_n\to\mathbb{N}\times\mathbb{N} as follows. For each x\in\bigcup_nX_n, let m be minimal such that x\in X_m and define f(x)=(m,f_m(x)). Then if f(x)=f(y)=(r,s), we know that x,y\in X_r and f_r(x)=f_r(y)=s, which implies that x=y, since r is an injection. Therefore f is an injection.

We are now asked to prove that \mathbb{N}^n is countable for every n. Here’s the proof that the examiner clearly had in mind.

We prove this by induction. It is obviously true when n=1. If it is true for n, then it is true for n+1, since \mathbb{N}^{n+1}=\bigcup_r\{r\}\times\mathbb{N}^n, which is a countable union of countable sets.

I much prefer the following way of proving that sets are countable. Intuitively, a set is countable if every element of that set has a finite description. And the reason it is countable is that there are only finitely many elements that can be described using a description of length at most n, so it is a countable union of finite sets. That intuitive idea can usually be turned into a quick and completely rigorous proof.

Here’s what I’d do for \mathbb{N}^n. I’d note that you can describe an element of \mathbb{N}^n just by writing down n integers, each of which has finitely many digits. So it’s obviously countable. How do I measure the “complexity” of an element? A natural way is simply to take the sum of the numbers involved (the maximum would work just as well). So I’d write this.

For each r the set S_r of (x_1,\dots,x_n)\in\mathbb{N}^n such that x_1+\dots+x_n\leq r is finite. Since \mathbb{N}^n=\bigcup_rS_r, \mathbb{N}^n is countable.

Yet another proof directly generalizes the proof that \mathbb{N}\times\mathbb{N} is countable. (I like it less because it involves an unnecessary clever idea, but it’s undoubtedly quick to write out.)

Let p_1,\dots,p_m be the first m primes. By the fundamental theorem of arithmetic, the function f:\mathbb{N}^m\to\mathbb{N} that takes (a_1,\dots,a_m) to p_1^{a_1}\dots p_m^{a_m} is an injection. Therefore, \mathbb{N}^m is countable.

On to the last part. First, let’s think about what the examiner has in mind. Clearly, we are supposed to observe that there is a one-to-one correspondence between functions with period m and elements of \mathbb{N}^m. The correspondence takes the function f to the element (f(1),f(2),\dots,f(m)), and in the reverse direction takes the m-tuple (x_1,\dots,x_m) to the function that takes an integer r to x_s, where s is the unique integer between 1 and m that is congruent to r mod m.

Here’s what I might write in order to give the intended answer.

For each m, let F_m be the set of all functions f:\mathbb{Z}\to\mathbb{N} of period m. Then it is enough to prove that each F_m is countable, since the set of all periodic functions is the (countable) union of the F_m.

But the function \phi:F_m\to\mathbb{N}^m that takes f to (f(1),\dots,f(m)) is an injection, since once you know the values of a function in F_m at 1,\dots,m then you know the entire function. Since \mathbb{N}^m is countable, there is an injection from \mathbb{N}^m to \mathbb{N}. Composing with \phi we see that F_m is countable, as desired.

And here is the proof that I prefer. Again, we think about how much information is needed to specify a periodic function, and realize that we’ve pinned it down if we say what the period m is and then say what the values are at 1,2,\dots,m. So we can write this.

For each periodic function f, write \pi(f) for the period of f. Let P_r be the set of all periodic functions f such that \pi(f)+f(1)+\dots+f(\pi(f))\leq r. Then each set P_r is finite and their union includes all periodic functions. The result follows.

Finally, for those who like the prime-factorization approach, you could go for this, though it seems to be a bit longer to write out than the previous approach.

Define a map \psi from the set of all periodic functions that takes a function f to the integer p_1^{f(1)}\dots p_m^{f(m)}, where p_1,\dots,p_m are the first m primes and m is the period of f. Then \psi is an injection, by the fundamental theorem of arithmetic and the fact that the first m values of f determine f when f has period m.

12 Responses to “A look at a few Tripos questions VII”

  1. Joel Says:

    I suppose that you need to allow the “empty function” from the empty set to the natural numbers to provide the injection in that case. (Not that I have any objection to the empty function!)

  2. Richard Baron Says:

    When you refer to finite descriptions, do you need to specify that the descriptions are composed using symbols drawn from a finite alphabet? Or is that too obsessive about details?

    I think that once you have established the results in this question, you can say that finite describability using symbols drawn from a countably infinite alphabet establishes countability, but we have to establish the result first.

    • gowers Says:

      I did indeed mean that I was using a finite alphabet. But since every description I’ve ever given of a mathematical object (at least if it pins down that object uniquely) uses a finite alphabet, I didn’t bother to say so.

      There is a different meaning of “description” for which this reply wouldn’t work. For example, one might say that every linear map from \mathbb{R}^2 to \mathbb{R}^2 can be described using just four real numbers (the numbers that make up the matrix of the map with respect to the standard basis), or that every orientable compact 2-manifold can be described by means of one non-negative integer (its genus).

      Actually, if the alphabet is countable, then it might as well be finite, since instead of using countably many different symbols, one might as well use positive integers, which we know how to represent finitely with a finite alphabet.

  3. Max Says:

    The formulation of the question *requires* that countable includes finite: otherwise it is not true that “if X is countable, then so is any subset of X.” There is a choice of definition, but not a choice of meaning.

  4. Max Says:

    I should have read to the end before commenting 🙂

  5. Anonymous Says:

    The discussion of periodic functions appears to assume, without expressly stating, that m is the least period of the function in question.

    I don’t know if failing to make that explicit would cost marks, but since all that is required is “Let m > 0 be the least integer such that for all x, f(x) = f(x+m)” it’s probably worth doing so.

    (The codomain of the map $\phi : f \mapsto (f(1) ,…, f(m))$ is stated to be N, rather than N^m as clearly intended.)

    Thanks — corrected now.

    • gowers Says:

      I can’t find anywhere where I assumed that: I use the phrase “the period of” to refer to the least m such that the function repeats every m integers. But I may have missed a point where I wasn’t quite clear about this.

  6. Robber Says:

    I really would have loved these a few years ago!

    Any chance of doing the same for Part III courses ;)?

    • gowers Says:

      The best I can do for Part III is suggest that when a question asks you, in a slightly disguised way, to write out a certain chunk of your notes, then you should do your best to write out that chunk. Good luck …

  7. Peter L. Griffiths Says:

    Gowers misses the point about the ages for learning maths, the age range is from 10 to 15. For the ages 10 to 12 the teachers need not be very advanced mathematicians but they should be really good at teaching what little maths they do know. Educational systems round the world have completely failed to adjust to this situation.

  8. Andrej Says:

    I’m late on this, as I’m just clearing the backlog of unread articles from your blog in my RSS feed, but I think there’s a typo where it says “which implies that x = y, since r is an injection.” I think you meant f_r is an injection, right?

    Other than that, I really like the various approaches you’ve taken to prove the desired results, as I wouldn’t have thought of using, say, the prime factorization method myself. I’ve also never been taught the “finite description trick” for the determination of countability, and am still not entirely comfortable with it, but your examples on this blog will hopefully ultimately lead to me adding another tool to my maths toolbox.

Leave a Reply

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

WordPress.com Logo

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

Google photo

You are commenting using your Google 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 )

Connecting to %s

%d bloggers like this: