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

- метод, применяемый в математич. Логике для замены рассуждений о выражениях к.-л. Логико-математич. Языка рассуждениями о натуральных числах. С целью такой замены устанавливается к.-л. Достаточно простое взаимно однозначное отображение множества всех слов (в алфавите рассматриваемого языка) в натуральный ряд. Образ слова наз. Его номером. Отношения и операции, определенные на словах, переходят при этом отображении в отношения и операции, определенные на номерах. Требование "достаточной простоты" отображения сводится к тому, чтобы нек-рые основные отношения (такие, как отношение вхождения одного слова в другое и т. П.) и операции (такие, как операция соединения слов и т. П.) переходили в отношения п операции, имеющие простую алгоритмич.

Природу (напр., оказывающиеся примитивно рекурсивными). В частности, если среди выражений рассматриваемого языка содержатся программы для нек-рого семейства вычислимых функций, А. Естественно приводит к нумерации этого семейства (при к-рой номером функции считается номер всякой ее программы). Впервые А. Была применена К. Гёделем [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. В. А. Успенский.