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:
“Silence is the universal refuge, the sequel to all dull discourses and all foolish acts, a balm to our every chagrin, as welcome after satiety as after disappointment; that background which the painter may not daub, be he master or bungler, and which, however awkward a figure we may have made in the foreground, remains ever our inviolable asylum, where no indignity can assail, no personality can disturb us.”
—Henry David Thoreau (1817–1862)
“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.)
“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)