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
the number
,
where
is the number corresponding to the letter
,
and
is the
-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
for the denotation of the creation of the theory
of real numbers in the
19th century
using
set-theoretic constructions, starting from the natural numbers.