1.4.7: Reduction

\(\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} } }\)

We showed \(\Pow{\PosInt}\) to be uncountable by a diagonalization argument. We already had a proof that \(\Bin^\omega\), the set of all infinite sequences of \(0\)s and \(1\)s, is uncountable. Here’s another way we can prove that \(\Pow{\PosInt}\) is uncountable: Show that if \(\Pow{\PosInt}\) is countable then \(\Bin^\omega\) is also countable. Since we know \(\Bin^\omega\) is not countable, \(\Pow{\PosInt}\) can’t be either. This is called reducing one problem to another—in this case, we reduce the problem of enumerating \(\Bin^\omega\) to the problem of enumerating \(\Pow{\PosInt}\). A solution to the latter—an enumeration of \(\Pow{\PosInt}\)—would yield a solution to the former—an enumeration of \(\Bin^\omega\).

How do we reduce the problem of enumerating a set \(B\) to that of enumerating a set \(A\)? We provide a way of turning an enumeration of \(A\) into an enumeration of \(B\). The easiest way to do that is to define a surjective function \(f\colon A \to B\). If \(x_1\), \(x_2\), … enumerates \(A\), then \(f(x_1)\), \(f(x_2)\), … would enumerate \(B\). In our case, we are looking for a surjective function \(f\colon \Pow{\PosInt} \to \Bin^\omega\).

Problem \(\PageIndex{1}\)

Show that if there is an injective function \(g\colon B \to A\), and \(B\) is uncountable, then so is \(A\). Do this by showing how you can use \(g\) to turn an enumeration of \(A\) into one of \(B\).

Proof of Theorem 4.6.2 by reduction.

Suppose that \(\Pow{\PosInt}\) were countable, and thus that there is an enumeration of it, \(Z_{1}\), \(Z_{2}\), \(Z_{3}\), …

Define the function \(f \colon \Pow{\PosInt} \to \Bin^\omega\) by letting \(f(Z)\) be the sequence \(s_{k}\) such that \(s_{k}(n) = 1\) iff \(n \in Z\), and \(s_k(n) = 0\) otherwise. This clearly defines a function, since whenever \(Z \subseteq \PosInt\), any \(n \in \PosInt\) either is an element of \(Z\) or isn’t. For instance, the set \(2\PosInt = \{2, 4, 6, \dots\}\) of positive even numbers gets mapped to the sequence \(010101\dots\), the empty set gets mapped to \(0000\dots\) and the set \(\PosInt\) itself to \(1111\dots\).

It also is surjective: Every sequence of \(0\)s and \(1\)s corresponds to some set of positive integers, namely the one which has as its members those integers corresponding to the places where the sequence has \(1\)s. More precisely, suppose \(s \in \Bin^\omega\). Define \(Z \subseteq \PosInt\) by: \[Z = \Setabs{n \in \PosInt}{s(n) = 1}\nonumber\] Then \(f(Z) = s\), as can be verified by consulting the definition of \(f\).

Now consider the list \[f(Z_1), f(Z_2), f(Z_3), \dots\nonumber\] Since \(f\) is surjective, every member of \(\Bin^\omega\) must appear as a value of \(f\) for some argument, and so must appear on the list. This list must therefore enumerate all of \(\Bin^\omega\).

So if \(\Pow{\PosInt}\) were countable, \(\Bin^\omega\) would be countable. But \(\Bin^\omega\) is uncountable (Theorem 4.6.1). Hence \(\Pow{\PosInt}\) is uncountable. ◻

It is easy to be confused about the direction the reduction goes in. For instance, a surjective function \(g \colon \Bin^\omega \to B\) does not establish that \(B\) is uncountable. (Consider \(g \colon \Bin^\omega \to \Bin\) defined by \(g(s) = s(1)\), the function that maps a sequence of \(0\)’s and \(1\)’s to its first element. It is surjective, because some sequences start with \(0\) and some start with \(1\). But \(\Bin\) is finite.) Note also that the function \(f\) must be surjective, or otherwise the argument does not go through: \(f(x_1)\), \(f(x_2)\), … would then not be guaranteed to include all the elements of \(B\). For instance, \[h(n) = \underbrace{000\dots0}_{\text{$n$ $0$'s}}\nonumber\] defines a function \(h\colon \PosInt \to \Bin^\omega\), but \(\PosInt\) is countable.

Problem \(\PageIndex{2}\)

Show that the set of all sets of pairs of positive integers is uncountable by a reduction argument.

Problem \(\PageIndex{3}\)

Show that \(\Nat^\omega\), the set of infinite sequences of natural numbers, is uncountable by a reduction argument.

Problem \(\PageIndex{4}\)

Let \(P\) be the set of functions from the set of positive integers to the set \(\{0\}\), and let \(Q\) be the set of partial functions from the set of positive integers to the set \(\{0\}\). Show that \(P\) is countable and \(Q\) is not. (Hint: reduce the problem of enumerating \(\Bin^\omega\) to enumerating \(Q\)).

Problem \(\PageIndex{5}\)

Let \(S\) be the set of all surjective functions from the set of positive integers to the set {0,1}, i.e., \(S\) consists of all surjective \(f\colon \PosInt \to \Bin\). Show that \(S\) is uncountable.

Problem \(\PageIndex{6}\)

Show that the set \(\Real\) of all real numbers is uncountable.