Skip to main content
\(\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}}\)
[ "article:topic", "authorname:learykristiansen", "showtoc:no" ]
Mathematics LibreTexts

5.13: Summing Up, Looking Ahead

  • Page ID
    10073
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

    Well, in all likelihood you are exhausted at this point. This chapter has been full of dense, technical arguments with imposing definition piled upon imposing definition. We have established our axioms, discussed representable sets, and talked about \(\Delta\)-definitions. You have just finished wading through an unending stream of \(\Delta\)-definitions that culminated with the formula \(Deduction \left( c, f \right)\) which holds if and only if \(c\) is a code for a deduction of the formula with Gödel number \(f\). We have succeeded in coding up our deductive theory inside of number theory.

    Let us reiterate this. If you look at that formula \(Deduction\), what it looks like is a disjunction of a lot of equations and inequalities. Everything is written in the language \(\mathcal{L}_{NT}\), so everything in that formula is of the form \(SSS0 < SS0 + x\) (with, it must be admitted, rather more \(S\)'s than shown here). Although we have given these formulas names which suggest that they are about formulas and terms and tautologies and deductions, the formulas are formulas of elementary number theory, so the formulas don't know that they are about anything beyond whether this number is bigger than that number, no matter how much you want to anthropomorphize them. The interpretation of the numbers as standing for formulas via the scheme of Gödel numbering is imposed on those numbers by us.

    The next chapter brings us to the statement and the proof of Gödel's Incompleteness Theorem. To give you a taste of things to come, notice that if we define the statement

    \(Thm_N \left( f \right) =\)

    \[\left( \exists c \right) \left( Deduction \left( c, f \right) \right),\]

    then \(Thm_N \left( f \right)\) should hold if and only if \(f\) is the Gödel number of a formula that is a theorem of \(N\). We are sure that you notice that \(Thm_N\) is not a \(\Delta\)-formula, and there is no way to fix that - we cannot bound the length of a deduction of a formula. But \(Thm_N\) is a \(\Sigma\)-formula, and Proposition 5.3.13 tells us that true \(\Sigma\)-sentences are provable. That will be one of the keys to Gödel's proof.

    Well, if \(90\%\) of the iceberg is under water, we've covered that. Now it is time to examine that glorious \(10\%\) that is left.