Рекурсивная арифметика - Большая Энциклопедия Нефти и Газа, статья, страница 3
Прошу послать меня на курсы повышения зарплаты. Законы Мерфи (еще...)

Рекурсивная арифметика

Cтраница 3


Остается нерешенным вопрос о том, можно ли доказательству, которое здесь представлено схематически в довольно сыром виде, придать такую форму, чтобы оказалась возможной его формализация при помощи какой-либо из схем расширенной таким образом рекурсивной арифметики.  [31]

I обобщения схемы индукции, дающие частичную компенсацию за ограничения, наложенные на эту схему, тоже согласуются с нашей нп-теоремой, потому что они, как мы уже установили1), сводятся при помощи примитивных рекурсий к обычной схеме индукции нашей рекурсивной арифметики.  [32]

Высказывание число т является номером некоторой последовательности выражений из F, являющейся выводом выражения с номером п-о с помощью нумерации конечных последовательностей выражений из F, получающейся из нумерации выражений из F путем использования разложения целых чисел 52 на простые множители, изображается двуместным рекурсивным предикатом и, тем самым, в формализме рекурсивной арифметики оно выражается некоторой рекурсивной формулой2) 33 ( т, п), у которой тип суть единственные входящие в нее переменные.  [33]

Иногда в наших доказательствах непротиворечивости используется один вид полной индукции, который не формализуется схемой индукции рекурсивной арифметики. Этот выход за рамки рекурсивной арифметики связан с тем, что в наших формулировках и доказательствах время от времени встречаются такие допущения, в которых говорится об истинности некоторых всеобщих предложений; таковы, например, предположение о невыводимости или о неопровержимости какой-либо формулы, или предположение о непротиворечивости какого-либо формализма, или же предположение о верифицируемоети какой-либо формулы, что, согласно определению, означает, что эта формула при любой замене свободных переменных цифрами оказывается истинной. Любое высказывание, содержащее такого рода предположение, представляет трудности и для финитного понимания. Как известно, финитное допущение всегда относится к какой-либо наглядно характеризуемой ситуации. Но истинность всеобщего предложения не может считаться таковой. Правда, вместо предположения, что рассматриваемое всеобщее предложение истинно, можно взять предположение о том, что истинность этого предложения установлена.  [34]

Разумеется, во многих случаях оказывается, что этого формализма уже недостаточно для проведения требующейся нам формализации. Ряд методов, выходящих за пределы рекурсивной арифметики ( в первоначальном смысле этого слова), был рассмотрен нами уже в гл.  [35]

Всякая формула этого формализма представляет собой равенство между термами. В качестве термов мы берем, во-первых, термы рекурсивной арифметики ( рекурсивные терм ы), с тем, однако, ограничением, что используемые функциональные знаки берутся только одноместными и двуместными. В-третьих, термами считаются выражения, представляющие собой введенные посредством явных определений функциональные знаки с термами в качестве аргументов.  [36]

Рекурсивная арифметика на такой основе не развивается детально в той статье: это основная задача настоящей работы. Цель состоит в том, чтобы показать адекватность этой формулировки рекурсивной арифметики: конечный результат - это доказательство того, что рассматриваемая система эквивалентна системе Гильберта и Бернайса.  [37]

Поэтому каждый обладающий достаточными изобразительными возможностями и достаточно четко очерченный формализм является дедуктивно незавершенным; точнее говоря, существуют предложения, причем даже предложения рекурсивной арифметики, которые формулируемы в нем, но дедуктивно неразрешимы. Если же удастся доказать непротиворечивость этого формализма F, то найдется такое предложение рекурсивной арифметики, которое хотя и будет доказуемым, но не будет формально доказуемым в F. Действительно, если формализм F непротиворечив, то предложение, изображаемое рассматриваемым нами равенством f ( m) 0, в силу доказанной теоремы о неполноте будет истинным.  [38]

Эта теорема может быть распространена и на формализмы несколько иного типа. Мы не обязательно должны требовать, чтобы формализм F содержал в себе формулы арифметического формализма непосредственно; вполне достаточно, чтобы соотношения рекурсивной арифметики как-то были выражены в нем с помощью соответствующих выводимых формул.  [39]

Этот замечательный результат, который был открыт Куртом Геделем в 1931 году, наводит на мысль о том, что натуральные числа, возможно, не являются единственным классом объектов, для которых доказуемые формулы из М верифицируемы, и что, возможно, существует класс объектов, который включает все натуральные числа и, кроме них, другие объекты, для которых доказуемые формулы М верифицируемы. То, что такой класс на самом деле существует, было действу тельно установлено через три года после результата Ге-деля Торальфом Сколемом, создателем рекурсивной арифметики, который показал ( независимо от методов и результатов Геделя), что не только системы вроде М и М, но всякая формализация арифметики не может полностью характеризовать понятие числа и допускает в качестве значений числовых переменных класс объектов такой, что все натуральные числа являются лишь его начальным сегментом.  [40]

Можно не требовать, чтобы рекурсивные функции были непосредственно изобразимы в F. Достаточно требовать некоторой заменимости этих функций, наподобие того, как это было сделано при замене функциональных знаков соответствующими предикатными символами или при замене в формализме ( Z) равенств рекурсивной арифметики соответствующими формулами.  [41]

Однако во многих случаях это выглядит неестественным, и нам остается просто-напросто признать, что мы вынуждены сделать границы финитных рассмотрений несколько размытыми. Первоначальное более узкое понятие финитного высказывания в области арифметики состоит в том, что в качестве финитных арифметических высказываний допускаются лишь такие высказывания, которые либо сами изображаются в формализме рекурсивной арифметики с добавлением, быть может, некоторых символов для конкретных вычислимых арифметических функций ( одного или нескольких аргументов), однако без использования формульных переменных, либо имеют некоторую усиленную интерпретацию с помощью высказываний, изобразимых в таком формализме.  [42]

Далее, мы выяснили, что к этому формализму, не нарушая применимости нп-теоремы, можно добавить: 1) схему индукции для формул без связанных переменных, 2) схемы рекурсий рекурсивной арифметики и 3) аксиомы равенства для любой вновь вводимой функции.  [43]

Таким образом, у () для всех п и у ( п п для некоторых п, если только имеется значение п, для которого g ( n) Q. Покажем, что доказательство рекурсивной сходимости ап составляет разрешающую процедуру для равенства g ( n) 0, но, как мы уже заметили, существование такой разрешающей процедуры привело бы к противоречию в рекурсивной арифметике.  [44]

Имеется несколько систем конструктивной теории функций; некоторые из них, как, например, интуиционистский анализ, основаны на новой логике, другие изучают конструктивные объекты, например, рекурсивные вещественные числа, методами классического анализа, а третьи пытаются выразить с помощью функционалов часть классического анализа в виде формул со свободными переменными. Система, описанная в этой книге, отличается от всех этих систем. Она основана на примитивно рекурсивной арифметике, и в ней делается попытка построить теорию функций в поле рациональны чисел, напоминающую в одних отношениях классический анализ, а в других - интуиционистский анализ. Все доказательства в рекурсивном анализе формализуемы в исчислении равенств) - системе рекурсивной арифметики, описанной в моей книге Рекурсивная теория чисел, но настоящую работу можно читать без детального знания рекурсивной арифметики.  [45]



Страницы:      1    2    3    4