Gödels theorem simplified
Hem / Historia, Vetenskap & Forskning / Gödels theorem simplified
That is, numerals which name 1, 2, 3, … are \(0', 0'', 0''',\ldots\) and are abbreviated by \(\overline{1}\), \(\overline{2}\), \(\overline{3}\), …
In his original proof, Gödel used his specific notion of \(\omega\)-consistency, and for some purposes, it is still convenient to follow Gödel’s original approach.
The incompleteness theorems. In the latter case, the set is called “recursively enumerable” (r.e.), that is to say, it can be effectively generated, or it is “semi-decidable.” It is a fundamental result of the theory of computability (or “the theory of recursive functions”) that there are semi-decidable sets, sets which can be effectively generated (i.e., are recursively enumerable), but are not decidable (i.e., not recursive).
Therefore, because of the second incompleteness theorem, the principle itself cannot be provable in PA (Gentzen 1936).
Ramsey’s theorem is a result in infinitary combinatorics, established by Frank Ramsey (1930), and deals with possibilities of “colouring” for certain graphs.
Gödel’s theorem does not merely claim that such statements exist: the method of Gödel’s proof explicitly produces a particular sentence that is neither provable nor refutable in \(F\); the “undecidable” statement can be found mechanically from a specification of \(F\).
\]
It is obvious how all these notions are generalized to many-place relations. The author and SEP editors would like to thank Richard O’Callaghan for bringing to our attention that, in an earlier version of the supplement on the Diagonalization Lemma, the definition of the substitution function, although standard, didn’t suffice for the purposes of the proof.
Republished as A Decision Method for Elementary Algebra and Geometry, 2nd ed. However, the applicability of the incompleteness theorems can be dramatically extended outside the language of first-order arithmetic and its extensions, when it is noted that all that is needed is that weak theories such as Q, or PRA, can be interpreted in the system in question.
(eds.), Oxford: Oxford University Press.
Moving now to stronger theories beyond PA, one can mention, for example, Kruskal’s Theorem.
5. Perhaps an even cleaner example is Goodstein’s theorem, due to Reuben Goodstein (1944), which is purely number theoretic in nature. In 1939, Hilbert and Bernays’ second volume of Die Grundlagen der Mathematik appeared, including a detailed proof of the second incompleteness theorem.
Let us denote the formula which strongly represents this relation in \(F\) itself as \(\Prf_F (x, y)\). He obtained abstract versions of incompleteness results apparently already in 1922. Gödel's result showed that Hilbert's goal of creating a complete and consistent formal system was unattainable.
The theorem also highlights the importance of rigor and caution in mathematical reasoning.
Non-standard models have since then become a rich research area in mathematical logic (see, e.g., Boolos & Jeffrey 1989: Ch. 17; Kaye 1991).
3. Among the formulas of the language of arithmetic, he isolates what he calls PR- and RE-formulas; the former correspond to the canonical primitive recursive (PR) definitions in arithmetic, and the latter to existential generalizations of the former.
126–141.
The latter, however, is impossible, as it has already been shown. Secondly, Feferman looks for a suitable constraint for presenting the axioms.
In the first and loose statements of the incompleteness theorems given above, the vague requirement that “a certain amount of elementary arithmetic can be carried out” occurred.
A theory \(F\) is called essentially undecidable if every consistent extension of it in the language of \(F\) is undecidable.