The obligatory question on countability/uncountability.

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

Show that is countable. Hence or otherwise, show that a countable union of countable sets is countable. Show also that for any , is countable.

A function is *periodic* if there exists a positive integer such that, for every , . Show that the set of periodic functions 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 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 for proper subsets than always write 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 to .

2. There is a surjection from to .

3. is finite or there is a bijection from to .

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 .

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 to ), 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 is *countable* if there is an injection from to . Suppose that is countable and , and let be an injection. Define a map by setting for every . Then is an injection, so is countable.

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

There are all sorts of ways of showing that is countable. A quick one would be this.

By the fundamental theorem of arithmetic, the function is an injection. Therefore, 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 . We can then put all those injections together to get an injection from the union into , and composing that with the injection we had from to gives us an injection to . Here’s what I’d actually write.

Let be countable sets. (If there are only finitely many of them, the proof is similar but easier.) For each , let 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 as follows. If , then .

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

Define a function as follows. For each , let be minimal such that and define . Then if , we know that and , which implies that , since is an injection. Therefore is an injection.

We are now asked to prove that is countable for every . Here’s the proof that the examiner clearly had in mind.

We prove this by induction. It is obviously true when . If it is true for , then it is true for , since , 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 , 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 . I’d note that you can describe an element of just by writing down 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 the set of such that is finite. Since , is countable.

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

Let be the first primes. By the fundamental theorem of arithmetic, the function that takes to is an injection. Therefore, 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 and elements of . The correspondence takes the function to the element , and in the reverse direction takes the -tuple to the function that takes an integer to , where is the unique integer between 1 and that is congruent to mod .

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

For each , let be the set of all functions of period . Then it is enough to prove that each is countable, since the set of all periodic functions is the (countable) union of the .

But the function that takes to is an injection, since once you know the values of a function in at then you know the entire function. Since is countable, there is an injection from to . Composing with we see that 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 is and then say what the values are at . So we can write this.

For each periodic function , write for the period of . Let be the set of all periodic functions such that . Then each set 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 from the set of all periodic functions that takes a function to the integer , where are the first primes and is the period of . Then is an injection, by the fundamental theorem of arithmetic and the fact that the first values of determine when has period .

May 20, 2012 at 12:14 pm |

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

Joel

May 20, 2012 at 10:13 pm |

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.

May 21, 2012 at 9:32 pm

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

May 21, 2012 at 11:13 am |

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.

May 21, 2012 at 11:14 am |

I should have read to the end before commenting :)

May 21, 2012 at 9:29 pm |

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.May 21, 2012 at 9:37 pm

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

May 23, 2012 at 11:22 pm |

I really would have loved these a few years ago!

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

May 24, 2012 at 4:57 am

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 …

August 8, 2012 at 2:16 pm |

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.

August 8, 2012 at 2:35 pm

I’m struggling to relate this comment to the post. Was it intended for a different post?

June 18, 2013 at 5:03 pm |

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.