In mathematical logic, the diagonal lemma, also known as the diagonalization lemma, the self-reference lemma or the fixed point theorem, establishes the existence of self-referential sentences in certain formal theories. Kurt Godel used a particular instance of it in 1931 to construct his proof of the incompleteness theorems, Alfred Tarski used it in 1933 to prove his undefinability theorem, and Rudolf Carnap was the first to publish the lemma at a general level in 1934; its name refers to Cantor's diagonal argument in set theory and number theory.
Facts
StatementFor a formal theory T able to represent every computable function, and a formula phi(x) with one free variable, the diagonal lemma produces a sentence psi such that T proves psi if and only if T proves phi applied to the Godel number of psi, so psi effectively asserts phi about its own Godel number. 1 Proof YearRudolf Carnap published the lemma at this level of generality in 1934. Kurt Godel had already used one specific instance of it in his 1931 incompleteness paper without naming it as a separate lemma; see the paired proved-by edge below. Classification
Statement Form Connections
Proved By
Why this is disputed. Godel used one specific instance of this lemma in his 1931 incompleteness paper without naming it as a separate result; Rudolf Carnap, who is not yet a live mathematician entity in this atlas, published the lemma at a general level in 1934, so crediting sole proof to Godel is disputed rather than settled.
Source Diagonal Lemma (Wikipedia)
Sources
1. Diagonal Lemma (Wikipedia)
Wikimedia FoundationLede
In mathematical logic, the diagonal lemma (also known as diagonalization lemma, self-reference lemma or fixed point theorem) establishes the existence of self-referential sentences in certain formal theories.
History section
In 1934, Rudolf Carnap was the first to publish the diagonal lemma in some level of generality
Lead section, statement-form reference
In mathematical logic, the diagonal lemma (also known as diagonalization lemma, self-reference lemma or fixed point theorem) establishes the existence of self-referential sentences in certain formal theories.
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.