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:
“The history of his present majesty, is a history of unremitting injuries and usurpations ... all of which have in direct object the establishment of an absolute tyranny over these states. To prove this, let facts be submitted to a candid world, for the truth of which we pledge a faith yet unsullied by falsehood.”
—Thomas Jefferson (1743–1826)
“We know only a single science, the science of history. One can look at history from two sides and divide it into the history of nature and the history of men. However, the two sides are not to be divided off; as long as men exist the history of nature and the history of men are mutually conditioned.”
—Karl Marx (1818–1883)
“It is the true office of history to represent the events themselves, together with the counsels, and to leave the observations and conclusions thereupon to the liberty and faculty of every man’s judgement.”
—Francis Bacon (1561–1626)