Skip to main content

Section A.1 Cardinality

For sets \(A\) and \(B\text{,}\) the equality \(|A|=|B|\) means that there is a bijection between them. In this 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 two standard countable sets that will be useful 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{.}\)

Proof.
Define \(F:\N\times\{0,1\}\to\N\) by \(F(n,0)=2n\) and \(F(n,1)=2n-1\text{.}\) This map is bijective, so \(|\N\times\{0,1\}|=|\N|\text{.}\)
The next proposition shows that \(\N\) has the smallest infinite cardinality.

Proof.
If \(f:\N\to A\) is injective, then \(f(\N)\) is an infinite subset of \(A\text{,}\) so \(A\) is infinite. Conversely, suppose that \(A\) is infinite. Choose \(a_1\in A\text{,}\) and recursively choose \(a_{n+1}\in A\setminus\{a_1,\ldots,a_n\}\text{.}\) This is possible at every stage because \(A\) is not finite. The map \(n\mapsto a_n\) is an injection from \(\N\) to \(A\text{.}\)
Our main tool for comparing cardinalities is the following theorem.
Proofs of Theorem A.1.4 can be found in [11] and [12].

Proof.
Let \(A\) be an infinite subset of \(\N\text{.}\) The inclusion \(A\hookrightarrow\N\) is injective, so \(|A|\le|\N|\text{.}\) Since \(A\) is infinite, Proposition A.1.3 gives \(|\N|\le|A|\text{.}\) Therefore \(|\N|=|A|\) by Theorem A.1.4.
A direct proof of the preceding proposition that does not invoke Theorem A.1.4 is left as an exercise.

Proof.
(Item A.1.7:1 implies Item A.1.7:2.) If \(A\) is countably infinite, any bijection from \(A\) to \(\N\) is an injection. If \(A=\{a_1,\ldots,a_k\}\) is finite, the map \(a_j\mapsto j\) is injective.
(Item A.1.7:2 implies Item A.1.7:3.) Let \(i\colon A\to\N\) be injective, and choose \(a_0\in A\text{.}\) Define \(s:\N\to A\) by \(s(n)=i^{-1}(n)\) when \(n\in i(A)\) and by \(s(n)=a_0\) otherwise. Every element of \(A\) has the form \(i^{-1}(n)\) for some \(n\in i(A)\text{,}\) so \(s\) is surjective.
(Item A.1.7:3 implies Item A.1.7:1.) Suppose that \(s\colon\N\to A\) is surjective. Assign to each \(a\in A\) its least preimage: \(i(a)=\min\{n\in\N:s(n)=a\}\text{.}\) The resulting map \(i:A\to\N\) is injective and hence gives a bijection from \(A\) to \(i(A)\text{.}\) If \(i(A)\) is finite, then \(A\) is finite. If \(i(A)\) is infinite, then Proposition A.1.5 shows that \(i(A)\) is countably infinite, and therefore so is \(A\text{.}\) In either case, \(A\) is countable.

Proof.
Define \(P:\N^2\to\N\) by \(P(j,m)=2^{j-1}(2m-1)\text{.}\) Every \(k\in\N\) has a unique factorization \(k=2^r q\text{,}\) where \(r\geq0\) and \(q\) is odd. Thus \(k=P(j,m)\) for the unique pair \(j=r+1\) and \(m=(q+1)/2\text{.}\) Therefore \(P\) is bijective.
See Exercise A.2.1 for an alternative constructive proof based on diagonal enumeration.
The countability of \(\N^2\) yields an important closure property.

Proof.
Let \(A_1,A_2,\ldots\) be a countable family indexed by \(\N\text{.}\) For each \(a\in\bigcup_{j\in\N}A_j\text{,}\) let \(j(a)\) be the least index such that \(a\in A_{j(a)}\text{.}\) For each \(j\text{,}\) choose an injection \(f_j:A_j\to\N\text{.}\) Then \(a\mapsto(f_{j(a)}(a),j(a))\) is an injection from \(\bigcup_{j\in\N}A_j\) into \(\N^2\text{.}\) Since \(\N^2\) is countable, the union is countable.
We now apply these countability results to the rational numbers.

Proof.
The map \(n\mapsto n/1\) is an injection from \(\N\) to \(\Q\text{,}\) so \(|\N|\le|\Q|\text{.}\) For the reverse inequality, write each \(r\in\Q\) uniquely as \(r=m/n\) in lowest terms, with \(m\in\Z\) and \(n>0\text{,}\) and map \(r\) to \((m,n)\in\Z\times\N\text{.}\) This map is injective. The map \(c:\Z\to\N\) defined by \(c(m)=2m+1\) for \(m\geq0\) and \(c(m)=-2m\) for \(m<0\) is also injective. Hence \((m,n)\mapsto(c(m),n)\) injects \(\Z\times\N\) into \(\N^2\text{.}\) By Proposition A.1.8, \(\Z\times\N\) is countable, and therefore \(|\Q|\le|\N|\text{.}\) It follows that \(|\Q|=|\N|\) by Theorem A.1.4. Finally, restricting such a bijection to \(\Z\subseteq\Q\) gives an injection from \(\Z\) to \(\N\text{,}\) so \(\Z\) is countable.
We now turn to uncountable sets.
Let \(X\) be a set and \(A\subseteq X\text{.}\) The indicator function of \(A\) in \(X\text{,}\) denoted by \(1_A^X\) (or simply \(1_A\) when \(X\) is understood), is the map \(1_A^X:X\to\{0,1\}\) defined by
\begin{equation*} 1_A^X(x)= \begin{cases} 1,&\text{if }x\in A,\\ 0,&\text{if }x\notin A. \end{cases}. \end{equation*}
Indicator functions give a bijection \(\mathcal{P}(X)\cong 2^X\text{,}\) where \(2^X\) denotes the set of maps from \(X\) to \(\{0,1\}\text{.}\)

Proof.
The map \(x\mapsto 1_{\{x\}}\) is an injection from \(X\) to \(2^X\text{.}\) To prove that no surjection exists in the opposite direction, suppose that \(\Phi:X\to2^X\) is surjective. Define \(d:X\to\{0,1\}\) by \(d(x)=1-\Phi(x)(x)\text{.}\) Surjectivity gives \(d=\Phi(a)\) for some \(a\in X\text{.}\) Evaluating at \(a\) yields \(\Phi(a)(a)=1-\Phi(a)(a)\text{,}\) a contradiction. Hence \(|X|<|2^X|\text{.}\)

Proof.
By Theorem A.1.11, \(|\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{.}\) Since \(|\N|<|2^{\N}|\text{,}\) the real line cannot be countable.

Proof.
If \(\R\setminus\Q\) were countable, then \(\R=(\R\setminus\Q)\cup\Q\) would be a union of two countable sets and therefore countable, contradicting Corollary A.1.12.
PrevTopNext