Statement of The Lemma
Let T be a first-order theory in the language of arithmetic and capable of representing all computable functions. Let ψ be a formula in the theory T with one free variable. The diagonal lemma states that there is a sentence φ such that φ ↔ ψ(#(φ)) is provable in T.
Intuitively, φ is a self-referential sentence saying that φ has the property ψ. The sentence φ can also be viewed as a fixed point of the operation assigning to each formula θ the sentence ψ(#(θ)). The sentence φ constructed in the proof is not literally the same as ψ(#(φ)), but is provably equivalent to it in the theory T.
Read more about this topic: Diagonal Lemma
Famous quotes containing the words statement of and/or statement:
“Most personal correspondence of today consists of letters the first half of which are given over to an indexed statement of why the writer hasn’t written before, followed by one paragraph of small talk, with the remainder devoted to reasons why it is imperative that the letter be brought to a close.”
—Robert Benchley (1889–1945)
“If we do take statements to be the primary bearers of truth, there seems to be a very simple answer to the question, what is it for them to be true: for a statement to be true is for things to be as they are stated to be.”
—J.L. (John Langshaw)