Arithmetization

A method used in mathematical logic for replacing a reasoning on the expressions of some logico-mathematical language by reasonings on natural numbers. For this purpose the replacement is constructed by some sufficiently simple one-to-one mapping of the set of all words (in the alphabet of the language under consideration) into the natural number sequence. The image of a word is called its number. Relations between and operations defined on words are transformed by this mapping into relations between and operations on natural numbers. The requirement of a "sufficiently simple" mapping leads to the fact that some basic relations (such as the relation of imbedding of one word into another, etc.) and some operations (like the operation of concatenation of words, etc.) are transformed into relations and operations having a simple algorithmic nature (e.g. are primitive recursive). In particular, if among the expressions of the language under consideration there exist programs for some family of computable functions (cf. Computable function), arithmetization naturally leads to an enumeration of this family (in which for the number of each function is taken the number of its program).

The first arithmetization was constructed by K. Gödel [1] for the proof of the incompleteness of formal arithmetic (cf. Gödel incompleteness theorem). More precisely, Gödel put the letters of the alphabet in correspondence with some, pairwise different, natural numbers and attached to the word $\tau_1\cdots\tau_n$ the number $2^{t_1}\dotsm p_n^{t_n}$, where $t_i$ is the number corresponding to the letter $\tau_i$, and $p_i$ is the $i$-th prime number in the natural number sequence. Such an enumeration is called a Gödel enumeration. In a broad sense every enumeration of words arising from arithmetization is called a Gödel enumeration and the number corresponding to a word is called its Gödel number.

In 1936 A. Church used arithmetization to obtain the first example of an unsolvable algorithmic problem of arithmetic.

The term "arithmetization" (in the phrase "arithmetization of analysis" ) is also used in the literature on the foundations of mathematics to denote the creation of the theory of real numbers in the 19th century using set-theoretic constructions, starting from the natural numbers.

References

[1]	K. Gödel, "Ueber formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I" Monatsh. Math. Physik , 38 (1931) pp. 178–198
[2]	A. Church, "An unsolvable problem of elementary number theory" Amer. J. Math. , 58 (1936) pp. 345–363
[3]	S.C. Kleene, "Introduction to metamathematics" , North-Holland (1951)

References

[a1]	C. Smorinsky, "The incompleteness theorems" J. Barwise (ed.) , Handbook of mathematical logic , North-Holland (1977) pp. 821–866