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}}\)
Mathematics LibreTexts

4.7: Summing Up, Looking Ahead

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

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

    The big concepts that we have introduced in this chapter are three. First is coding, both the idea behind it and the mechanism that we will use to accomplish it. Secondly, we have defined what it means to talk about the complexity of a formula, and introduced the collections of \(\Sigma\)-, \(\Pi\)-, and \(\Delta\)-formulas. Then, we reintroduced the collection of axioms \(N\), and we mentioned (but did not prove) that \(N\) is \(\Sigma\)-complete; \(N\) is strong enough to prove all \(\Sigma\)-sentences that are true in \(\mathfrak{N}\).

    Before use we have the path to Gödel's Incompleteness Theorem. But we should say "paths" rather than path. You, the reader, get to choose what happens next. If you would like to see a development of incompleteness that is based on formulas in \(\mathcal{L}_{NT}\), then continue on into Chapter 5. If, on the other hand, you are more interested in an argument that focuses on computations rather than formulas, skip Chapters 5 and 6 for now and move on to Chapter 7. Of course, on a second reading you should look over (at least briefly) the material that you skipped; there are insights and subtleties to be appreciated in each approach! We will bring things back together in Chapter 8 and point you toward further reading in Mathematical Logic that will introduce you to further results and other areas of study in this fascinating field. But first, on to Incompleteness!