Diagonal Argument
\(\newcommand{\footnotename}{footnote}\)
\(\def \LWRfootnote {1}\)
\(\newcommand {\footnote }[2][\LWRfootnote ]{{}^{\mathrm {#1}}}\)
\(\newcommand {\footnotemark }[1][\LWRfootnote ]{{}^{\mathrm {#1}}}\)
\(\let \LWRorighspace \hspace \)
\(\renewcommand {\hspace }{\ifstar \LWRorighspace \LWRorighspace }\)
\(\newcommand {\mathnormal }[1]{{#1}}\)
\(\newcommand \ensuremath [1]{#1}\)
\(\newcommand {\LWRframebox }[2][]{\fbox {#2}} \newcommand {\framebox }[1][]{\LWRframebox } \)
\(\newcommand {\setlength }[2]{}\)
\(\newcommand {\addtolength }[2]{}\)
\(\newcommand {\setcounter }[2]{}\)
\(\newcommand {\addtocounter }[2]{}\)
\(\newcommand {\arabic }[1]{}\)
\(\newcommand {\number }[1]{}\)
\(\newcommand {\noalign }[1]{\text {#1}\notag \\}\)
\(\newcommand {\cline }[1]{}\)
\(\newcommand {\directlua }[1]{\text {(directlua)}}\)
\(\newcommand {\luatexdirectlua }[1]{\text {(directlua)}}\)
\(\newcommand {\protect }{}\)
\(\def \LWRabsorbnumber #1 {}\)
\(\def \LWRabsorbquotenumber "#1 {}\)
\(\newcommand {\LWRabsorboption }[1][]{}\)
\(\newcommand {\LWRabsorbtwooptions }[1][]{\LWRabsorboption }\)
\(\def \mathchar {\ifnextchar "\LWRabsorbquotenumber \LWRabsorbnumber }\)
\(\def \mathcode #1={\mathchar }\)
\(\let \delcode \mathcode \)
\(\let \delimiter \mathchar \)
\(\def \oe {\unicode {x0153}}\)
\(\def \OE {\unicode {x0152}}\)
\(\def \ae {\unicode {x00E6}}\)
\(\def \AE {\unicode {x00C6}}\)
\(\def \aa {\unicode {x00E5}}\)
\(\def \AA {\unicode {x00C5}}\)
\(\def \o {\unicode {x00F8}}\)
\(\def \O {\unicode {x00D8}}\)
\(\def \l {\unicode {x0142}}\)
\(\def \L {\unicode {x0141}}\)
\(\def \ss {\unicode {x00DF}}\)
\(\def \SS {\unicode {x1E9E}}\)
\(\def \dag {\unicode {x2020}}\)
\(\def \ddag {\unicode {x2021}}\)
\(\def \P {\unicode {x00B6}}\)
\(\def \copyright {\unicode {x00A9}}\)
\(\def \pounds {\unicode {x00A3}}\)
\(\let \LWRref \ref \)
\(\renewcommand {\ref }{\ifstar \LWRref \LWRref }\)
\( \newcommand {\multicolumn }[3]{#3}\)
\(\require {textcomp}\)
\(\newcommand {\intertext }[1]{\text {#1}\notag \\}\)
\(\let \Hat \hat \)
\(\let \Check \check \)
\(\let \Tilde \tilde \)
\(\let \Acute \acute \)
\(\let \Grave \grave \)
\(\let \Dot \dot \)
\(\let \Ddot \ddot \)
\(\let \Breve \breve \)
\(\let \Bar \bar \)
\(\let \Vec \vec \)
\(\require {mathtools}\)
\(\newenvironment {crampedsubarray}[1]{}{}\)
\(\newcommand {\smashoperator }[2][]{#2\limits }\)
\(\newcommand {\SwapAboveDisplaySkip }{}\)
\(\newcommand {\LaTeXunderbrace }[1]{\underbrace {#1}}\)
\(\newcommand {\LaTeXoverbrace }[1]{\overbrace {#1}}\)
\(\newcommand {\LWRmultlined }[1][]{\begin {multline*}}\)
\(\newenvironment {multlined}[1][]{\LWRmultlined }{\end {multline*}}\)
\(\let \LWRorigshoveleft \shoveleft \)
\(\renewcommand {\shoveleft }[1][]{\LWRorigshoveleft }\)
\(\let \LWRorigshoveright \shoveright \)
\(\renewcommand {\shoveright }[1][]{\LWRorigshoveright }\)
\(\newcommand {\shortintertext }[1]{\text {#1}\notag \\}\)
\(\newcommand {\vcentcolon }{\mathrel {\unicode {x2236}}}\)
\(\def \LWRtensorindicesthreesub #1#2{{_{#2}}\LWRtensorindicesthree }\)
\(\def \LWRtensorindicesthreesup #1#2{{^{#2}}\LWRtensorindicesthree }\)
\(\newcommand {\LWRtensorindicesthreenotsup }{}\)
\(\newcommand {\LWRtensorindicesthreenotsub }{ \ifnextchar ^ \LWRtensorindicesthreesup \LWRtensorindicesthreenotsup }\)
\(\newcommand {\LWRtensorindicesthree }{ \ifnextchar _ \LWRtensorindicesthreesub \LWRtensorindicesthreenotsub }\)
\(\newcommand {\LWRtensorindicestwo }{ \ifstar \LWRtensorindicesthree \LWRtensorindicesthree }\)
\(\newcommand {\indices }[1]{\LWRtensorindicestwo #1}\)
\(\newcommand {\LWRtensortwo }[3][]{{}\indices {#1}{#2}\indices {#3}}\)
\(\newcommand {\tensor }{\ifstar \LWRtensortwo \LWRtensortwo }\)
\(\newcommand {\LWRnuclidetwo }[2][]{{\vphantom {\mathrm {#2}}{}^{\LWRtensornucleonnumber }_{#1}\mathrm {#2}}}\)
\(\newcommand {\nuclide }[1][]{\def \LWRtensornucleonnumber {#1}\LWRnuclidetwo }\)
\(\newcommand {\FF }{\mathbb {F}}\)
\(\newcommand {\cO }{\mathcal {O}}\)
\(\newcommand {\cC }{\mathcal {C}}\)
\(\newcommand {\cP }{\mathcal {P}}\)
\(\newcommand {\cF }{\mathcal {F}}\)
\(\newcommand {\cS }{\mathcal {S}}\)
\(\newcommand {\cK }{\mathcal {K}}\)
\(\newcommand {\cM }{\mathcal {M}}\)
\(\newcommand {\GG }{\mathbb {G}}\)
\(\newcommand {\ZZ }{\mathbb {Z}}\)
\(\newcommand {\NN }{\mathbb {N}}\)
\(\newcommand {\PP }{\mathbb {P}}\)
\(\newcommand {\QQ }{\mathbb {Q}}\)
\(\newcommand {\RR }{\mathbb {R}}\)
\(\newcommand {\LL }{\mathbb {L}}\)
\(\newcommand {\HH }{\mathbb {H}}\)
\(\newcommand {\EE }{\mathbb {E}}\)
\(\newcommand {\SP }{\mathbb {S}}\)
\(\newcommand {\CC }{\mathbb {C}}\)
\(\newcommand {\FF }{\mathbb {F}}\)
\(\renewcommand {\AA }{\mathbb {A}}\)
\(\newcommand {\sF }{\mathscr {F}}\)
\(\newcommand {\sC }{\mathscr {C}}\)
\(\newcommand {\ts }{\textsuperscript }\)
\(\newcommand {\mf }{\mathfrak }\)
\(\newcommand {\cc }{\mf {c}}\)
\(\newcommand {\mg }{\mf {g}}\)
\(\newcommand {\ma }{\mf {a}}\)
\(\newcommand {\mh }{\mf {h}}\)
\(\newcommand {\mn }{\mf {n}}\)
\(\newcommand {\mc }{\mf {c}}\)
\(\newcommand {\ul }{\underline }\)
\(\newcommand {\mz }{\mf {z}}\)
\(\newcommand {\me }{\mf {e}}\)
\(\newcommand {\mff }{\mf {f}}\)
\(\newcommand {\mm }{\mf {m}}\)
\(\newcommand {\mt }{\mf {t}}\)
\(\newcommand {\pp }{\mf {p}}\)
\(\newcommand {\qq }{\mf {q}}\)
\(\newcommand {\gl }{\mf {gl}}\)
\(\newcommand {\msl }{\mf {sl}}\)
\(\newcommand {\so }{\mf {so}}\)
\(\newcommand {\mfu }{\mf {u}}\)
\(\newcommand {\su }{\mf {su}}\)
\(\newcommand {\msp }{\mf {sp}}\)
\(\renewcommand {\aa }{\mf {a}}\)
\(\newcommand {\bb }{\mf {b}}\)
\(\newcommand {\sR }{\mathscr {R}}\)
\(\newcommand {\lb }{\langle }\)
\(\newcommand {\rb }{\rangle }\)
\(\newcommand {\ff }{\mf {f}}\)
\(\newcommand {\ee }{\epsilon }\)
\(\newcommand {\heart }{\heartsuit }\)
\(\newcommand {\Mloc }{\mathcal {M}_{\text {loc}}}\)
\(\newcommand {\Mnilpnil }{\mathcal {M}_{\text {nil}}^{\text {pnil}}}\)
\(\newcommand {\Uloc }{\mathcal {U}_{\text {loc}}}\)
\(\newcommand {\Mnil }{\mathcal {M}_{\text {nil}}}\)
\(\newcommand {\Unil }{\mathcal {U}_{\text {nil}}}\)
\(\newcommand {\floor }[1]{\lfloor #1 \rfloor }\)
\(\newcommand {\ceil }[1]{\lceil #1 \rceil }\)
\(\newcommand {\pushout }{\arrow [ul, phantom, "\ulcorner ", very near start]}\)
\(\newcommand {\pullback }{\arrow [dr, phantom, "\lrcorner ", very near start]}\)
\(\newcommand {\simp }[1]{#1^{\Delta ^{op}}}\)
\(\newcommand {\arrowtcupp }[2]{\arrow [bend left=50, ""{name=U, below,inner sep=1}]{#1}\arrow [Rightarrow,from=U,to=MU,"#2"]}\)
\(\newcommand {\arrowtclow }[2]{\arrow [bend right=50, ""{name=L,inner sep=1}]{#1}\arrow [Rightarrow,from=LM,to=L]{}[]{#2}}\)
\(\newcommand {\arrowtcmid }[2]{\arrow [""{name=MU,inner sep=1},""{name=LM,below,inner sep=1}]{#1}[pos=.1]{#2}}\)
\(\newcommand {\dummy }{\textcolor {white}{\bullet }}\)
\(\newcommand {\adjunction }[4]{ #1\hspace {2pt}\colon #2 \leftrightharpoons #3 \hspace {2pt}\colon #4 }\)
\(\newcommand {\aug }{\mathop {\rm aug}\nolimits }\)
\(\newcommand {\MC }{\mathop {\rm MC}\nolimits }\)
\(\newcommand {\art }{\mathop {\rm art}\nolimits }\)
\(\newcommand {\DiGrph }{\mathop {\rm DiGrph}\nolimits }\)
\(\newcommand {\FMP }{\mathop {\rm FMP}\nolimits }\)
\(\newcommand {\CAlg }{\mathop {\rm CAlg}\nolimits }\)
\(\newcommand {\perf }{\mathop {\rm perf}\nolimits }\)
\(\newcommand {\cof }{\mathop {\rm cof}\nolimits }\)
\(\newcommand {\fib }{\mathop {\rm fib}\nolimits }\)
\(\newcommand {\Thick }{\mathop {\rm Thick}\nolimits }\)
\(\newcommand {\Orb }{\mathop {\rm Orb}\nolimits }\)
\(\newcommand {\ko }{\mathop {\rm ko}\nolimits }\)
\(\newcommand {\Spf }{\mathop {\rm Spf}\nolimits }\)
\(\newcommand {\Spc }{\mathop {\rm Spc}\nolimits }\)
\(\newcommand {\sk }{\mathop {\rm sk}\nolimits }\)
\(\newcommand {\cosk }{\mathop {\rm cosk}\nolimits }\)
\(\newcommand {\holim }{\mathop {\rm holim}\nolimits }\)
\(\newcommand {\hocolim }{\mathop {\rm hocolim}\nolimits }\)
\(\newcommand {\Pre }{\mathop {\rm Pre}\nolimits }\)
\(\newcommand {\THR }{\mathop {\rm THR}\nolimits }\)
\(\newcommand {\THH }{\mathop {\rm THH}\nolimits }\)
\(\newcommand {\Fun }{\mathop {\rm Fun}\nolimits }\)
\(\newcommand {\Loc }{\mathop {\rm Loc}\nolimits }\)
\(\newcommand {\Bord }{\mathop {\rm Bord}\nolimits }\)
\(\newcommand {\Cob }{\mathop {\rm Cob}\nolimits }\)
\(\newcommand {\Set }{\mathop {\rm Set}\nolimits }\)
\(\newcommand {\Ind }{\mathop {\rm Ind}\nolimits }\)
\(\newcommand {\Sind }{\mathop {\rm Sind}\nolimits }\)
\(\newcommand {\Ext }{\mathop {\rm Ext}\nolimits }\)
\(\newcommand {\sd }{\mathop {\rm sd}\nolimits }\)
\(\newcommand {\Ex }{\mathop {\rm Ex}\nolimits }\)
\(\newcommand {\Out }{\mathop {\rm Out}\nolimits }\)
\(\newcommand {\Cyl }{\mathop {\rm Cyl}\nolimits }\)
\(\newcommand {\Path }{\mathop {\rm Path}\nolimits }\)
\(\newcommand {\Ch }{\mathop {\rm Ch}\nolimits }\)
\(\newcommand {\SSet }{\mathop {\rm \Set ^{\Delta ^{op}}}\nolimits }\)
\(\newcommand {\Sq }{\mathop {\rm Sq}\nolimits }\)
\(\newcommand {\Free }{\mathop {\rm Free}\nolimits }\)
\(\newcommand {\Map }{\mathop {\rm Map}\nolimits }\)
\(\newcommand {\Chain }{\mathop {\rm Ch}\nolimits }\)
\(\newcommand {\LMap }{\mathop {\rm LMap}\nolimits }\)
\(\newcommand {\RMap }{\mathop {\rm RMap}\nolimits }\)
\(\newcommand {\Tot }{\mathop {\rm Tot}\nolimits }\)
\(\newcommand {\MU }{\mathop {\rm MU}\nolimits }\)
\(\newcommand {\MSU }{\mathop {\rm MSU}\nolimits }\)
\(\newcommand {\MSp }{\mathop {\rm MSp}\nolimits }\)
\(\newcommand {\MSO }{\mathop {\rm MSO}\nolimits }\)
\(\newcommand {\MO }{\mathop {\rm MO}\nolimits }\)
\(\newcommand {\BU }{\mathop {\rm BU}\nolimits }\)
\(\newcommand {\KU }{\mathop {\rm KU}\nolimits }\)
\(\newcommand {\BSU }{\mathop {\rm BSU}\nolimits }\)
\(\newcommand {\BSp }{\mathop {\rm BSp}\nolimits }\)
\(\newcommand {\BGL }{\mathop {\rm BGL}\nolimits }\)
\(\newcommand {\BSO }{\mathop {\rm BSO}\nolimits }\)
\(\newcommand {\BO }{\mathop {\rm BO}\nolimits }\)
\(\newcommand {\KO }{\mathop {\rm KO}\nolimits }\)
\(\newcommand {\Tor }{\mathop {\rm Tor}\nolimits }\)
\(\newcommand {\Cotor }{\mathop {\rm Cotor}\nolimits }\)
\(\newcommand {\imag }{\mathop {\rm Im}\nolimits }\)
\(\newcommand {\real }{\mathop {\rm Re}\nolimits }\)
\(\newcommand {\Cat }{\mathop {\rm Cat}\nolimits }\)
\(\newcommand {\Fld }{\mathop {\rm Fld}\nolimits }\)
\(\newcommand {\Frac }{\mathop {\rm Frac}\nolimits }\)
\(\newcommand {\Dom }{\mathop {\rm Dom}\nolimits }\)
\(\newcommand {\Hotc }{\mathop {\rm Hotc}\nolimits }\)
\(\newcommand {\Top }{\mathop {\rm Top}\nolimits }\)
\(\newcommand {\Ring }{\mathop {\rm Ring}\nolimits }\)
\(\newcommand {\CRing }{\mathop {\rm CRing}\nolimits }\)
\(\newcommand {\CGHaus }{\mathop {\rm CGHaus}\nolimits }\)
\(\newcommand {\Alg }{\mathop {\rm Alg}\nolimits }\)
\(\newcommand {\Bool }{\mathop {\rm Bool}\nolimits }\)
\(\newcommand {\hTop }{\mathop {\rm hTop}\nolimits }\)
\(\newcommand {\Nat }{\mathop {\rm Nat}\nolimits }\)
\(\newcommand {\Rel }{\mathop {\rm Rel}\nolimits }\)
\(\newcommand {\Mod }{\mathop {\rm Mod}\nolimits }\)
\(\newcommand {\Space }{\mathop {\rm Space}\nolimits }\)
\(\newcommand {\Vect }{\mathop {\rm Vect}\nolimits }\)
\(\newcommand {\FinVect }{\mathop {\rm FinVect}\nolimits }\)
\(\newcommand {\Matr }{\mathop {\rm Matr}\nolimits }\)
\(\newcommand {\Ab }{\mathop {\rm Ab}\nolimits }\)
\(\newcommand {\Gr }{\mathop {\rm Gr}\nolimits }\)
\(\newcommand {\Grp }{\mathop {\rm Grp}\nolimits }\)
\(\newcommand {\Hol }{\mathop {\rm Hol}\nolimits }\)
\(\newcommand {\Gpd }{\mathop {\rm Gpd}\nolimits }\)
\(\newcommand {\Grpd }{\mathop {\rm Gpd}\nolimits }\)
\(\newcommand {\Mon }{\mathop {\rm Mon}\nolimits }\)
\(\newcommand {\FinSet }{\mathop {\rm FinSet}\nolimits }\)
\(\newcommand {\Sch }{\mathop {\rm Sch}\nolimits }\)
\(\newcommand {\AffSch }{\mathop {\rm AffSch}\nolimits }\)
\(\newcommand {\Idem }{\mathop {\rm Idem}\nolimits }\)
\(\newcommand {\SIdem }{\mathop {\rm SIdem}\nolimits }\)
\(\newcommand {\Aut }{\mathop {\rm Aut}\nolimits }\)
\(\newcommand {\Ord }{\mathop {\rm Ord}\nolimits }\)
\(\newcommand {\coker }{\mathop {\rm coker}\nolimits }\)
\(\newcommand {\ch }{\mathop {\rm char}\nolimits }\)
\(\newcommand {\Sym }{\mathop {\rm Sym}\nolimits }\)
\(\newcommand {\adj }{\mathop {\rm adj}\nolimits }\)
\(\newcommand {\dil }{\mathop {\rm dil}\nolimits }\)
\(\newcommand {\Cl }{\mathop {\rm Cl}\nolimits }\)
\(\newcommand {\Diff }{\mathop {\rm Diff}\nolimits }\)
\(\newcommand {\End }{\mathop {\rm End}\nolimits }\)
\(\newcommand {\Hom }{\mathop {\rm Hom}\nolimits }\)
\(\newcommand {\Gal }{\mathop {\rm Gal}\nolimits }\)
\(\newcommand {\Pos }{\mathop {\rm Pos}\nolimits }\)
\(\newcommand {\Ad }{\mathop {\rm Ad}\nolimits }\)
\(\newcommand {\GL }{\mathop {\rm GL}\nolimits }\)
\(\newcommand {\SL }{\mathop {\rm SL}\nolimits }\)
\(\newcommand {\vol }{\mathop {\rm vol}\nolimits }\)
\(\newcommand {\reg }{\mathop {\rm reg}\nolimits }\)
\(\newcommand {\Or }{\textnormal {O}}\)
\(\newcommand {\U }{\mathop {\rm U}\nolimits }\)
\(\newcommand {\SOr }{\mathop {\rm SO}\nolimits }\)
\(\newcommand {\SU }{\mathop {\rm SU}\nolimits }\)
\(\newcommand {\Spin }{\mathop {\rm Spin}\nolimits }\)
\(\newcommand {\Sp }{\mathop {\rm Sp}\nolimits }\)
\(\newcommand {\Int }{\mathop {\rm Int}\nolimits }\)
\(\newcommand {\im }{\mathop {\rm im}\nolimits }\)
\(\newcommand {\dom }{\mathop {\rm dom}\nolimits }\)
\(\newcommand {\di }{\mathop {\rm div}\nolimits }\)
\(\newcommand {\cod }{\mathop {\rm cod}\nolimits }\)
\(\newcommand {\colim }{\mathop {\rm colim}\nolimits }\)
\(\newcommand {\ad }{\mathop {\rm ad}\nolimits }\)
\(\newcommand {\PSL }{\mathop {\rm PSL}\nolimits }\)
\(\newcommand {\PGL }{\mathop {\rm PGL}\nolimits }\)
\(\newcommand {\sep }{\mathop {\rm sep}\nolimits }\)
\(\newcommand {\MCG }{\mathop {\rm MCG}\nolimits }\)
\(\newcommand {\oMCG }{\mathop {\rm MCG^+}\nolimits }\)
\(\newcommand {\Spec }{\mathop {\rm Spec}\nolimits }\)
\(\newcommand {\rank }{\mathop {\rm rank}\nolimits }\)
\(\newcommand {\diverg }{\mathop {\rm div}\nolimits }\)
\(\newcommand {\disc }{\mathop {\rm disc}\nolimits }\)
\(\newcommand {\sign }{\mathop {\rm sign}\nolimits }\)
\(\newcommand {\Arf }{\mathop {\rm Arf}\nolimits }\)
\(\newcommand {\Pic }{\mathop {\rm Pic}\nolimits }\)
\(\newcommand {\Tr }{\mathop {\rm Tr}\nolimits }\)
\(\newcommand {\res }{\mathop {\rm res}\nolimits }\)
\(\newcommand {\Proj }{\mathop {\rm Proj}\nolimits }\)
\(\newcommand {\mult }{\mathop {\rm mult}\nolimits }\)
\(\newcommand {\N }{\mathop {\rm N}\nolimits }\)
\(\newcommand {\lk }{\mathop {\rm lk}\nolimits }\)
\(\newcommand {\Pf }{\mathop {\rm Pf}\nolimits }\)
\(\newcommand {\sgn }{\mathop {\rm sgn}\nolimits }\)
\(\newcommand {\grad }{\mathop {\rm grad}\nolimits }\)
\(\newcommand {\lcm }{\mathop {\rm lcm}\nolimits }\)
\(\newcommand {\Ric }{\mathop {\rm Ric}\nolimits }\)
\(\newcommand {\Hess }{\mathop {\rm Hess}\nolimits }\)
\(\newcommand {\sn }{\mathop {\rm sn}\nolimits }\)
\(\newcommand {\cut }{\mathop {\rm cut}\nolimits }\)
\(\newcommand {\tr }{\mathop {\rm tr}\nolimits }\)
\(\newcommand {\codim }{\mathop {\rm codim}\nolimits }\)
\(\newcommand {\ind }{\mathop {\rm index}\nolimits }\)
\(\newcommand {\rad }{\mathop {\rm rad}\nolimits }\)
\(\newcommand {\Rep }{\mathop {\rm Rep}\nolimits }\)
\(\newcommand {\Lie }{\mathop {\rm Lie}\nolimits }\)
\(\newcommand {\Der }{\mathop {\rm Der}\nolimits }\)
\(\newcommand {\hgt }{\mathop {\rm ht}\nolimits }\)
\(\newcommand {\Ider }{\mathop {\rm Ider}\nolimits }\)
\(\newcommand {\id }{\mathop {\rm id}\nolimits }\)
2 Interpretations
If we work in the category of sets, this becomes the familiar Cantor’s Theorem. However we can also interpret this proof to give Godel’s Incompleteness Theorem and the solution to the Halting Problem.For the Halting Problem, \(X\) is a countable set of inputs, and a program is a map \(X \to \Omega \) as it takes an input and either halts or doesn’t. We label our countable number of programs so that \(X \cong \Omega ^X\) Now if there were a solution to the halting problem, the evaluation map \(X \times X \to \Omega \) is a program. But then our proof yields another program that halts iff it doesn’t halt.
For Gödel’s incompleteness theorem, \(X\) is the natural numbers \(\NN \), and a map \(\NN \to \Omega \) is a statement that depends on a natural number parameter (the value in \(\Omega \) is whether that statement is true or false). Then we have assumed that our formal system is strong enough such that we can have a Gödel numbering: i.e our statements can be indexed over the natural numbers in such a way that the formal system can answer the family of statements "Is this statement true on this natural number?" Then the diagonal construction leads to the statement "is this statement false", which is neither true nor false.