1.4.6: Uncountable Sets

\(\def\Assign#1#2{ { #1^{\Struct{#2}} } }\)
\(\def\Atom#1#2{ { \mathord{#1}(#2) } }\)
\(\def\Bin{ {\mathbb{B}} }\)
\(\def\cardeq#1#2{ { #1 \approx #2 } }\)
\(\def\cardle#1#2{ { #1 \preceq #2 } }\)
\(\def\cardless#1#2{ { #1 \prec #2 } }\)
\(\def\cardneq#1#2{ { #1 \not\approx #2 } }\)
\(\def\comp#1#2{ { #2 \circ #1 } }\)
\(\def\concat{ { \;\frown\; } }\)
\(\def\Cut{ { \text{Cut} } }\)
\(\def\Discharge#1#2{ { [#1]^#2 } }\)
\(\def\DischargeRule#1#2{ { \RightLabel{#1}\LeftLabel{\scriptsize{#2} } } }\)
\(\def\dom#1{ {\operatorname{dom}(#1)} }\)
\(\def\Domain#1{ {\left| \Struct{#1} \right|} }\)
\(\def\Elim#1{ { {#1}\mathrm{Elim} } }\)
\(\newcommand{\Entails}{\vDash}\)
\(\newcommand{\EntailsN}{\nvDash}\)
\(\def\eq[#1][#2]{ { #1 = #2 } }\)
\(\def\eqN[#1][#2]{ { #1 \neq #2 } }\)
\(\def\equivclass#1#2{ { #1/_{#2} } }\)
\(\def\equivrep#1#2{ { [#1]_{#2} } }\)
\(\def\Exchange{ { \text{X} } }\)
\(\def\False{ { \mathbb{F} } }\)
\(\def\FalseCl{ { \lfalse_C } }\)
\(\def\FalseInt{ { \lfalse_I } }\)
\(\def\fCenter{ { \,\Sequent\, } }\)
\(\def\fdefined{ { \;\downarrow } }\)
\(\def\fn#1{ { \operatorname{#1} } }\)
\(\def\Frm[#1]{ {\operatorname{Frm}(\Lang #1)} }\)
\(\def\fundefined{ { \;\uparrow } }\)
\(\def\funimage#1#2{ { #1[#2] } }\)
\(\def\funrestrictionto#1#2{ { #1 \restriction_{#2} } }\)
\(\newcommand{\ident}{\equiv}\)
\(\newcommand{\indcase}[2]{#1 \ident #2\text{:}}\)
\(\newcommand{\indcaseA}[2]{#1 \text{ is atomic:}}\)
\(\def\indfrm{ { A } }\)
\(\def\indfrmp{ { A } }\)
\(\def\joinrel{\mathrel{\mkern-3mu}}\)
\(\def\lambd[#1][#2]{\lambda #1 . #2}\)
\(\def\Lang#1{ { \mathcal{#1} } }\)
\(\def\LeftR#1{ { {#1}\mathrm{L} } }\)
\(\def\len#1{ {\operatorname{len}(#1)} }\)
\(\def\lexists#1#2{ { \exists #1\, #2 } }\)
\(\def\lfalse{ {\bot} }\)
\(\def\lforall#1#2{ { \forall#1\, #2 } }\)
\(\newcommand{\lif}{\rightarrow}\)
\(\newcommand{\liff}{\leftrightarrow}\)
\(\def\Log#1{ { \mathbf{#1} } }\)
\(\def\ltrue{ {\top} }\)
\(\def\Id#1{ {\operatorname{Id}_#1} }\)
\(\def\Int{ {\mathbb{Z}} }\)
\(\def\Intro#1{ { {#1}\mathrm{Intro} } }\)
\(\def\mModel#1{ { \mathfrak{#1} } }\)
\(\newcommand{\mSat}[3][{}]{\mModel{#2}{#1}\Vdash{#3}}\)
\(\newcommand{\mSatN}[3][{}]{\mModel{#2}{#1}\nVdash{#3}}\)
\(\def\Nat{ {\mathbb{N}} }\)
\(\def\nicefrac#1#2{ {{}^#1/_#2} }\)
\(\def\num#1{ { \overline{#1} } }\)

\(\def\ran#1{ {\operatorname{ran}(#1)} }\)
\(\newcommand{\Obj}[1]{\mathsf{#1}}\)
\(\def\Rat{ {\mathbb{Q}} }\)
\(\def\Real{ {\mathbb{R}} }\)
\(\def\RightR#1{ { {#1}\mathrm{R} } }\)
\(\def\Part#1#2{ { \Atom{\Obj P}{#1, #2} } }\)
\(\def\pto{ { \hspace{0.1 cm}\to\hspace{-0.44 cm}\vcenter{\tiny{\hbox{|}}}\hspace{0.35 cm} } }\)
\(\def\PosInt{ {\mathbb{Z}^+} }\)
\(\def\Pow#1{ {\wp(#1)} }\)
\(\newcommand{\Proves}{\vdash}\)
\(\newcommand{\ProvesN}{\nvdash}\)
\(\def\Relbar{\mathrel{=}}\)
\(\newcommand{\Sat}[3][{}]{\Struct{#2}{#1}\vDash{#3}}\)
\(\newcommand{\SatN}[3][{}]{\Struct{#2}{#1}\nvDash{#3}}\)
\(\newcommand{\Sequent}{\Rightarrow}\)
\(\def\Setabs#1#2{ { \{#1:#2\} } }\)
\(\newcommand{\sFmla}[2]{#1\,#2}\)
\(\def\Struct#1{ {#1} }\)
\(\def\subst#1#2{ { #1/#2 } }\)
\(\def\Subst#1#2#3{ { #1[\subst{#2}{#3}] } }\)
\(\def\TMblank{ { 0 } }\)
\(\newcommand{\TMendtape}{\triangleright}\)
\(\def\TMleft{ { L } }\)
\(\def\TMright{ { R } }\)
\(\def\TMstay{ { N } }\)
\(\def\TMstroke{ { 1 } }\)
\(\def\TMtrans#1#2#3{ { #1,#2,#3 } }\)
\(\def\Trm[#1]{ {\operatorname{Trm}(\Lang #1)} }\)
\(\def\True{ { \mathbb{T} } }\)
\(\newcommand{\TRule}[2]{#2#1}\)
\(\def\tuple#1{ {\langle #1 \rangle} }\)
\(\newcommand{\Value}[3][\,]{\mathrm{Val}_{#1}^{#3}(#2)}\)
\(\def\Var{ { \mathrm{Var} } }\)
\(\newcommand{\varAssign}[3]{#1 \sim_{#3} #2}\)
\(\def\Weakening{ { \text{W} } }\)

Some sets, such as the set \(\PosInt\) of positive integers, are infinite. So far we’ve seen examples of infinite sets which were all countable. However, there are also infinite sets which do not have this property. Such sets are called uncountable.

First of all, it is perhaps already surprising that there are uncountable sets. For any countable set \(A\) there is a surjective function \(f \colon \PosInt \to A\). If a set is uncountable there is no such function. That is, no function mapping the infinitely many elements of \(\PosInt\) to \(A\) can exhaust all of \(A\). So there are “more” elements of \(A\) than the infinitely many positive integers.

How would one prove that a set is uncountable? You have to show that no such surjective function can exist. Equivalently, you have to show that the elements of \(A\) cannot be enumerated in a one way infinite list. The best way to do this is to show that every list of elements of \(A\) must leave at least one element out; or that no function \(f\colon \PosInt \to A\) can be surjective. We can do this using Cantor’s diagonal method. Given a list of elements of \(A\), say, \(x_1\), \(x_2\), …, we construct another element of \(A\) which, by its construction, cannot possibly be on that list.

Our first example is the set \(\Bin^\omega\) of all infinite, non-gappy sequences of \(0\)’s and \(1\)’s.

Theorem \(\PageIndex{1}\)

\(\Bin^\omega\) is uncountable.

Proof. Suppose, by way of contradiction, that \(\Bin^\omega\) is countable, i.e., suppose that there is a list \(s_{1}\), \(s_{2}\), \(s_{3}\), \(s_{4}\), … of all elements of \(\Bin^\omega\). Each of these \(s_i\) is itself an infinite sequence of \(0\)’s and \(1\)’s. Let’s call the \(j\)-th element of the \(i\)-th sequence in this list \(s_i(j)\). Then the \(i\)-th sequence \(s_i\) is \[s_i(1), s_i(2), s_i(3), \dots\nonumber\]

We may arrange this list, and the elements of each sequence \(s_i\) in it, in an array: \[\begin{array}{c|c|c|c|c|c} & 1 & 2 & 3 & 4 & \dots \\\hline 1 & \mathbf{s_{1}(1)} & s_{1}(2) & s_{1}(3) & s_1(4) & \dots \\\hline 2 & s_{2}(1)& \mathbf{s_{2}(2)} & s_2(3) & s_2(4) & \dots \\\hline 3 & s_{3}(1)& s_{3}(2) & \mathbf{s_3(3)} & s_3(4) & \dots \\\hline 4 & s_{4}(1)& s_{4}(2) & s_4(3) & \mathbf{s_4(4)} & \dots \\\hline \vdots & \vdots & \vdots & \vdots & \vdots & \mathbf{\ddots} \end{array}\nonumber\] The labels down the side give the number of the sequence in the list \(s_1\), \(s_2\), …; the numbers across the top label the elements of the individual sequences. For instance, \(s_{1}(1)\) is a name for whatever number, a \(0\) or a \(1\), is the first element in the sequence \(s_{1}\), and so on.

Now we construct an infinite sequence, \(\overline{s}\), of \(0\)’s and \(1\)’s which cannot possibly be on this list. The definition of \(\overline{s}\) will depend on the list \(s_1\), \(s_2\), …. Any infinite list of infinite sequences of \(0\)’s and \(1\)’s gives rise to an infinite sequence \(\overline{s}\) which is guaranteed to not appear on the list.

To define \(\overline{s}\), we specify what all its elements are, i.e., we specify \(\overline{s}(n)\) for all \(n \in \PosInt\). We do this by reading down the diagonal of the array above (hence the name “diagonal method”) and then changing every \(1\) to a \(0\) and every \(0\) to a \(1\). More abstractly, we define \(\overline{s}(n)\) to be \(0\) or \(1\) according to whether the \(n\)-th element of the diagonal, \(s_n(n)\), is \(1\) or \(0\). \[\overline{s}(n) = \begin{cases} 1 & \text{if $s_{n}(n) = 0$}\\ 0 & \text{if $s_{n}(n) = 1$}. \end{cases}\nonumber\] If you like formulas better than definitions by cases, you could also define \(\overline{s}(n) = 1 - s_n(n)\).

Clearly \(\overline{s}\) is an infinite sequence of \(0\)’s and \(1\)’s, since it is just the mirror sequence to the sequence of \(0\)’s and \(1\)’s that appear on the diagonal of our array. So \(\overline{s}\) is an element of \(\Bin^\omega\). But it cannot be on the list \(s_1\), \(s_2\), … Why not?

It can’t be the first sequence in the list, \(s_1\), because it differs from \(s_1\) in the first element. Whatever \(s_1(1)\) is, we defined \(\overline{s}(1)\) to be the opposite. It can’t be the second sequence in the list, because \(\overline{s}\) differs from \(s_2\) in the second element: if \(s_2(2)\) is \(0\), \(\overline{s}(2)\) is \(1\), and vice versa. And so on.

More precisely: if \(\overline{s}\) were on the list, there would be some \(k\) so that \(\overline{s} = s_{k}\). Two sequences are identical iff they agree at every place, i.e., for any \(n\), \(\overline{s}(n) = s_{k}(n)\). So in particular, taking \(n = k\) as a special case, \(\overline{s}(k) = s_{k}(k)\) would have to hold. \(s_k(k)\) is either \(0\) or \(1\). If it is \(0\) then \(\overline{s}(k)\) must be \(1\)—that’s how we defined \(\overline{s}\). But if \(s_k(k) = 1\) then, again because of the way we defined \(\overline{s}\), \(\overline{s}(k) = 0\). In either case \(\overline{s}(k) \neq s_{k}(k)\).

We started by assuming that there is a list of elements of \(\Bin^\omega\), \(s_1\), \(s_2\), … From this list we constructed a sequence \(\overline{s}\) which we proved cannot be on the list. But it definitely is a sequence of \(0\)’s and \(1\)’s if all the \(s_i\) are sequences of \(0\)’s and \(1\)’s, i.e., \(\overline{s} \in \Bin^\omega\). This shows in particular that there can be no list of all elements of \(\Bin^\omega\), since for any such list we could also construct a sequence \(\overline{s}\) guaranteed to not be on the list, so the assumption that there is a list of all sequences in \(\Bin^\omega\) leads to a contradiction. ◻

This proof method is called “diagonalization” because it uses the diagonal of the array to define \(\overline{s}\). Diagonalization need not involve the presence of an array: we can show that sets are not countable by using a similar idea even when no array and no actual diagonal is involved.

Theorem \(\PageIndex{2}\)

\(\Pow{\PosInt}\) is not countable.

Proof. We proceed in the same way, by showing that for every list of subsets of \(\PosInt\) there is a subset of \(\PosInt\) which cannot be on the list. Suppose the following is a given list of subsets of \(\PosInt\): \[Z_{1}, Z_{2}, Z_{3}, \dots\nonumber\] We now define a set \(\overline{Z}\) such that for any \(n \in \PosInt\), \(n \in \overline{Z}\) iff \(n \notin Z_{n}\): \[\overline{Z} = \Setabs{n \in \PosInt}{n \notin Z_n}\nonumber\] \(\overline{Z}\) is clearly a set of positive integers, since by assumption each \(Z_n\) is, and thus \(\overline{Z} \in \Pow{\PosInt}\). But \(\overline{Z}\) cannot be on the list. To show this, we’ll establish that for each \(k \in \PosInt\), \(\overline{Z} \neq Z_k\).

So let \(k \in \PosInt\) be arbitrary. We’ve defined \(\overline{Z}\) so that for any \(n \in \PosInt\), \(n \in \overline{Z}\) iff \(n \notin Z_n\). In particular, taking \(n=k\), \(k \in \overline{Z}\) iff \(k \notin Z_k\). But this shows that \(\overline{Z} \neq Z_k\), since \(k\) is an element of one but not the other, and so \(\overline{Z}\) and \(Z_k\) have different elements. Since \(k\) was arbitrary, \(\overline{Z}\) is not on the list \(Z_1\), \(Z_2\), … ◻

The preceding proof did not mention a diagonal, but you can think of it as involving a diagonal if you picture it this way: Imagine the sets \(Z_1\), \(Z_2\), …, written in an array, where each element \(j \in Z_i\) is listed in the \(j\)-th column. Say the first four sets on that list are \(\{1,2,3,\dots\}\), \(\{2, 4, 6, \dots\}\), \(\{1,2,5\}\), and \(\{3,4,5,\dots\}\). Then the array would begin with \[\begin{array}{r@{}rrrrrrr} Z_1 = \{ & \mathbf{1}, & 2, & 3, & 4, & 5, & 6, & \dots\}\\ Z_2 = \{ & & \mathbf{2}, & & 4, & & 6, & \dots\}\\ Z_3 = \{ & 1, & 2, & & & 5\phantom{,} & & \}\\ Z_4 = \{ & & & 3, & \mathbf{4}, & 5, & 6, & \dots\}\\ \vdots & & & & & \ddots \end{array}\nonumber\] Then \(\overline{Z}\) is the set obtained by going down the diagonal, leaving out any numbers that appear along the diagonal and include those \(j\) where the array has a gap in the \(j\)-th row/column. In the above case, we would leave out \(1\) and \(2\), include \(3\), leave out \(4\), etc.

Problem \(\PageIndex{1}\)

Show that \(\Pow{\Nat}\) is uncountable by a diagonal argument.

Problem \(\PageIndex{2}\)

Show that the set of functions \(f \colon \PosInt \to \PosInt\) is uncountable by an explicit diagonal argument. That is, show that if \(f_1\), \(f_2\), …, is a list of functions and each \(f_i\colon \PosInt \to \PosInt\), then there is some \(\overline{f}\colon \PosInt \to \PosInt\) not on this list.