Cтраница 2
Иногда в наших доказательствах непротиворечивости используется один вид полной индукции, который не формализуется схемой индукции рекурсивной арифметики. Этот выход за рамки рекурсивной арифметики связан с тем, что в наших формулировках и доказательствах время от времени встречаются такие допущения, в которых говорится об истинности некоторых всеобщих предложений; таковы, например, предположение о невыводимости или о неопровержимости какой-либо формулы, или предположение о непротиворечивости какого-либо формализма, или же предположение о верифицируемоети какой-либо формулы, что, согласно определению, означает, что эта формула при любой замене свободных переменных цифрами оказывается истинной. Любое высказывание, содержащее такого рода предположение, представляет трудности и для финитного понимания. Как известно, финитное допущение всегда относится к какой-либо наглядно характеризуемой ситуации. Но истинность всеобщего предложения не может считаться таковой. Правда, вместо предположения, что рассматриваемое всеобщее предложение истинно, можно взять предположение о том, что истинность этого предложения установлена. [16]
Таким образом, она является дальнейшем шагом по сравнению с работой Сколема, который показал, что рекурсивную арифметику можно формализовать без кванторов. [17]
С другой стороны, аксиомы системы ( Z) выводятся в упомянутом ранее формализме2), получающемся расширением рекурсивной арифметики. [18]
Мы действительно можем легко показать, что натуральные числа не составляют наибольшего класса объектов, которые удовлетворяют аксиомам рекурсивной арифметики. [19]
Термин рекурсивный мы будем здесь употреблять в том же самом смысле, в каком он употреблялся нами в рекурсивной арифметике. Так, под рекурсивной функцией мы будем понимать такую функцию, которая может быть определена при помощи примитивных рекурсий. [20]
Рекурсивный анализ - это теория функций в поле рациональных чисел, содержащая лишь свободные переменные и основанная на рекурсивной арифметике. Он не содержит никаких предварительных логических предположений и развивается от определения к теореме только при помощи схем вывода. [21]
Доказательство состоит из ряда лемм, в которых локализуются шаги перестройки выводов; для этого вводится несколько вспомогательных формализации примитивно рекурсивной арифметики. [22]
В частности, теорема эта - на что указали Гедель и Крайзел - может быть распространена на формализмы без связанных переменных-например, на рекурсивную арифметику. [23]
Поэтому каждый обладающий достаточными изобразительными возможностями и достаточно четко очерченный формализм является дедуктивно незавершенным; точнее говоря, существуют предложения, причем даже предложения рекурсивной арифметики, которые формулируемы в нем, но дедуктивно неразрешимы. Если же удастся доказать непротиворечивость этого формализма F, то найдется такое предложение рекурсивной арифметики, которое хотя и будет доказуемым, но не будет формально доказуемым в F. Действительно, если формализм F непротиворечив, то предложение, изображаемое рассматриваемым нами равенством f ( m) 0, в силу доказанной теоремы о неполноте будет истинным. [24]
Это гипотетическое отношение, которое в рамках финитного рассмотрения допустимо как способ вывода следствия, хотя и не как финитное предложение, в рамках рекурсивной арифметики не может быть изображено какой-либо формулой. [25]
Добавив к элементарному исчислению со свободными переменными схему примитивной рекурсии и схему индукции вместе с аксиомами равенства и аксиомой 0 О, мы получим формализм рекурсивной арифметики. [26]
В том частном случае, когда в исходном выводе нет кванторов существования, можно с помощью рассуждения, аналогичного тому, которое было проведено при рассмотрении рекурсивной арифметики), показать, что заключительная формула данного вывода является верифицируемой, а поскольку она является нумерической, - то и истинной. Таким образом, в рассматриваемом частном случае доказательство закончено. [27]
Таким образом, мы можем каждую из получаемых по схеме ( fi) формул вывести из формул ( ij), ( i2) и ( ( is), пользуясь средствами рекурсивной арифметики и добавляя к ним одни лишь явные определения. [28]
Что касается изображения рекурсивных функций в формализме ( Z), то для этих функций в ( Z) могут быть взяты те же самые символы, которые ранее использовались нами в рекурсивной арифметике. [29]
Тем же самым способом с применением рассуждений, проведенных нами в § 1 данной главы1), можно показать, что утверждения нашей нп-теоремы остаются в силе и для формализма, который получается из рекурсивной арифметики в результате присоединения к ней формул и схем для кванторов, а также е-символа и е-формулы 2), поскольку в качестве распределения значений для элементарных формул без переменных ( в данном случае это будут одни только равенства) мы берем такое распределение, которое индуцируется выделенной оценкой истинностных значений для равенства и процедурой вычисления значений рекурсивных функций. [30]