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

About these ads

This entry was posted on May 20, 2012 at 11:19 am and is filed under Cambridge teaching, IA Numbers and Sets. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

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

Joel Says:
May 20, 2012 at 12:14 pm | Reply
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
Richard Baron Says:
May 20, 2012 at 10:13 pm | Reply
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:
  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 $\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.
Max Says:
May 21, 2012 at 11:13 am | Reply
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.
Max Says:
May 21, 2012 at 11:14 am | Reply
I should have read to the end before commenting
Anonymous Says:
May 21, 2012 at 9:29 pm | Reply
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:
  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 $m$ such that the function repeats every $m$ integers. But I may have missed a point where I wasn’t quite clear about this.
Robber Says:
May 23, 2012 at 11:22 pm | Reply
I really would have loved these a few years ago!

Any chance of doing the same for Part III courses ?
- gowers Says:
  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 …
Peter L. Griffiths Says:
August 8, 2012 at 2:16 pm | Reply
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.
- gowers Says:
  August 8, 2012 at 2:35 pm
  I’m struggling to relate this comment to the post. Was it intended for a different post?

Gowers's Weblog