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 .