Hunter Liu's Website

2. Countability

≪ 1. Some Practise with Sequences | Table of Contents | 3. Comments on Homework 1 ≫

Infinite sets come up quite frequently throughout mathematics. Something we must grapple with is the notion of “different infinities”. To qualify this statement, recall that for any set \(A\), its power set (or the set of all subsets of \(A\)) \(\mathcal{P}(A)\) is strictly larger than \(A\). More precisely, there does not exist a surjective function from \(A\) to \(\mathcal{P}(A)\). When \(A\) is an infinite set, so too is its power set, but it’s somehow a “larger infinite”.

The smallest and thereby the least aggressive infinite is the countable infinite. Recall this definition:

Definition 1.

A set \(A\) is countable if \(A\) is a finite set or there exists a bijection \(f:\mathbb{N}\to A\).

For me, this is the definition I prefer; other authors may use “countable” to only mean the countably infinite sets. Often, however, one can determine how specific “countable” is from context.

Such a bijection as in the definition is sometimes called an enumeration, and it’s the same as finding an exhaustive sequence of elements of \(A\). Indeed, given such an \(f\), one may form the sequence \(f(1), f(2), f(3), \ldots\), and this will eventually “count through” each of the elements of \(A\) exactly once.

Exercise 2.

Show that the following statements are equivalent:

  1. \(A\) is a countable set.
  2. There exists an injective function \(f:A\to \mathbb{N}\).
  3. There exists a surjective function \(g:\mathbb{N}\to A\).

In other words, show that if any one of the three above conditions are true, then the other two are necessarily true as well.

Countably infinite sets come up frequently in math because lots of arguments work well in a finite setting, but extend to infinite things very poorly. For instance, you may know that a vector space \(V\) is isomorphic to its dual when \(V\) is finite dimensional, but not necessarily when it’s infinite-dimensional. With countable sets, there’s sometimes a way to bridge these sorts of logical gaps!

We would thus very much care about being able to determine whether or not any given set is countable! To directly prove or disprove the countability of an infinite set \(A\), one has a few options:

Sometimes, actually producing these functions or constructions is nearly impossible. For proving countability, the following exercise (lifted from the homework) is extremely helpful:

Exercise 3.

Show that countable unions of countable sets are countable. In other words, show that if \(A_1,A_2, A_3, \ldots\) are countable sets, then \(\bigcup _{n=1}^{\infty} A_n\) is countable as well.

Show that finite products of countable sets are countable. That is, if \(A_1, \ldots, A_n\) are countable sets, then the Cartesian product \(A_1\times\cdots\times A_n\) is countable as well. Show that infinite products of even finite sets can be uncountable.

For this, it’s helpful to think about why \(\mathbb{N}^2\), the set of pairs of natural numbers, is also countable. The idea is to use a clever counting strategy. We will enumerate \(\mathbb{N}^2\) as follows: we’ll start with \((1, 1)\), then count \((1, 2), (2, 1)\), then \((1, 3)\), \((2, 2)\), and \((3, 1)\), and so on and so forth. Draw a picture and trace out the “path” that this takes. Make sure you understand why this shows countability! If this intuition makes sense to you, try formalising it yourself.

Here are some more practise exercises that might be helpful.

Exercise 4.

For this problem, an open interval is a set of the form \(\left\lbrace x\in \mathbb{R} : a < x < b \right\rbrace\) for some real numbers \(a\) and \(b\). Suppose \(S\) is a set of pairwise disjoint open intervals. Show that \(S\) is countable.

Hint
Try finding an injection from \(S\) into \(\mathbb{Q}\) — is there a way to uniquely identify the intervals in \(S\) with some rational number?
Solution

Every nonempty open inteval in \(\mathbb{R}\) contains a rational number. If \((a, b)\subseteq \mathbb{R}\), let \(\epsilon=b-a\) be the width of the interval, and pick \(N\) a very large integer such that \(\frac{1}{N} < \epsilon\). Then, consider the sequence \[\cdots, -\frac{2}{N}, -\frac{1}{N} , 0, \frac{1}{N} , \frac{2}{N} , \cdots\] Then \((a, b)\) must contain one of the above points! Otherwise, it must fit inside one of the “gaps” between adjacent multiples of \(\frac{1}{N} \), which contradicts its width being wider than \(\frac{1}{N}\).

For each \(I\in S\), pick a rational number in \(I\). No two intervals in \(S\) may contain the same rational, so this produces an injective map \(S\to \mathbb{Q}\); it follows that \(S\) is countable. \(\square\)

Exercise 5.

Let \(V\) be the set of all sequences of real numbers. We can make \(V\) a real vector space: you can add sequences term-by-term, and you can scale a sequence by a real number term-by-term as well. Let \(W\) be the subspace of sequences that only have finitely many nonzero terms.

Show that \(W\) has a countable (Hamel) basis. Does \(V\) have a countable basis?

Solution

