Background
Let N be the set of natural numbers. A theory T represents the computable function f : N→N if there exists a formula δ(x,y) in the language of T such that for each n, T proves
- (∀y) .
Here n is the numeral corresponding to the natural number n, which is defined to be the closed term 1+ ··· +1 (n ones), and f(n) is the numeral corresponding to f(n).
The diagonal lemma also requires that there be a systematic way of assigning to every formula θ a natural number #(θ) called its Gödel number. Formulas can then be represented within the theory by the numerals corresponding to their Gödel numbers.
The diagonal lemma applies to theories capable of representing all primitive recursive functions. Such theories include Peano arithmetic and the weaker Robinson arithmetic. A common statement of the lemma (as given below) makes the stronger assumption that the theory can represent all computable functions.
Read more about this topic: Diagonal Lemma
Famous quotes containing the word background:
“... every experience in life enriches one’s background and should teach valuable lessons.”
—Mary Barnett Gilson (1877–?)
“Pilate with his question “What is truth?” is gladly trotted out these days as an advocate of Christ, so as to arouse the suspicion that everything known and knowable is an illusion and to erect the cross upon that gruesome background of the impossibility of knowledge.”
—Friedrich Nietzsche (1844–1900)
“In the true sense one’s native land, with its background of tradition, early impressions, reminiscences and other things dear to one, is not enough to make sensitive human beings feel at home.”
—Emma Goldman (1869–1940)