Гильберт, Бернайс - Основания математики. Теория доказательств (947376), страница 48
Текст из файла (страница 48)
3»«Е(Г1, .... 1>«) (1. 6ФО) и не содержащая индивндных переменных, отличных от х1, ..., х„ 21, ..., р,. Пусть р — некоторая цифра, а «2 — система вычисли- (Ф> мых 1-местных арифметических функций Ч>ы ..., 1р,. Под Ьр мы ') См. т. 1, с. 168. будем понимать коиаюнкцию, состоящую нз членов 2)(п>,1 ..., и, р Е, р ..., 1, 1) (1=0, ..., (р+1)' — 1; Е;;=12,(п,, ..., и«;) для 1=!, ..., 6) где набор и, р ..., п,, пробегает (р+1)' различных р-членных наборов, состоящих нз цифр, не превосходящих р (эти наборы упорядочены по наибольшей встречающейся в них цифре, а затем лексикографически). Тогда в применении к формуле 5 наш предыдущий результат изобразится следующим образом.
Если формула Я опровержима в исчислении предикатов, то на основе ее опровержения можно для любой системы 12 вычислимых арифметических функций 12„..., 12, от 1 аргументов указать такую цифру р, что конъюнкция йр«' будет опровержима средствами исчисления высказываний, т. е. будет получаться подстановкой из отрицания некоторой тождественно истинной формулы исчисления высказываний. Такая цифра р получится и в том случае, если заданная система функций будет определяться с помощью свободно становящейся последовательности ').
С другой стороны, если для некоторой цифры р и некоторой разделяющей системы 12 функций 12„..., 12 формулами»~Ф' будет опровержима средствами исчисления высказываний, то, пользуясь этой опровержимостью, мы сможем получить опровержение $ в исчислении предикатов. Теперь попытаемся разобраться в том, что означает опровержимость формулы 5рФ~ средствами исчисления высказываний. Вопервых, она выражает тот факт, что эта формула получается подстановкой из отрицания некоторой тождественно истинной формулы исчисления высказываний; и так как формула брч> не содержит связанных переменных, то это в свою очередь означает, что при любом распределении истинностных значений между входящими в 5~ю элементарными формулами вся формула в целом всегда будет принимать значение «ложна (еслн связки исчисления высказываний понимать как истинностные функции). Далее, если мы учтем, что формула 5'„Ф' представляет собой конъюнкцию, состоящую из членов е(п1,1, ..., В„), Е>,р ..., Е, 1) (1=0, .", (р+1)' — 1), где Е; 1 при 1=1, ..., 6 является значением выражения 12, (пир ...
..., и,;), и что 6(п1, ..., и, р Еь и ..., Е«1) не содержит нина- 1) См. с. 216. 222 е-СИМВОЛ И ЛОГИЧССКИП ЕОРМДЛИЗМ !гл ги 223 кРитеРии опповержимости ких переменных, кроме формульных переменных формулы 5, и никаких других термов, кроме цифр пир ..., и, „, 1ь 0 ..., 1« 1, то получится, что опровержимость 5 средствами исчисления ип высказываний равносильна тому, что если формульные переменные формулы 5 заменить логическими функциями с тем же самым числом аргументов, определенными для цифр, фигурирующих в формуле (1~е', а формульные переменные без аргументов — истинностными значениями '), то (при данных пробегах логических функций и при интерпретировании связок исчисления высказываний как истинностных функций) формула 5~~' будет всегда принимать значение «ложь».
В противоположность этому, неопровержимость формулы 5» средствами исчисления высказываний заключается в том, что среди возможных замен формульных переменных в 5 логическими функциями найдется по крайней мере одна такая, в результате выполнения которой формула я~„'о~ примет значения «истина» (так как в 5,',о' входит лишь конечное число цифр, мы можем ограничиться рассмотрением лишь конечного числа систем пробегов их значений). Другими словами, неопровержимость формулы 5»е' средствами исчисления высказываний означает, что можно выбрать такие логические функции для замены формульных переменных в формуле $, что каждая из формул З(п>ь)» ° ° ° пи р 1« р ' ''> 1«,1) для 1=0, ..., (в+1)' — 1.
где 1> 1 представляет собой значение выражения <р;(иь;, ..., п«1), примет значение «истина». Возможность построения таких логических функций мы можем кратко выразить, сказав, что при рассматриваемых арифметических функциях фы ..., фа формулы З(пир ..., п, 1, <р,(пь), ..., и,;), ..., фз(пи 1, ..., и,;)) совместно выполнимы.
Выполнимость при этом понимается как выполнимость с помощью логических функций, которые подставляются вместо формульных переменных формулы $ (каждая логическая функция берется с тем же самым числом аргументов, что и соответствующая ей формульная переменная, а вместо формульных перемен- ') Этя ястяпностяые зкачепяя можко рассматривать как нульместяые логяческке фуякцяв. ных без аргументов подставляются просто истинностные значения); эти функции определены на конечной инднвидной области встречающихся у нас цифр (или, если угодно, на области пифр от 0 до наибольшей из числа встречающихся). Ввиду того, что область эта ограничена, высказывание о совместной выполнимости упомянутых формул имеет флнитный смысл. В итоге для установленных нами критериев опровержимости формул 5 исчисления предикатов, имеющих вид 'УУ» ...
'ЧУ,Ж, ... -)Р«З(УИ ..., Ра), где с, бФО, а уы ..., ры з)х, ..., ра — полный список входящих в эту формулу ицдивидных переменных, мы получаем следующие более прозрачные формулировка, в которых также используется ранее уже применявшаяся нумерация г-члеиных наборов цифр пь), ..., п,) (1=0, 1, ...): 1. Если формула $ опровержима в исчислении предикатов, то для всякой системы вычислимых «-местных арифметических функций ф», ..., ра формулы З(пь р ' ' ' > и«, р Ч>1(пь 1» пс, 1) ° > Ч>е(пи 1> ° ° и«, 1)) 1=0, ..., (р+1)" — 1 не являются совместно выполнимыми, начиная с некоторой цифры р, определяемой для данной системы функций на основе опровержения формулы й.
2. Если формула й опровержима в исчислении предикатов, то для любой свободно становящейся последовательности В-членных наборов цифр 1ь), ..., 1,1 (1=0, 1, ...) формулы З(пь;, ..., и, 1, 1ь), ..., 1 )) 1= О, ..., (р + 1)« — 1, начиная с некоторой цифры р (получающейся в ходе построения втой последовательности с помощью опровержения формулы б), не являются совместно выполнимыми ').
>) Можно было бы пытаться заменить этот критерий более простым, утверждакяцкм, что в случае опровержпмостя формулы 6, начиная с некоторой цифры Р, будет невозможно указать такие «-«лепные наборы (»1 В« для которых формулы ю(за ) " "«,1 >х.) "° ««,1) КРИТЕРИИ ОПРОВЕРЖИМОСТИ [ГЛ. Н! а-снмвол и логнчвскии еормллизм 3. Если для любой цифры р и для любой разделяющей системы') вычислимых арифметических функций [р!. ° ° ° [рб формулы 6(И,, ..., И, [Рь(И!Ой ..., ИС, 1), ° ° ° ь СРЕ(пь,!ь ° ° ° ь ПС, !)) 1=0, .", (р+1)' — 1 не являются совместно выполнимыми, то из невыполнимости зтого списка формул следует опровержимость формулы [у в исчислении предикатов, Первое из этих трех утверждений является непосредственным следствием второго, Действительно, упомянутые в нем Т-местные вычислимые функции ср„..., [рб можно использовать для порождения свободно становящейся последовательности, беря всякий раз в качестве [и[, ..., [; значения функций [ра, ..., ьре на наборе и,,(, ..., и, 1.
Критерии 1 и 2 дают необходимое условие опровержимости. Критерий 3 дает достаточное условие, Так как это достаточное условие слабее, чем упомянутые необходимые, то каждое из этих условий является одновременно и необходимым и достаточным условием опровержимости формулы 5 в исчислении предикатон, Из критериев 1-3 можно извлечь следующие важные правила, касающиеся установления неопровержимости формул вида Р Е! ° ° )УЗД[)! ° ° ° Э)ВЗ(Г! " ° [Ъ) о отличными от нуля ! и В и о единственными индивидными переменными и[, ..., Б„»„..., [)е: 1е.
Для того чтобы установить неопровержимость формулы В в исчислении предикатов, достаточно указать такую систему вычислимых с-местных арифметических функций [р„..., [р, при которой формулы 6(иь,, ..., и, 1, срь(иь,(, „и, !), ..., [р (и[,1, ..., и, )) 1=(), ..., (р+1) — 1 совместно выполнимы при произвольном выборе цифры р. ае являются совместно выполввыыыв. В таком случае лопатке свободно ста- поввшейсв последовательности здесь было бы квавшпыы. Однако в действительности упомянутое более простое условве выполняется вовсе пе дла каждой опровержимой формулы расскатрвваемого вида. Это обнаруживается уже па примере формулы ьсхЗу (А (х) й ! А (у)), которая, равуыеетсв, опровержака, в то время как формулы А ([) й 1 А [р + 1), ! О, ..., р, СОВМЕСТВО ВЫПОЛНИМЫ ПРВ ЛЮбой ЦИФРЕ р ь) Сы.
с. 2!7, 2*. Для того чтобы установить неопровержимость формулы й в исчислении предикатов, достаточно показать, что какая-либо свободно становящаяся последовательность 6-членных наборов цифр [ь, 1* " !е 1 (! = б 1 . ) может быть неограниченно продолжена таким образом, что всякий раз, когда эта последовательность построена до места с номером 1=(р+1)' — 1, формулы 6(иь(, ..., ие 1, !ьр ..., 1,,) 1 = О, ..., (р+ 1)" — 1 оказываются совместно выполнимыми.
3*. Если формула 5 неопровержима в исчислении предикатов, то формулы 9(п, р ..., и„р срз(иь р ..., и,;), ..., [р,(ив!, ..., и,;)) ! = б, ..., (р + 1) — 1 совместно выполнимы для любой разделяющей системы ') вычислимых г-местных арифметических функций срз, ..., [ре и для любой цифры р. Такая формулировка этих критериев имеет определенные преимущества для использования их в вопросах непротиворечивости формализованных систем аксиом первой ступени; эти вопросы, как мы знаем, сводятся к вопросам о неопровержимости тех или иных формул исчисления предикатов.
Однако следует отметить, что этот вариант формулировки данных критериев,— отвлекаясь от того, что он облечен не в форму теорем, а всего лишь в форму правил для неформального вывода,— при финитном рассмотрении не полностью воспроизводит содержание критериев 1 — 3. Мы кратко поясним эту мысль на примере критерия 1. Критерий этот утверждает, что нз существования какого-либо опровержения формулы 5 вытекает, что для всякой системы вычислимых функций ср„ ..., ср существует некоторая цифра р, обладающая некоторым конкретным, непосредственно устанавливаемым свойством ~(р„ф„..., ср ).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
