A short post on countability and uncountability

There is plenty I could write about countability and uncountability, but much of what I have to say I have said already in written form, and I don’t see much reason to rewrite it. So here’s a link to two articles on the Tricki, which, if you don’t know, is a wiki for mathematical techniques. The Tricki hasn’t taken off, and probably never will, but it’s still got some useful material on it that you might enjoy looking at. The articles in question are one about how to tell almost instantly whether a set is countable and another about how to find neat proofs that sets are countable when they are.

The main additional point I’d like to make about this whole area is that you will do much better if you follow some of the general advice from earlier in this series of posts and work from the formal definitions and basic facts that you have been taught. Perhaps I can make that clearer by spelling out what you shouldn’t do, which is to pay too much attention to the words “countable” and “uncountable”. Let’s face it, you can’t count the natural numbers — you’ll be dead long before you’ve got to 10^{20}. You can’t even put them in a list, since the number of atoms in the universe is only around 10^{79}. And if you imagine some hypothetical world where you live for ever, you’ll never actually finish counting through the natural numbers if you try to do so (unless you find some way of speeding up without limit so that the sum of the times you take converges, but let’s not go there). So if you think of countable as meaning “can be counted”, then you risk confusing yourself — and I know for a fact that many people do end up confusing themselves.

Far better to stick to basic facts and definitions that are stated in precise mathematical language. Here’s a list of them — I may forget one or two important ones but I’ll try not to. You should have all these facts at your fingertips. (If you can prove the ones that aren’t definitions, then so much the better, but knowing the facts is even more important than knowing the proofs, since it is the facts themselves that you will use to go on to prove other things.)

Incidentally, some people use the convention that all finite sets are countable, whereas others use the word “countable” only for infinite sets. I’ll use the convention that finite sets are countable, so if you prefer the other convention then you’ll have to make some small modifications.

1. A set X is finite if for some n there is a bijection \phi:X\to\{1,2,\dots,n\}. Otherwise, it is infinite.

2. A set X is countable if and only if it is finite or there is a bijection \phi:X\to\mathbb{N}. Otherwise, it is uncountable.

3. Two sets X and Y are said to have the same cardinality if there is a bijection \phi:X\to Y.

4. If X and Y are sets, then X has cardinality at most that of Y if there is an injection \psi:X\to Y.

5. If X and Y are sets and X is non-empty, then the following two statements are equivalent.

(i) There is an injection from X to Y.

(ii) There is a surjection from Y to X.

6. Let X be an infinite set. The following statements are equivalent.

(i) There is a bijection from X to \mathbb{N}.

(ii) There is an injection from X to \mathbb{N}.

(iii) There is a surjection from \mathbb{N} to X.

[Note that this gives three potential ways of proving that X is countable. Although I gave (i) as the definition of countability, it is usually much more convenient to prove (ii).]

7. \mathbb{R} is uncountable.

8. If X is any set, then the power set of X has strictly larger cardinality than X. (Equivalently, there is no surjection from X to the power set of X.) In particular, the power set of an infinite set is uncountable.

9. A union of countably many countable sets is countable. More formally, if \Gamma is a countable set and for each \gamma\in\Gamma the set X_\gamma is countable, then the union \bigcup_{\gamma\in\Gamma}X_\gamma is countable.

10. In particular, a union of countably many finite sets is countable. If you are told to prove that a set is countable, then using this very simple principle usually leads to the shortest proof.

11. If n>m then there is no injection from the set \{1,2,\dots,n\} to the set \{1,2,\dots,m\} (and hence no surjection from the set \{1,2,\dots,m\} to the set \{1,2,\dots,n\}).

[This may look obvious, but it needs a proof. One way to do it is to use the well-ordering principle. Pick a counterexample with n minimal. Let \phi be an injection from \{1,2,\dots,n\} to \{1,2,\dots,m\}. If \phi(n)=j, then define \psi:\{1,\dots,n-1\}\to\{1,\dots,m-1\} by taking \psi(r)=\phi(r) if \phi(r)<j and \psi(r)=\phi(r)-1 if \phi(r)>j. This is an injection, which contradicts the minimality of n.]

Here are a couple of examples of how to do exercises that involve countability.

1. Prove that if Y is countable and f:X\to Y is an injection, then X is countable.

Solution. Since Y is countable, there is an injection g:Y\to\mathbb{N}. A composition of injections is an injection, so g\circ f is an injection from X to \mathbb{N}. Therefore, X is countable. \square

Note how short and clean the above proof is. Note also that what I did not do was say anything about “putting the elements of Y in a list”.

