Cтраница 1
Арифметический предикат S всегда может быть записан в префиксной нормальной форме как рекурсивный предикат R с некоторым префиксом кванторов [ 5, стр. Этот квантор-ный префикс может быть представлен в виде чередующихся кванторов, и тогда предикаты помещаются в иерархии согласно числу чередования кванторов существования и общности в префиксе. [1]
Арифметическим предикатом называется предикат, аргументы которого должны принимать десятичные числовые значения. В языке имеются следующие арифметические предикаты. [2]
Какого рода арифметический предикат может удовлетворять условию, что R ( х, у) эффективно разрешим. [3]
В содержательном понимании арифметический предикат представляет собой произвольный ( не обязательно конструктивно определенный) предикат на множестве всех целых неотрицательных чисел. Построенная нами формальная арифметическая система дает способ конструктивного задания некоторых арифметических предикатов. [4]
Отсюда следует, что арифметические предикаты и функции, ( вполне) соответствующие метаматематическим, определенным посредством Dn 1 - Dn 13а § 51 ( см. лемму 191 § 52) и Df 1 - Df 15 § 56 ( см. лемму III), являются элементарными. Действительно, в этих метаматематических, определениях обобщенной арифметик рекурсии служат только для введения представляющих функций предикатов. В частности, 5n ( Df 13) и, следовательно, ( С) Тп ( предшествует формулировке теоремы IV) и U ( Df 15) элементарны. [5]
Заметим, что CF ( e x) не совпадает с вполне соответствующим арифметическим предикатом для E f ( E, х), потому что он истинен, когда е или х не является геделевским номером. Но это не играет роли, потому что ( е) г входит также в F e), a ( d) 2t - в V ( ( d) sa), которые соответствуют условиям из Шп9, что С - формула, а х - переменная. [6]
Кроме того, в LDL поддерживаются предикаты равенства и неравенства и несколько арифметических предикатов. [7]
Для каждого из предикатов и функций, определенных посредством Dfl - Dfl5, вполне соответствующий арифметический предикат или соответствующая арифметическая функция примитивно-рекурсивны. [8]
Теперь мы рассмотрим на примере арифметики, каковы возможности описанного выше языка для представления свойств арифметических предикатов и термов. Сужение же сигнатуры упрощает модальную логику, но может привести к уменьшению выразительных возможностей. [9]
Таким же образом рассматриваются определения остальных предикатов из списка Dnl - Dnl3, DnlSa, за исключением отмеченных выше случаев рекурсии по двум переменным и пунктов, помеченных звездочками. Определяемый арифметический предикат, получающийся в результате перевода ( подобного переходу от ( 1) к ( 2)), истинен только для геделевских номеров в качестве аргументов, потому что в каждом пункте первоначального определения каждая переменная вещь должна удовлетворять ранее рассмотренному предикату или следовать за вещами, которые фиксированы или удовлетворяют ранее рассмотренным или определяемому предикатам. [10]
Простейшие ограниченно арифметические предикаты. [11]
Арифметическим предикатом называется предикат, аргументы которого должны принимать десятичные числовые значения. В языке имеются следующие арифметические предикаты. [12]
Если мы перейдем от вещей к их геделевским номерам, то предикат или функция вещей становится предикатом или функцией геделевских номеров. Мы говорим, что арифметический предикат или функция, полученные путем расширения определения этого предиката на все натуральные числа, соответствует первоначальному предикату или функции. [13]
Мы говорим, что предикат S является рекурсивным, если S рекурсивно разрешим. Говорят, что S - арифметический предикат тогда и только тогда, когда S получен из некоторого рекурсивного предиката навешиванием кванторов. [14]
Имеется специальный случай, когда применимость закона исключенного третьего все же может быть доказана интуиционистски, а именно ( в случае индуктивного определения класса), когда порядок, в котором согласно индуктивным пунктам появляются элементы этого класса, совпадает с тем порядком, в котором эти элементы порождаются согласно фундаментальному индуктивному определению. Из этой второй формы мы получаем вполне соответствующий арифметический предикат ( Ey) [ Pf ( y) & ( y) 0 d ] ( см. Dn 12), который имеет вид ( Ey) R ( d y), где предикат R примитивно-рекурсивен. [15]