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:
“They were more than hostile. In the first place, I was a south Georgian and I was looked upon as a fiscal conservative, and the Atlanta newspapers quite erroneously, because they didn’t know anything about me or my background here in Plains, decided that I was also a racial conservative.”
—Jimmy Carter (James Earl Carter, Jr.)
“... 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)