A good way of proving that a set is countable

a repository of mathematical know-how

A good way of proving that a set is countable

Title: *

Area of mathematics: *

A comma-separated list of areas of mathematics to which this article applies. Use ">" to tag in a subcategory. Example: Analysis > Harmonic analysis, Combinatorics

Keywords:

A comma-separated list of keywords associated with this article. Example: free group

Used in:

A comma-separated list of examples of where this technique is used. Example: Cauchy-Schwarz inequality

Parent articles:		Order

Body:

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

==== See also ====

[[A quick way of recognising countable sets|A quick way of recognising countable sets]]

[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 $f: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 $f:A\rightarrow\mathbb{N}$ such that every $n\in\mathbb{N}$ has finitely many preimages.<comment thread="180" /> (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 $\{a\in A: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]

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 <em>really </em>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).<comment thread="549" />

[EXAMPLE]

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]

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]

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

This is a stub

A stub is an article that is not sufficiently complete to be interesting.

Notifications

File attachments

Changes made to the attachments are not permanent until you save this post. The first "listed" file will be included in RSS feeds.

Attach new file:

Images are larger than 640x480 will be resized. The maximum upload size is 1 MB. Only files with the following extensions may be uploaded: jpg jpeg gif png svg.

Revision information

Log message:

An explanation of the additions or updates being made to help other authors understand your motivations.

A good way of proving that a set is countable

Recent articles

Active forum topics

Recent comments