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

- метод, применяемый в математич. логике для замены рассуждений о выражениях к.-л. логико-математич. языка рассуждениями о натуральных числах. С целью такой замены устанавливается к.-л. достаточно простое взаимно однозначное отображение множества всех слов (в алфавите рассматриваемого языка) в натуральный ряд; образ слова наз. его номером. Отношения и операции, определенные на словах, переходят при этом отображении в отношения и операции, определенные на номерах. Требование "достаточной простоты" отображения сводится к тому, чтобы нек-рые основные отношения (такие, как отношение вхождения одного слова в другое и т. п.) и операции (такие, как операция соединения слов и т. п.) переходили в отношения п операции, имеющие простую алгоритмич. природу (напр., оказывающиеся примитивно рекурсивными). В частности, если среди выражений рассматриваемого языка содержатся программы для нек-рого семейства вычислимых функций, А. естественно приводит к нумерации этого семейства (при к-рой номером функции считается номер всякой ее программы). Впервые А. была применена К. Гёделем [1] для доказательства неполноты формальной арифметики (см. Гё-деля теорема о неполноте). Именно, Гёдель поставил в соответствие буквам алфавита некоторые попарно различные натуральные числа и затем занумеровал слово [img: http://localhost:8080/file/010131-49.jpg] номером [img: http://localhost:8080/file/010131-50.jpg],где [img: http://localhost:8080/file/010131-51.jpg] -число, поставленное в соответствие букве [img: http://localhost:8080/file/010131-52.jpg] а [img: http://localhost:8080/file/010131-53.jpg] есть i-е по порядку простое число. Так описанная нумерация слов наз. гёделевой; в широком смысле слова гёделевой наз. всякая нумерация слов, возникающая при А., при этом номера слов паз. пхгёделевыми номерами. В 1936 А. Чёрч [2] с помощью А. получил первый пример неразрешимой алгоритмич. проблемы арифметики. Термин "А." (в сочетании "А. анализа") употребляется также в литературе по основаниям математики для обозначения осуществленного в 19 в. построения теории действительных чисел с помощью теоретико-множественных конструкций, отправляющихся от натуральных чисел.