Let \(v_n\) be the sequence of all zeroes except for a single one at the \(n\)-th term. This is a countable basis for \(W\); I hope this is clear.

It so turns out that \(V\) does not have a countable basis, and there are several different ways to prove this. Let \(\left\lbrace v_n \right\rbrace _{n=1}^{\infty}\) be any countable set of vectors in \(V\); we will construct a sequence that’s not in the linear span of the \(v_n\)’s.

First, pick \(\left(a_1,a_2\right)\) not in the linear span of \(\left(v _{1,1}, v _{1,2}\right)\). This is certainly possible. Inductively select \(a _{n+1}\) so that \(\left( a_1,\ldots, a _{n+1} \right)\) is not in the linear span of \(\left( v _{i,1},\ldots, v _{i, n+1} \right)\), where \(i\) ranges over \(1,\ldots, n\). In words, we are constructing the \(n+1\)-th term of a sequence in such a way that it remains linearly independent of the first \(n+1\) terms of \(v_1,\ldots, v_n\).

Let \(a\) be the sequence constructed above. \(a\) does not lie in the span of the \(v_n\)’s by contsruction (detailed proof left as an exercise!). It follows that \(V\) does not have a countable basis. \(\square\)

Alternative Solution

Another way to show that \(V\) does not have a countable basis is to construct an uncountable linearly independent set of vectors. This is possible but somewhat involved, and it hinges on finding an uncountable subset \(S\subseteq \mathcal{P}(\mathbb{N})\) such that every element of \(S\) is infinite, yet no two elements of \(S\) have an infinite intersection. Try constructing such sets yourself!

To each \(A\in S\), one may associate the indicator sequence \(\chi_A\), where the \(n\)-th term is zero if \(n\notin A\) and the \(n\)-th term is one otherwise. This collection of indicator sequences will be linearly independent if you construct \(A\) as above — linear combinations of the \(\chi_A\)’s can only zero out finitely many terms at a time!

Some Remarks

First, infinite-dimensional real vector spaces come up all over analysis, and of central importance is the notion of a Banach space. This is quite beyond the scope of this class, so don’t worry about that too much.

Second, and perhaps a bit more relevant to countability, is that \(V\) has uncountably many “directions” one can go in, in fact it has one for every subset of \(\mathbb{N}\). These “directions” may not be linearly independent, but somehow the condition of linear dependence is a countable condition: only finitely many vectors may be linearly dependent at once, and so we (very vaguely) have a “countable number of conditions to satisfy”. After dealing with these countably many exceptions in our uncountable set of “directions”, we should still be left with uncountably many linearly independent vectors.

Exercise 6.

A real number \(\alpha\) is called algebraic if \(p(\alpha)=0\) for some polynomial \(p\) with integer coefficients. Show that the set of all algebraic numbers is countable. As a consequence, show that there exist real numbers that are not algebraic.

Note: You may know that \(e\) and \(\pi\) are not algebraic, but this is quite a difficult thing to show. Such numbers are called transcendentals.

Hint
Try expressing the set of algebraic numbers as a countable union of countable sets.
Solution

Let \(A\) denote the set of algebraic numbers. Let \(A_d\) denote the set of algebraic numbers that are roots of integer polynomials of degree \(d\). We clearly have \(A=\bigcup _{d=1}^{\infty} A_d\), so it suffices to show that the \(A_d\)’s are all countable, for the countable union of countable sets is countable.

Let \(P_d\) denote the set of integer polynomials of degree exactly \(d\). There is a bijection \(P_d\to \left( \mathbb{Z}\setminus \left\lbrace 0 \right\rbrace \right)\times \mathbb{Z} ^{d}\) given by \(a_dx^d+\cdots+a_1x+a_0\mapsto \left( a_d,\ldots, a_0 \right)\). Both \(\mathbb{Z}\) and \(\mathbb{Z}\setminus \left\lbrace 0 \right\rbrace\) are countable, and the finite product of countable sets is countable. Thus \(P_d\) is countable.

Finally, if \(p\) is a polynomial, define \(R(p)\) to be the set of roots of \(p\). By the fundamental theorem of algebra \(R(p)\) is finite. We thus have that \(A_d=\bigcup _{p\in P_d}R(p)\), so \(A_d\) is a countable union of finite sets! It follows that \(A_d\) is countable, and we conclude that \(A\) is countable. \(\square\)

Exercise 7. (Challenging)

It is possible to draw an uncountably infinite number of non-intersecting line segments in the coordinate plane: you can place a vertical line segment with one endpoint at \((x, 0)\) as \(x\) ranges over the real numbers.

Is it possible to draw an uncountably infinite number of non-intersecting circles in the coordinate plane? What about figure 8s? What about Y-shapes?

Note: You do not have to draw perfect shapes. You can distort the figure 8s and the Y-shapes, and you can shrink or enlarge them as you wish. For instance, the letter “E” is a “topological Y-shape” — it has three “legs” branching out from a common point.