A good way of proving that a set is countable

Prerequisites

The definition of a countable set, function-related notions such as injections and surjections.

Quick description

If you can find a function from $A$ to $\mathbb{N}$ such that every $n$ has finitely many preimages, then $A$ is countable.

General discussion

Here is a quick informal account of a standard proof that the set $\mathbb{N}\times\mathbb{N}$ is countable: we can list its elements in the order $(1,1)$ , $(2,1)$ , $(1,2)$ , $(3,1)$ , $(2,2)$ , $(1,3)$ , $(4,1)$ , and so on. (This is informal because I have talked about "lists" and have not actually defined how the sequence continues.) We can view this proof geometrically as follows: in order to count through the set $\mathbb{N}\times\mathbb{N}$ , which forms an infinite grid in the plane, we note that each downward-sloping diagonal (that is, a set of pairs of positive integers with constant sum) is finite, and then we count through each of these sets in turn.

Here, we are making use of the very simple principle that a countable union of finite sets is countable. To put this more formally, if $A$ is a set that can be written as a union $\bigcup_{n=1}^\infty A_n$ for some collection $A_1,A_2,\dots$ of finite sets, then $A$ is countable.

This is very easy to see informally: one just counts through each $A_n$ in turn (leaving out elements that have already been counted). It is not important for this article, but for completeness let us briefly see how we might prove it more formally. We could write each set $A_n$ as $\{a_{n1},\dots,a_{nk_n}\}$ , where $k_n$ is the size of $A_n$ . And then we could define an ordering on all pairs $(n,m)$ with $m\leq k_n$ by taking $(n,m)<(r,s)$ if and only if either (i) $n<r$ or (ii) $n=r$ and $m<s$ . And then we would define a function $A\rightarrow\mathbb{N}$ by the following procedure. We would repeatedly choose the element $a_{ij}$ with minimal index $(i,j)$ for which $f(a_{ij})$ was not yet defined, and we would define it to be the minimal integer that was not yet assigned as a value of $f$ . It is not hard to check that one ends up assigning a value to all elements of $A$ and we never assign the same value twice. Thus, $f$ is an injection and $A$ is countable.

In particular, a set $A$ is countable if there is a function $A\rightarrow\mathbb{N}$ such that every $n\in\mathbb{N}$ has finitely many preimages.^♦ (This means that for every $n\in\mathbb{N}$ there are only finitely many $a\in A$ with $f(a)=n$ .) This follows because we can define $A_n$ to be $f(a)=n\}$ , and then we have expressed $A$ as a countable union of finite sets.

This observation is not particularly interesting as a theoretical statement, but as a tool for giving quick proofs of countability it is extremely useful. Here are some examples.

Example 1

To prove that the rational numbers form a countable set, define a function $f$ that takes each rational number $p/q$ (which we assume to be written in its lowest terms, with $q>0$ ) to the positive integer $|p|+|q|$ . The number of preimages of $n$ is certainly no more than $(2n+1)^2$ , so we are done.

