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