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–?)
“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.)
“I had many problems in my conduct of the office being contrasted with President Kennedy’s conduct in the office, with my manner of dealing with things and his manner, with my accent and his accent, with my background and his background. He was a great public hero, and anything I did that someone didn’t approve of, they would always feel that President Kennedy wouldn’t have done that.”
—Lyndon Baines Johnson (1908–1973)