As another aside, it was a bit irritating to have to worry about the lowest terms there. For some reason many mathematicians are afraid of multifunctions (that is, things that are like functions except that each element in the domain can map to several elements in the range) and sweep them under the carpet. But for the rationals it is convenient to have them. We define a multifunction $f$ from $\mathbb{Q}$ to $\mathbb{N}$ by mapping $p/q$ to $|p|+|q|$ . This looks as though it isn't well-defined, which as a function it isn't, but if we think of it as a multifunction, then for instance the rational number $2/3$ maps to all possible values of $|p|+|q|$ for which $3p=2q$ . (If you really don't like this, then you could rephrase it in terms of bipartite graphs or something like that.) Each positive integer $n$ still has only finitely many preimages (defined to be any rational number that has at least one image equal to $n$ ), and this proves the result since any multifunction with that property can clearly be restricted to a function with that property (just select, for each element of the domain, one of its images).^♦

Example 2

To prove that the set of all finite subsets of $\mathbb{N}$ is countable, how might we find a suitable function? An obvious function to consider is $f(A)=|A|$ , but this doesn't work since there are infinitely many sets of any given size. (OK, apart from size zero.) But there's another very simple function that works: $f(A)=\max A$ . Clearly, the number of sets with maximal element $n$ is finite (in fact, it is $2^{n-1}$ ), so we are done.

Example 3

To prove that the set of all polynomials with integer coefficients is countable is a similar exercise, but slightly more complicated. It is tempting to consider the sum of the absolute values of the coefficients, but then we notice that the polynomials $1, x, x^2, x^3, \dots$ all have coefficients with absolute values adding up to 1. So we need to restrict the degree somehow. But that is very easy indeed: given a polynomial $P$ we define $f(P)$ to be the degree of $P$ plus the sum of the absolute values of the coefficients of $P$ .

Example 4

To prove that the set of all algebraic numbers is countable, it helps to use the multifunction idea. Then we map each algebraic number $\theta$ to every polynomial with integer coefficients that has $\theta$ as a root, and compose that with the function defined in Example 3. It is easy to check (using the fact that every polynomial has finitely many roots) that for every integer $n$ there are at most finitely many algebraic numbers that map to $n$ , and we are done.

General discussion

A tool that is more often presented in treatments of countability is the fact that a countable union of countable sets is countable. That translates into the more general principle that if you can find a function $X\rightarrow\N$ such that each $n$ has at most countably many preimages, then $X$ is countable. The point of this article is that it is almost always possible to use a function with only finitely many preimages for each $n$ , and that this often leads to short, easy proofs.

120152 reads
Subscribe

Comments

Inline comments

The following comments were made inline in the article. You can click on 'view commented text' to see precisely where they were made.

Doesn't need to be finitely many.

Tue, 21/04/2009 - 05:27 — Beetle B.

Actually, a weaker requirement is that the preimages be countable (i.e. they could be countably infinite). This works because as mentioned earlier in the article, the countable union of countable sets is countable.

I started editing the article, but couldn't phrase it well without making it sound recursive. We're trying to show that A is countable, and I'm saying the pre-image of every n is countable. Strictly speaking, I'm not being recursive or circular, but I'd like someone to write it in a way that won't confuse any one.

Although that's true, I'm not

Tue, 21/04/2009 - 07:57 — gowers

Although that's true, I'm not completely in favour of mentioning it, because the point of this particular article is to encourage the reader to use the result with "finite". For example, to prove that $\N^k$ is countable, I prefer defining $f(x_1,\dots,x_k)=\max_i|x_i|$ to defining $g(x_1,\dots,x_k)=x_k$ and using induction, even though both proofs are correct.

True, but I just feel that

Tue, 21/04/2009 - 17:54 — Beetle B.

True, but I just feel that fact should be mentioned somewhere in the article - if only as a sidenote.

I'm merely worried someone relatively new to the issue of countability may think finiteness is *required*. Perhaps a note in parentheses at the end of the paragraph stating that countably infinite inverses work as well, but it's usually more appropriate/easier to find a finite case?

OK, I've now added a

Tue, 21/04/2009 - 23:31 — gowers

OK, I've now added a paragraph making this point but without compromising the theme of the article.

Thanks!

Wed, 22/04/2009 - 04:27 — Beetle B.

Thanks!

Inline comments

The following comments were made inline in the article. You can click on 'view commented text' to see precisely where they were made.

I like how you snuck in the

Fri, 17/07/2009 - 21:39 — Michael Burge (not verified)

I like how you snuck in the Axiom of Choice here, and hid it under the rug since its use is "clear".

Apparent use of axiom of choice

Sun, 19/07/2009 - 04:43 — emerton

I don't think one really needs to apply the axiom of choice in this context: Since the multifunction is taking values in positive integers, we could just define the corresponding function by taking its value to be the least member of the set of values of the multifunciton. (This process will then, I guess, secretly take us back to the original function construction, where we write each rational in lowest terms — but we don't need to pay attention to this if we don't want to.)

Post new comment

(Note: commenting is not possible on this snapshot.)