On Formally Undecidable Propositions of Principia Mathematica and Related Systems
"Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I" ("On Formally Undecidable Propositions of Principia Mathematica and Related Systems I") is a paper in mathematical logic by Kurt Gödel. Submitted November 17, 1930, it was originally published in German in the 1931 volume of Monatshefte für Mathematik und Physik. Several English translations have appeared in print, and the paper has been included in two collections of classic mathematical logic papers. The paper contains Gödel's incompleteness theorems, now fundamental results in logic that have many implications for consistency proofs in mathematics. The paper is also known for introducing new techniques that Gödel invented to prove the incompleteness theorems.
This article is about the paper. For theorems proved in this paper, see Gödel's incompleteness theorems.Outline and key results[edit]
The main results established are Gödel's first and second incompleteness theorems, which have had an enormous impact on the field of mathematical logic. These appear as theorems VI and XI, respectively, in the paper.
In order to prove these results, Gödel introduced a method now known as Gödel numbering. In this method, each sentence and formal proof in first-order arithmetic is assigned a particular natural number. Gödel shows that many properties of these proofs can be defined within any theory of arithmetic that is strong enough to define the primitive recursive functions. (The contemporary terminology for recursive functions and primitive recursive functions had not yet been established when the paper was published; Gödel used the word rekursiv ("recursive") for what are now known as primitive recursive functions.) The method of Gödel numbering has since become common in mathematical logic.
Because the method of Gödel numbering was novel, and to avoid any ambiguity, Gödel presented a list of 45 explicit formal definitions of primitive recursive functions and relations used to manipulate and test Gödel numbers. He used these to give an explicit definition of a formula Bew(x) that is true if and only if x is the Gödel number of a sentence φ and there exists a natural number that is the Gödel number of a proof of φ. The name of this formula derives from Beweis, the German word for proof.
A second new technique invented by Gödel in this paper was the use of self-referential sentences. Gödel showed that the classical paradoxes of self-reference, such as "This statement is false", can be recast as self-referential formal sentences of arithmetic. Informally,
the sentence employed to prove Gödel's first incompleteness theorem says "This statement is not provable." The fact that such self-reference can be expressed within arithmetic was not known until Gödel's paper appeared; independent work of Alfred Tarski on his indefinability theorem was conducted around the same time but not published until 1936.
In footnote 48a, Gödel stated that a planned second part of the paper would establish a link between consistency proofs and type theory (hence the "I" at the end of the paper's title, denoting the first part), but Gödel did not publish a second part of the paper before his death. His 1958 paper in Dialectica did, however, show how type theory can be used to give a consistency proof for arithmetic.