Cтраница 1
Рекурсивная арифметика на такой основе не развивается детально в той статье: это основная задача настоящей работы. Цель состоит в том, чтобы показать адекватность этой формулировки рекурсивной арифметики: конечный результат - это доказательство того, что рассматриваемая система эквивалентна системе Гильберта и Бернайса. [1]
Рекурсивная арифметика, такая, какой она была введена в 2.1, непротиворечива в том смысле, что мы можем показать, что если р д, где р и q - определенные цифры, является доказуемым равенством, то р и q - одна и та же цифра. [2]
Элементарными формулами рекурсивной арифметики являются равенства между термами, а класс всех формул строится из элементарных формул с помощью операций исчисления высказываний. Термами являются свободные цифровые переменные, знак 0 и знаки для функций. [3]
В следующем далее изложении рекурсивной арифметики мы показываем, что логику и арифметику можно строить одновременно в исчислении равенств со свободными переменными, в котором единственными утверждениями являются равенства вида а bt где а и & означают функциональные выражения. С помощью этого исчисления равенств можно построить логику и арифметику с самого начала, с полной строгостью и со всеми деталями на значительно более элементарном уровне, чем было возможно до сих пор, и есть надежда, что первая половина этой книги окажется до Ступной первокурснику университета, специализирующемуся по математике. [4]
Гедель показал, что средств рекурсивной арифметики вполне достаточно для математического построения такой модели и для ее формализации. Используемый им метод арифметизации состоит в арифметическом имитировании линейного расположения знаков в формулах формализованной математики. Действительно, логическую и математическую символику мы всегда можем выбрать таким образом, чтобы расположение символов и переменных в формулах было строго линейным. [5]
Этот терм не является термом рекурсивной арифметики. Но для этого надо было бы указать какую-нибудь оценку для i; однако получение такой оценки в данном случае себя не оправдывает. [6]
Логический формализм, лежащий в основе рекурсивной арифметики, представляет собой элементарное исчисление со свободными переменными. К нему в качестве исходных формул добавляются аксиомы равенства и формула О Ф О, а в качестве схем - схема индукции и схема примитивной рекурсии. Средств этого формализма уже достаточно для того, чтобы с их помощью можно было изобразить различные понятия, утверждения и доказательства элементарной арифметики. С другой стороны, этот формализм еще допускает определенное финитное истолкование. Но и без прямого обращения к этому истолкованию мы легко смогли доказать непротиворечивость этого формализма и даже установить, что всякая выводимая в нем формула, не содержащая формульных переменных, при любой замене входящих в нее свободных индивидных переменных цифрами после вычисления значений соответствующих функций переходит в истинную формулу. [7]
Формализм F содержит термы и формулы рекурсивной арифметики), не считая, быть может, тех, в которых содержатся формульные переменные. [8]
Среди прочего, он должен знать примитивно рекурсивную арифметику. [9]
Таким образом, теперь мы уже выразили на языке рекурсивной арифметики все глаьные понятия, необходимые для определения вывода. [10]
Любое вычисление значения рекурсивного терма без переменных в рамках рекурсивной арифметики может быть формализовано выводом равенства, указывающего результат этого вычисления. В этом выводе в качестве исходных формул используются рекурсивные равенства для рекурсивных функций, прямо или косвенно фигурирующих в этом терме, и аксиомы равенства. При этом использование этих формул производится с помощью подстановок и схем заключения. [11]
В самой теории алгоритмов можно выделить исследования в области рекурсивной арифметики, куда входят различные классификации рекурсивных и рекурсивно перечислимых множеств) степени неразрешимости рекурсивно перечислимых множеств, исследования сложности записи алгоритмов и сложности алгоритмич. Обширным развивающимся разделом теории алгоритмов является теория нумераций. [12]
В самой теории алгоритмов можно выделить исследования в области рекурсивной арифметики, куда входят различные классификации рекурсивных и рекурсивно-перечислимых множеств, степени неразрешимости ре-курсивно-перечислимых множеств, исследования сложности записи алгоритмов и сложности алгоритмич. [13]
Тем самым мы попадаем в сферу действия того арифметического формализма, который получается из рекурсивной арифметики в результате присоединения исчисления предикатов ( в полном объеме), а также распространения на расширенную область формул схемы индукции и добавления ц-символа с относящимися к нему формулами ( iij), ( ц2) и ( мз) 2) - Этот формализм равносилен рассмотренному в гл. [14]
Третьей системой, которая была развита для того, чтобы избавиться от рефлексивного парадокса, была рекурсивная арифметика Скодема. [15]