Diagonal Lemma - History

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:

    “There is no example in history of a revolutionary movement involving such gigantic masses being so bloodless.”
    —Leon Trotsky (1879–1940)

    “The only thing worse than a liar is a liar that’s also a hypocrite!
    There are only two great currents in the history of mankind: the baseness which makes conservatives and the envy which makes revolutionaries.”
    —Edmond De Goncourt (1822–1896)