2. Let X be an uncountable set and let f be an injection from X to another set Y. Prove that Y is uncountable.

Solution. Since uncountability is defined negatively, it will be no surprise that we prove this result by looking at the contrapositive. If Y is countable, then by the previous exercise X is countable, contradicting our hypothesis. So Y is uncountable. \square

3. Prove that the set of all irrational numbers is uncountable.

Solution 1. There are various ways of doing this. The easiest argument starts from the thought that the reals form a huge set, and to get the irrationals we take away just the rationals, which form a small set. Therefore, the irrationals must form a huge set.

To turn that into a proper proof, we once again prove the contrapositive — for the same reason as we did when solving question 2. If the set of all irrationals is countable, then the reals are the union of two countable sets. Hence, by fact 9 above, the reals are countable. But that contradicts fact 7. \square

Solution 2. It is tempting to try to use the solution to 2 above. That is, we’d like to find a set that we know is uncountable, and define an injection from that set to the irrationals. The most obvious uncountable set is the set of reals. Can we inject those to the set of irrationals? Hmm, it seems hard, since nothing that’s even slightly continuous has any hope of working. Are there any “less continuous” uncountable sets that we could use? Yes: we could take the set of all 01 sequences. So now we’d like a way of associating an irrational with each 01 sequence. This is fun to do, so here’s a spoiler alert. I’ll leave some space, then I’ll give a solution in just one paragraph, then I’ll leave some more space, and then I’ll present a third solution.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Bearing in mind that all rational numbers have repeating decimal expansions, we just need some way of associating a non-repeating sequence with each 01 sequence. This can be done in many natural ways, of which one is this. To each sequence associate a decimal between 0 and 1 that is 0 in the nth decimal place whenever n is not a square, and is either 1 or 2 in the square places according to whether the 01 sequence is 0 or 1. For example, if the 01 sequence begins 00101, then the decimal will begin 0.10010000200000010000000020… \square
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Solution 3. This is just for people who know a little about continued fractions. If you haven’t, then don’t worry about it — though if you read the beginning of the Wikipedia article on the subject then that will be more than enough to understand what follows.

Continued fractions give a very beautiful bijection between the set of all positive irrational numbers and the set of all infinite sequences of natural numbers. Given a positive irrational number, you just take the terms of its continued-fraction expansion, and given an infinite sequence, you just take the number that has those terms, which must be irrational since all rational numbers have terminating continued-fraction expansions. It is easy to prove that the set of all infinite sequences of natural numbers is uncountable, so we’re done. \square


Sometimes one is asked to prove that a set X is uncountable when you’re not told what X is, but just that it has certain properties. This is slightly harder to deal with. I’m not going to work through an example, because I don’t want to spoil what may be a nice examples sheet question from next term. However, here is a technique that can sometimes work very nicely. You define, using information about X, a function \phi that takes finite sequences of 0s and 1s to points in X, and you do it in such a way that for any infinite sequence, the images of its initial segments form a sequence that you prove converges to something in X. (For instance, if the infinite sequence starts 110101… then the sequence of points in X starts \phi(1),\phi(11),\phi(110),\phi(1101),\phi(11010),\phi(110101),....) You also do the construction in a way that ensures that no two limits are the same.

About these ads

