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 the, statement of and/or statement:
“Eroticism has its own moral justification because it says that pleasure is enough for me; it is a statement of the individual’s sovereignty.”
—Mario Vargas Llosa (b. 1936)
“Truth is used to vitalize a statement rather than devitalize it. Truth implies more than a simple statement of fact. “I don’t have any whisky,” may be a fact but it is not a truth.”
—William Burroughs (b. 1914)
“Eroticism has its own moral justification because it says that pleasure is enough for me; it is a statement of the individual’s sovereignty.”
—Mario Vargas Llosa (b. 1936)