Proposition A.1.1.
The set \(\N\cup\{0\}\) is countable.
Section A.1 Cardinality
For sets \(A,B\text{,}\) \(|A|=|B|\) means there is a bijection between them. In that case, we say that \(A\) and \(B\) have the same cardinality. We write \(|A| \le |B|\) if there is an injection \(A \to B\text{.}\) A set \(A\) is countably infinite if \(|A|=|\N|\text{.}\) A set is countable if it is either finite or countably infinite.
We begin with standard countable models that will be reused in later proofs.
Proof.
The map \(f:\N\to \N\cup\{0\}\text{,}\) \(f(n)=n-1\text{,}\) is bijective, with inverse \(g(m)=m+1\text{.}\) Hence \(|\N\cup\{0\}|=|\N|\text{.}\)
Proposition A.1.2.
The set \(\N\times\{0,1\}\) is countable.
Proof.
Define \(F:\N\times\{0,1\}\to\N\) by \(F(n,0)=2n\) and \(F(n,1)=2n-1\text{.}\) This is bijective, so \(|\N\times\{0,1\}|=|\N|\text{.}\)
Proposition A.1.3.
The set \(\N^2\) is countable.
Proof.
For each \(s\in\N\text{,}\) the diagonal \(D_s=\{(m,n)\in\N^2:m+n=s\}\) is finite. Also \(\N^2=\bigcup_{s\ge2}D_s\text{.}\) Enumerating each diagonal in increasing order of \(s\) gives an enumeration of \(\N^2\text{,}\) so \(\N^2\) is countable.
The next theorem is the main comparison tool.
Theorem A.1.4. Cantor-Bernstein-Schroder.
If \(|A|\le |B|\) and \(|B|\le |A|\text{,}\) then \(|A|=|B|\text{.}\)
Proposition A.1.5.
A countable union of countable sets is countable.
Proof.
Let \(A_1,A_2,\ldots\) be a countable family (indexed by \(\N\)) of countable sets. For \(a\in\bigcup_{j\in\N}A_j\text{,}\) let \(j(a)\) be the least index with \(a\in A_{j(a)}\text{.}\) Then \(a\mapsto (a,j(a))\) is an injection into \(\bigcup_j(A_j\times\{j\})\text{.}\) For each \(j\text{,}\) choose an injection \(f_j:A_j\to\N\text{.}\) Then \((a,j)\mapsto (f_j(a),j)\) injects \(\bigcup_j(A_j\times\{j\})\) into \(\N^2\text{.}\) Since \(\N^2\) is countable, the union is countable.
Proposition A.1.6.
The set \(\Q\) is countable (hence \(\Z\) is countable).
Proof.
The map \(n\mapsto n/1\) gives an injection \(\N\to\Q\text{,}\) so \(|\N|\le |\Q|\text{.}\) For the reverse inequality, map \(r\in\Q\) to \((m,n)\in\Z\times\N\) where \(r=m/n\) in lowest terms and \(n>0\text{.}\) This is injective, and \(\Z\times\N\) is countable (as a countable union of countable sets), so \(|\Q|\le |\N|\text{.}\) By Theorem A.1.4, \(|\Q|=|\N|\text{.}\)
Let \(X\) be a set and let \(A\subseteq X\text{.}\) The indicator function of \(A\) in \(X\text{,}\) denoted \(1_A^X\) (or \(1_A\) when \(X\) is understood), is the map \(1_A^X:X\to\{0,1\}\) defined by \(1_A^X(x)=
\begin{cases}
1,&\text{if }x\in A,\\ 0,&\text{if }x\notin A.
\end{cases}\)
For any set \(X\text{,}\) indicator functions give a bijection \(\mathcal{P}(X)\cong 2^X\text{,}\) where \(2^X\) is the set of maps \(X\to\{0,1\}\text{.}\)
Theorem A.1.7. Cantor.
For every set \(X\text{,}\) \(|X| < |2^X|\text{.}\)
Proof.
The map \(x\mapsto 1_{\{x\}}\) is an injection \(X\to2^X\text{.}\) To show there is no surjection \(X\to2^X\text{,}\) suppose \(\Phi:X\to2^X\) is surjective. Define \(d:X\to\{0,1\}\) by \(d(x)=1-\Phi(x)(x)\text{.}\) Since \(\Phi\) is surjective, \(d=\Phi(a)\) for some \(a\in X\text{.}\) Evaluating at \(a\) gives \(\Phi(a)(a)=1-\Phi(a)(a)\text{,}\) impossible. Hence \(|X|<|2^X|\text{.}\)
Corollary A.1.8.
The real line \(\R\) is uncountable.
Proof.
By Theorem A.1.7, \(|\N|<|2^{\N}|\text{.}\) Define \(\Psi:2^{\N}\to\R\) by \(\Psi((a_k)_{k\ge1})=\sum_{k\ge1}a_k/10^k\text{.}\) If \(a\ne
b\text{,}\) let \(n\) be the first index with \(a_n\ne b_n\text{.}\) Then \(|\Psi(a)-\Psi(b)|\ge 10^{-n}(1-1/9)>0\text{,}\) so \(\Psi\) is injective. Therefore \(|2^{\N}|\le |\R|\text{,}\) and thus \(\R\) cannot be countable.
Proposition A.1.9.
The irrational numbers \(\R\setminus\Q\) are uncountable.
Proof.
If \(\R\setminus\Q\) were countable, then \(\R=(\R\setminus\Q)\cup\Q\) would be a union of two countable sets, hence countable, contradicting Corollary A.1.8.