11 Responses to “A short post on countability and uncountability”

  1. Tom Leinster Says:

    Here’s an annoying little comment: fact 5 isn’t quite true as it stands, because of the possibility that X is empty and Y is not. Then there is an injection from X to Y, but no surjection from Y to X.

    Thanks — corrected now.

    It’s maybe also worth noting that (ii) => (i) is closely related to the axiom of choice. The axiom of choice states that every surjection has a section (right inverse). Any section of any map is injective, so the axiom of choice immediately tells you that (ii) => (i).

    I think it’s better for students to meet the axiom of choice first in this simple setting. Often it’s first introduced in a more advanced context, with an unnecessary amount of mystery attached.

  2. Greg Martin Says:

    A pedantic comment regarding your proof for Example 2: to me your proof reads like a proof by contradiction, rather than a proof of the contrapositive. The two are, of course, very closely related and especially hard to distinguish in such a short proof; here I’m swayed by the particular words you used, “contradicting our hypothesis”.

    Let XU and YU be the statements “X is uncountable” and “Y is uncountable”, and let I be the statement “there exists an injection f from X to Y”. Then the statement as written is “if XU and I, then YU”. The literal contrapositive is certainly “if not YU, then (not XU) or (not I)”; but we experienced mathematicians would probably also call either “if XU and not YU, then not I” or “if I and not YU, then not XU” a contrapositive of the original statement.

    It is this latter formulation that we want to use here; personally I prefer (with this level of audience) to formulate the contrapositive explicitly so that my proof is easily seen to be a proof of the new explicit statement. Even though your proof never uses the hypothesis XU, it reads (as currently worded) a little bit like the proof by contradiction “if XU and I and not YU, then False”. I like to discourage my students from these types of proofs by contradiction where one hypothesis is never used; I think it leads to greater clarity of thought to explicitly identify the form of the contrapositive that’s being used.

  3. plm Says:

    I take the opportunity to point out a great piece of knowledge that many (mathematicians) would appreciate I think:

    http://en.wikipedia.org/wiki/Observable_universe

    (with a section on matter content)

    So at the beginning of your article you probably meant “observable universe” rather than “universe”.

    Current orthodoxy in cosmology seems to be that the universe is spatially infinite (has points at arbitrarily large spatial distances), with a positive homogeneous (on large-scale) matter density. Then there are as many atoms as natural numbers in the universe.
    But please anyone correct me if I am mistaken, this is a tricky topic to learn.

  4. Kevin O'Bryant Says:

    There are set theoretic issues buried here that aren’t widely appreciated. The definition of “X is countable” not only uses the set X, but also the malleable notion of “function”. To come head-to-head with this, find the error in the statement: “there are countable models of ZFC, and (a model of) the reals sits inside that model, and so the reals are countable.”

    Most mathematicians fix ZFC, and also fix a model of it, and don’t concern themselves with whether they are doing math or metamath or metametamath, and don’t even acknowledge issues like whether Grothendieck universes are consistent with ZFC. For those, “countable” is a property a set may or may not have. But there is a substantial that like to vary their set theory and/or their model of it, and for these “countable” expresses an interplay between the set theory, the model, and the specific set.

    • Tom Leinster Says:

      Kevin, without disagreeing with your substantive point, I wanted to pick up on this:

      Most mathematicians fix ZFC

      Surely most mathematicians ignore ZFC (and all other axiomatizations of set theory).

      There’s an implicitly agreed collection of “naive” rules about how sets can be manipulated, and this forms a kind of fixed framework for almost all non-set-theorists. But that collection of rules is definitely not ZFC. It’s probably more like what appears in the first year course that Tim is writing about.

    • plm Says:

      I rather wonder about the “fix a model of it” part.

      Textbooks usually develop their material using the axiom of choice (e.g. for the existence of basis of vector spaces, of algebraic closure of fields, etc.). In this sense mathematicians’ naive rules amount to assuming ZFC (and also first-order logic as opposed to say type theory, although there are interesting nuances to argue between both kinds of assumption).

      But what particular model is necessary or used, explicitly or implicitly?

  5. Pete L. Clark Says:

    I hope it is okay to post such a comment…

    A few years ago I wrote some notes on elementary set theory. They come in three parts. The first part treats finite, countable and uncountable sets in a quite naive way (i.e., set-theoretically serious people will notice that some of the results presented require or are even equivalent to the Axiom of Choice, whereas AC is not even mentioned until the next set of notes. This is a deliberate expository choice):

    http://math.uga.edu/~pete/settheorypart1.pdf

    In comparison to Prof. Gowers’s notes, the first thing to say is that mine are much longer. Other than that they seem broadly similar (how dramatically different could two treatments of this topic be?). Perhaps my notes are a bit more “conceptual” — i.e., I spend some time trying to explain how one should think about infinite sets as mathematical objects — whereas his are more “practical”, i.e., he has more concrete advice on how to prove things about infinite sets.

    Any feedback on these notes would be warmly received. They have not been used for any very official purpose, but I have referred students to them, for instance, so improvements would certainly be beneficial.

  6. dasuxullebt Says:

    It may not fit perfectly, but as you are discussing misconceptions on countability, a somewhat similar concept which is often confused with countability is enumerability, aka semi-decidability. Both concepts have similar meanings and some proof-techniques (like diagonalization) are common, but the class of countable sets is strictly greater than the class of enumerable sets.

  7. animateholic Says:

    There are various ways of doing this. The easiest argument starts from the thought that the reals form a huge set,

    Huge set is infinte set ??

  8. Pensierini base su matematiche avanzate (e web culturale) | agora-vox.bluhost.info Says:

    [...] molti materiali anche introduttivi (per chi fa seriamente matematica, è ovvio; lo stesso Gowers ammette però che il sito non è [...]

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 )

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


Follow

Get every new post delivered to your Inbox.

Join 1,571 other followers

%d bloggers like this: