11.1 Countable
We first notice that there are some infinite sets where we can “count” the elements.
In essence a countable set is an infinite set where we can enumerate the elements, \(x_1, x_2, x_3, \dots\) where \(x_i=f(i)\) for \(i\in\mathbb{Z}_+\).
Note that some texts in literature say that a set if countable if it is finite or if there exists a bijective function \(f:\mathbb{Z}_+\to X\), and when there exists a bijective function \(f:\mathbb{Z}_+\to X\), these texts say \(X\) is countably infinite. However, in this course, a countable set must be infinite (it makes some theorems easier to state).
Combining the definition of countability with the definition of cardinality, we have that \(X\) is a countable set if and only if \(|X|=|\mathbb{Z}_+|\).We show that the set of positive even integers is countable.
Let \(2\mathbb{Z}_+=\{2x: x\in\mathbb{Z}_+ \}\) and define \(f:\mathbb{Z}_+\to 2\mathbb{Z}_+\) by \(f(x)=2x\), for all \(x\in\mathbb{Z}_+\). To see that \(f\) is injective, suppose that \(x,y\in\mathbb{Z}_+\) such that \(f(x)=f(y)\). Then \(2x=2y\), so \(x=y\), showing that \(f\) is injective.
To see that \(f\) is surjective, take \(a\in \mathbb{Z}_+\). Then \(a=2x\), for some \(x\in\mathbb{Z}_+\), and hence \(a=2x=f(x)\). Hence, \(f\) is surjective. This shows that \(f\) is bijective. Therefore, \(A\) is countable.
Similarly, the set of odd positive integers, \(\{2x-1: x\in\mathbb{Z}_+\}\), can be shown to be countable.Let \(X\) and \(Y\) be two sets such that \(|X|=|Y|\). If \(X\) is countable, then \(Y\) is countable.
Let \(|X|=|Y|\) and suppose that \(X\) is countable. Then \(|X|=|\mathbb{Z}_+|\) so \(|Y|=|X|=|\mathbb{Z}_+|\). Hence \(|Y|\) is countable.
□
Every infinite set contains a countable subset.
Non-examinable. It is beyond the scope of this course.
□
While the statement seems intuitive, proving this result is outside the scope of this course. It involves using the Axiom of Choice, which says given a countable number of non-empty sets, we can choose one element from each set.
Interestingly, some research is done into how many theorems are true independent of the Axiom of Choice (and therefore would be true if we did not assume the Axiom of Choice to be true.)Let \(X\) be a subset of \(\mathbb{Z}_+\). Then \(X\) is either finite or countable.
If \(X\) is finite then we are done. So suppose \(X\) is infinite. We have an injective map \(g:X\to \mathbb{Z}_+\) given by \(g(x)=x\), so \(|X|\le |\mathbb{Z}_+|\). On the other hand, we know that \(X\) contains a countable subset \(A\). Hence, there exists a bijective map \(h:\mathbb{Z}_+\to A\). Now, define \(f:\mathbb{Z}_+\to X\) by \(f(n)=h(n)\), for all \(n\in\mathbb{Z}_+\). Then \(f\) is an injective map from \(\mathbb{Z}_+\) into \(X\). Hence, \(|\mathbb{Z}_+|\le|X|\). So by Theorem 7.8, we have that \(|X|=|\mathbb{Z}_+|\). It follows that \(X\) is countable.
□
Suppose \(X\) is an infinite set. Then \(X\) is countable if and only if there exists an injective \(f:X\to \mathbb{Z}_+\).
We prove both directions separately.
(\(\Rightarrow\)) First, suppose that \(X\) is countable. Then there exists a bijection \(f:X\to \mathbb{Z}_+\). Since \(f\) is bijective, it is injective.
(\(\Leftarrow\)) Second, suppose there exists such an injective \(f:X\to \mathbb{Z}_+\). Then \(|X|=|f[X]|\), and \(f[X] \subseteq \mathbb{Z}_+\). Since \(X\) is not finite and \(|X|=|f[X]|\), \(f[X]\) is not finite. Hence, \(f[X]\) is countable. Therefore, we must have that \(X\) is countable.
Summarising, \(X\) is countable if and only if there exists an injective \(f:X\to \mathbb{Z}_+\).□
Let \(X\) be a set and let \(A,B\subseteq X\). Suppose that \(A\) is a countable set and that \(B\) is a nonempty finite set disjoint from \(A\) (\(A\cap B=\emptyset\)). Then \(A\cup B\) is countable.
Since \(A\) is countable, there exists an injective map \(f:A\to\mathbb{Z}_+\). Since \(B\) is finite we have that \(B=\{b_1,\ldots,b_m\}\), for some \(m\in\mathbb{Z}_+\), where \(|B|=m\). Now, define \(g:A\cup B\to\mathbb{Z}_+\) by \[g(x)=\begin{cases} i,&\text{if $x=b_i$,}\\ f(x)+m,&\text{if $x\in A$}.\end{cases}\] We claim that \(g\) is injective. To see this, take \(x,y\in A\cup B\) such that \(x\not=y\). If \(x,y\in B\), then \(x=b_i\) and \(y=b_j\) for some \(i,j\in\mathbb{Z}_+\) such that \(i\le m\), \(j\le m\) with \(i\not=j\). Hence, we have that \(g(x)=i\not=j=g(y)\). If \(x\in B\) and \(y\in A\), then \(x=b_i\) for some \(i\in\mathbb{Z}_+\) with \(i\le m\). Hence, we have that \(g(x)=i<m+1\le g(y)\). If \(x,y\in A\), then \(f(x)\not=f(y)\) since \(x\not=y\) and \(f\) is injective. So \(g(x)=f(x)+m+1\not=f(y)+m+1=g(y)\). It follows that \(g\) is injective.
Since \(A\subseteq A\cup B\) and \(A\) is infinite, \(A\cup B\) is infinite. Since \(g:A\cup B\to\mathbb{Z}_+\) is injective and \(A\cup B\) is infinite, \(A\cup B\) is countable.□
The above proof was popularised by David Hilbert (Prussian mathematician, 1862-1943) with what is now called the “Hilbert hotel”, where there is always room for another guest:
The Hilbert hotel has countably many rooms,
labelled \(1,2,3,\ldots\) (so for each number in \(\mathbb{Z}_+\), there is a room with that number). One night, the hotel is full,
and another potential guest arrives at the hotel looking for a room. The manager says, no problem! Then the manager announces
to the guests that every guest is to move to the next room (so the guests in room \(n\) move to room \(n+1\)). Thus all the guests
still have rooms, and room 1 has been made available to the new arrival.
We have that \(\mathbb{Z}_+\times \mathbb{Z}_+\) is countable.
First we note that \(\mathbb{Z}_+\times \mathbb{Z}_+\) is infinite as \(\mathbb{Z}_+\times \{1\}=\{(n,1): n \in \mathbb{Z}_+\} \subseteq \mathbb{Z}_+\times \mathbb{Z}_+\), and \(\mathbb{Z}_+\times \{1\}\) is countable (using the bijection \(f:\mathbb{Z}_+\to \mathbb{Z}_+\times \{1\}\) defined by \(f(n)=(n,1)\)).
We define \(f:\mathbb{Z}_+\times \mathbb{Z}_+ \to \mathbb{Z}_+\) by \(f((a,b)) = 2^a3^b \in \mathbb{Z}_+\). Suppose \(f((a_1,b_1))=f((a_2,b_2))\), then \(2^{a_1}3^{b_1}=2^{a_2}3^{b_2}=n\). Note that \(n\geq 2\) (since \(a_1\geq 1\)), so by the Fundamental Theorem of Arithmetic, \(n\) is expressed uniquely as a product of primes. That is \(a_1=a_2\) and \(b_1=b_2\), so \((a_1,b_1)=(a_2,b_2)\). Hence \(f\) is injective and \(\mathbb{Z}_+\times \mathbb{Z}_+\) is infinite, so \(\mathbb{Z}_+\times \mathbb{Z}_+\) is countable.□
There are many proofs of this theorem. Above we presented one that uses the Fundamental Theorem of Arithmetic. Below we outline the idea of another proof that doesn’t use the Fundamental Theorem of Arithmetic. We leave the rigorous details as an exercise.
We arrange the elements of \(\mathbb{Z}_+\times\mathbb{Z}_+\) in a grid: \[\begin{array}{ccccc} (1,1)&(1,2)&(1,3)&(1,4)&\cdots\\ (2,1)&(2,2)&(2,3)&(2,4)&\cdots\\ (3,1)&(3,2)&(3,3)&(3,4)&\cdots\\ (4,1)&(4,2)&(4,3)&(4,4)&\cdots\\ \vdots&\vdots&\vdots&\vdots \end{array}\] We order the elements of this grid along the cross-diagonals: \[(1,1);\ (1,2),\ (2,1);\ (1,3),\ (2,2),\ (3,1); \ldots\] So we want to construct a function \(f:\mathbb{Z}_+\times \mathbb{Z}_+\to \mathbb{Z}_+\) such that \(f((1,1))=1, f((1,2))=2, f((2,1))=3, \dots\). We leave it an exercise to find a general formula for \(f((n,m))\) and show that \(f\) is injective.
The following lemma lists the basic properties of countable sets.
Suppose that \(X\) is a countable set.
if \(A\subseteq X\), then \(A\) is either finite or countable.
if \(A\subseteq X\) and \(A\) is finite, then \(X\setminus A\) is countable.
there exists \(B\subseteq X\) such that \(B\) and \(X\setminus B\) are countable.
if \(f:C\to X\) is injective, then \(C\) is either a finite set or a countable set.
Exercise.
□
Using the above lemma, and the fact that \(\mathbb{Z}_+\times\mathbb{Z}_+\) is countable, we can deduce:
We have that \(\mathbb{Q}_+\), \(\mathbb{Q}\) and \(\mathbb{Z}\) are all countable. In particular \(|\mathbb{Z}_+|=|\mathbb{Z}|=|\mathbb{Q}|\).
Let \(X\) and \(Y\) be countable sets. Then
\(X\times Y\) is countable.
if \(X\cap Y=\emptyset\), then \(X\cup Y\) is countable.
Exercise.
□
Note that by repeated application of the above lemma, we can see that for countable \(X\) and for any \(n\in\mathbb{Z}_+\), we have \(X^n = X\times X \times X \times \dots \times X\) (the Cartesian product of \(n\) copies of \(X\)) is countable.
Let \(\{A_n: n\in\mathbb{Z}_+ \}\) be a (countable) collection of countable sets that are pairwise disjoint (i.e. \(A_i\cap A_j = \emptyset\) for all \(i\neq j\)). Then \(\bigcup\limits_{n\in\mathbb{Z}_+}A_n\) is countable.
First, note that since \(A_1\) is countable, we have that it is infinite. Since \(A_1\subseteq\bigcup\limits_{n\in\mathbb{Z}_+}A_n\), we know that \(\bigcup\limits_{n\in\mathbb{Z}_+}A_n\) is also infinite. We now construct an injective \(g:\bigcup\limits_{n\in\mathbb{Z}_+}A_n\to\mathbb{Z}_+\times\mathbb{Z}_+\).
For each \(n\in\mathbb{Z}_+\), enumerate the elements of \(A_n\) as \(a_{n,1},a_{n,2},a_{n,3},\ldots\). Now, define \(g:\bigcup\limits_{n=1}^{\infty}A_n\to\mathbb{Z}_+\times\mathbb{Z}_+\) by \[g(a_{m,k})=(m,k),\] for all \(a_{m,k}\in\bigcup\limits_{n=1}^{\infty}A_n\). To see that \(g\) is injective, suppose that \(g(a_{m,k})=g(a_{s,t})\) for some \(m,k,s,t\in\mathbb{Z}_+\). Then \((m,k)=(s,t)\), so \(m=s\), \(k=t\), and hence \(a_{m,k}=a_{s,t}\). It follows that \(g\) is injective. Hence, we have an injective function from \(\bigcup\limits_{n=1}^{\infty} A_n\) into a countable set. Since \(\bigcup\limits_{n=1}^{\infty}A_n\) is infinite, it follows that \(\bigcup\limits_{n=1}^{\infty}A_n\) is countable.□