Арифметизация

Метод, применяемый в математич. логике для замены рассуждений о выражениях к.-л. логико-математич. языка рассуждениями о натуральных числах. С целью такой замены устанавливается к.-л. достаточно простое взаимно однозначное отображение множества всех слов (в алфавите рассматриваемого языка) в натуральный ряд; образ слова наз. его номером. Отношения и операции, определенные на словах, переходят при этом отображении в отношения и операции, определенные на номерах. Требование "достаточной простоты" отображения сводится к тому, чтобы нек-рые основные отношения (такие, как отношение вхождения одного слова в другое и т. п.) и операции (такие, как операция соединения слов и т. п.) переходили в отношения п операции, имеющие простую алгоритмич. природу (напр., оказывающиеся примитивно рекурсивными). В частности, если среди выражений рассматриваемого языка содержатся программы для нек-рого семейства вычислимых функций, А. естественно приводит к нумерации этого семейства (при к-рой номером функции считается номер всякой ее программы). Впервые А. была применена К. Гёделем [1] для доказательства неполноты формальной арифметики (см. Гё-деля теорема о неполноте). Именно, Гёдель поставил в соответствие буквам алфавита некоторые попарно различные натуральные числа и затем занумеровал слово номером ,где -число, поставленное в соответствие букве а есть i-е по порядку простое число. Так описанная нумерация слов наз. гёделевой; в широком смысле слова гёделевой наз. всякая нумерация слов, возникающая при А., при этом номера слов паз. пхгёделевыми номерами. В 1936 А. Чёрч [2] с помощью А. получил первый пример неразрешимой алгоритмич. проблемы арифметики. Термин "А." (в сочетании "А. анализа") употребляется также в литературе по основаниям математики для обозначения осуществленного в 19 в. построения теории действительных чисел с помощью теоретико-множественных конструкций, отправляющихся от натуральных чисел. Лит.:[1] Godel К., "Monatsh. Math, und Physik", 1931, Bd 38, № 1, S. 173-98; [2] Сhurсh A., "Amer. J. Math.", 1936, v. 58, № 2, p. 345-63; [3] Клини С. К., Введение в метаматематику, пер. с англ., М., 1957. В. А. Успенский.