4.3: The Roadmap to Incompleteness

Last updated
Save as PDF

Page ID: 9702

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

At the end of the day, we will want to be looking at this true-in-\(\mathfrak{N}\) \(\Pi\)-formula \(\sigma\) that we have constructed and be able to say to it, "There is no deduction of you." The construction of the formula \(\sigma\) will involve rather detailed analysis of the collections of deductions, so it will be convenient, if initially messy, to have a way to translate deductions into natural numbers. Thus for example, rather than saying "This long sequence of formulas is a deduction of the formula \(0 = 1\)", we could say "The number 42 is a code for a deduction of \(0 = 1\)."

The other advantage of having this coding is that it will allow us to code up statements about numbers that code up statements. For example, it might be the case that the number 24601 is a code for the statement "The number 42 is a code for a deduction of \(0 = 1\)." Or even (and this is the key idea) 24601 might be the code for the statement "There is no number that is a code for a deduction of the formula for which I am the code." The rather messy details of this will be covered in Chapter 6.

This all hinges on the facts that it is easy to code statements as numbers and decode numbers to see what statements they encode. Also, it is easy to check whether a potential deduction is, in fact, a deduction. Recall that a deduction is nothing more than a finite sequence of formulas, each one of which is either an axiom or follows from previous formulas in the sequence via a rule of inference. Thus, once we decide on a way to code formulas and to code sequences of formulas, it will not be a problem to examine a number and decide if that number codes up a deduction or not. Thus our path forward will be to fix our coding scheme, prove that the coding is nice, use the coding scheme in order to construct the formula \(\sigma\), and then prove that \(\sigma\) is both true and not provable. This route to the Incompleteness Theorem is followed in Chapters 5 and 6.