History
The diagonal lemma is closely related to Kleene's recursion theorem in computability theory, and their respective proofs are similar.
The lemma is called "diagonal" because it bears some resemblance to Cantor's diagonal argument. The terms "diagonal lemma" or "fixed point" do not appear in Kurt Gödel's epochal 1931 article, or in Tarski (1936). Carnap (1934) was the first to prove that for any formula ψ in a theory T satisfying certain conditions, there exists a formula φ such that φ ↔ ψ(#(φ)) is provable in T. Carnap's work was phrased in alternate language, as the concept of computable functions was not yet developed in 1934. Mendelson (1997, p. 204) believes that Carnap was the first to state that something like the diagonal lemma was implicit in Gödel's reasoning. Gödel was aware of Carnap's work by 1937.
Read more about this topic: Diagonal Lemma
Famous quotes containing the word history:
“America is, therefore the land of the future, where, in the ages that lie before us, the burden of the World’s history shall reveal itself. It is a land of desire for all those who are weary of the historical lumber-room of Old Europe.”
—Georg Wilhelm Friedrich Hegel (1770–1831)
“I think that Richard Nixon will go down in history as a true folk hero, who struck a vital blow to the whole diseased concept of the revered image and gave the American virtue of irreverence and skepticism back to the people.”
—William Burroughs (b. 1914)