АРИФМЕТИЗАЦИЯ

Расстановка ударений: АРИФМЕТИЗА`ЦИЯ

АРИФМЕТИЗАЦИЯ - метод, применяемый в математич. логике для замены рассуждений о выражениях к.-л. логико-математич. языка рассуждениями о натуральных числах. С целью такой замены устанавливается к.-л. достаточно простое взаимно однозначное отображение множества всех слов (в алфавите рассматриваемого языка) в натуральный ряд; образ слова наз. его номером. Отношения и операции, определенные на словах, переходят при этом отображении в отношения и операции, определенные на номерах. Требование «достаточной простоты» отображения сводится к тому, чтобы нек-рые основные отношения (такие, как отношение вхождения одного слова в другое и т. п.) и операции (такие, как операция соединения слов и т. п.) переходили в отношения и операции, имеющие простую алгоритмич. природу (напр., оказывающиеся примитивно рекурсивными). В частности, если среди выражений рассматриваемого языка содержатся программы для нек-рого семейства вычислимых функций, А. естественно приводит к нумерации этого семейства (при к-рой номером функции считается номер всякой ее программы).

Впервые А. была применена К. Гёделем [1] для доказательства неполноты формальной арифметики (см. Гёделя теорема о неполноте). Именно, Гёдель поставил в соответствие буквам алфавита некоторые попарно различные натуральные числа и затем занумеровал слово τ₁, ..., τ_n номером 2^t₁ ⋅ 3^t₂ ⋅... ⋅ р_n^t_n, где t_i - число, поставленное в соответствие букве τ_i, а p_i есть i-e по порядку простое число. Так описанная нумерация слов наз. гёделевой; в широком смысле слова гёделевой наз. всякая нумерация слов, возникающая при А., при этом номера слов наз. их гёделевыми номерами.

В 1936 А. Чёрч [2] с помощью А. получил первый пример неразрешимой алгоритмич. проблемы арифметики.

Термин «А.» (в сочетании «А. анализа») употребляется также в литературе по основаниям математики для обозначения осуществленного в 19 в. построения теории действительных чисел с помощью теоретико-множественных конструкций, отправляющихся от натуральных чисел.

Лит. : [1] Gödel К., «Monatsh. Math, und Physiko, 1931, Bd 38, № 1, S. 173-98; [2] Сhurсh A., «Amer. J. Math. », 1936, v. 58, № 2, p. 345-63; [3] Клини С. К., Введение в метаматематику, пер. с англ., М., 1957.

В. А. Успенский.

Источники:

1. Математическая Энциклопедия. Т. 1 (А - Г). Ред. коллегия: И. М. Виноградов (глав ред) [и др.] - М., «Советская Энциклопедия», 1977, 1152 стб. с илл.