Гильберт, Бернайс - Основания математики. Теория доказательств (947376), страница 52
Текст из файла (страница 52)
Применим к этой формуле критерий неопровержимости 3* г), взяв в качестве сг„..., гр систему функций, которая на основе нашей нумерации г-членных наборов цифр ') определяется равенствами ср,(п»1, ..., и, )=д 1+1 (1=1, ..., 6; 1=0, 1, ...). Как было отмечено'), эти функции образуют разделяющую систему функций. Упомянутый критерий позволяет утверждать, что для любой цифры р формулы чг(пг), ..., Пс р 6 1+1, ..., 6.1+6) 1=0, ..., (р+ 1) — 1 являются совместно выполнимыми.
Это утверждение можно обосновать еще и следующим образом. Если бы для какой-нибудь цифры р указанные формулы не были ссвместно выполнимыми, то для этой цифры р при любом рас- ') См. с. 225. Для читателя, желаюшега избежать ссьшкн на упомянутый критерий, вскоре будет дана более прямое рассуждение. з) См. с. 218. 240 е.символ и логическии ео»мллизм» 1гл ш пределении истинностных значений между входящими в упомянутые формулы элементарными формулами по меньшей мере одна из этих формул получила бы значение «ложь»', и, значит, дизьюикция, составленная из отрицаний этих формул, была бы истинна не ной в логике высказываний, т. е.
получалась бы подстанов акой екоторой тождественно истинной формулы исчисления высказываний. Но из этой дизъюнкции, применяя производные правила !)«) и !Р) исчисления предикатов'), с помощью того же самого приема, который использовался для доказательства второй е-теоремы, можно было бы получить формулу З~»...'Э~,Ф)»...'ч»«)3!Г„..., Г«, р,, ..., 0«). Тогда было бы выводимо отрицание формулы 5, что противоречит нашему предположению. Полученному результату можно придать следующий внд: Если обозначить для краткости формулу 3!пь1, ..., п«1, з 1+1, ..., е 1+6) через 31, то для любого числа ! конъюнкция 3« й 3» «» ° ° й 31 будет выполнимой. Эту конъюнкцию, определенную формулой 5 и числом 1, мы обозначим через Кь Каждая из формул 5«Я», й„...
является подкоиъюнкцией всех формул 50 следующих за ней. Мы покажем, что пользуясь моделями формул 5„5„5„..., можно построить некоторую общую модель для всех этих формул, а тем самым и модель фомулы 5. В» р С этой целью мы рассмотрим структуру формул 3; 11 = О, !,...). Эти формулы составлены из элементарных формул с помощью свяэок исчисления высказываний. Пусть 3м ... 01 — элементар»'»о ные формулы, входящие в формулу 3, и расположенные в порядке их первого появления; пусть $„,+,, ..., 3И вЂ” элементарные формулы, входящие в 3», но не входящие в 3«и расположенные в порядке их первого появления, '...
И вообще, пусть 1)),. +,, ..., 3Р+, — элементарные формулы, впервые появляющиеся в 3;+, и расположенные в порядке их первого появления. Тогда каждой модели какой-либо конъюнкции 51 будет соответствовать некоторое приписывание истинностных значений элементарным формулам 3»> ... ° 3»1. ») См, с. 173.
пРимеиеиие к пРОБлеме Рл»Решимости 24! Имеется 21 различных возможных распределений истинностных значений для этих элементарных формул, и мы можем изобразить эти распределения числами, беря для изображения значений «истина» и «ложь» цифры О и 1 соотвэтственно и представляя полный список ш„..., ш„истииностных значений, сопоставленных элементарным формулам 41„..., 3,1, числом 21 ° ш,+2'1 ш,+...+2.ш«,+ш„, которое в двоичной системе счисления задается написанными друг за другом цифрами ш„..., ш,.
Таким образом, 2И различным распределениям истииностных значений между элементарными формулами Фм ..., Ч), в определенном порядке будут приписаны числа от О до 2и — 1. Если !) 1, то всякое распределение истинностных значений между элементарными формулами 41м ..., $, содержит в себе распределение истииностных значений между формулами $„ ..., $, . Из одного и того же распределения истинностных значений для ~~„ ..., 3, могут получиться различные распределения для Ф„ ..., 3, .
Но вследствие принятого нами способа изображения распределений истиниостных значений числами можно утверждать, что если е и 1 — числа, изображающие два распределения истинностных значений для формул 3м... ..., $,1, а з» и 1* — числа, изображающие содержащиеся в этих распределениях распределения для формул 41„..., ф«то если з»(1», то и 6(1. Распределение истинностных значений для элементарных формул ~3м . ° 3и, при котором формула 51 принимает значение «истина», мы будем называть выполняющим расп ределением для 5П Для каждого числа 1 имеется по крайней мере одно выполняющее распределение для 5б а с другой стороны, их имеется только конечное число (не больше 2"1). Если 1(1, то всякое выполняющее распределение для 51 содержит в себе некоторое вы полняющее распределение для Яб так как 51 является подконьюнкцией конъюнкции б!, 'зто выполняющее распределение для $1 мы для краткости будем называть 1-компонентой этого распределения для 111.
Если какое-либо выполняющее распределение для 51 является 1-компонентой некоторого выполняющего распре- Е СИМВОЛ И ЛОГИЧЕСКИИ ЕОРМАЛИЗМ ,~ (ГЛ,Ш деления для 5а и если число 1 заключено межф 1 и й, то это распределение будет также и 1-компонентой тяго выполняющего распределения для 5(, которое представляет собой 1-компоненту упомянутого выше выполняющего распределения для 5 . Поэтому а. среди выполняющих распределений для 5! должно иметься по крайней мере одно такое, что для каждого числа 1, большего 1, оно является 1-компонентой некоторого выполняющего распределения для 5!. При этом среди тех выполняющих распределений для 5), которые обладают указанным свойством, однозначным образом выделяется то, которое изображается наименьшим числом.
Таким образом для каждого числа 1 определяется некоторое выделенное распределение истииностных значений между элементаРными фоРмУлами 4)т, ..., Ч), как пеРвое (по числовомУ представлению) из таких выполняющих распределений для $ которые для всякого числа 1, большего 1, представляют собой 1-компоненту некоторого выполняющего распределения для 5. !. Из этого определения выделенного для числа 1распределения нстинностных значений вытекает, что для любых двух чисел 1 и 1, если 1(1, то выделенное для 1распределение является 1-компонентой выделенного для 1 распределения. Действительно, если а! и и! — числа, изображающие выделенные для чисел 1 и 1 распределения, и если т — число, изображающее 1-компоненту распределения, изображенного числом и!, то, во-первых, на основании определения и, число т не может быть меньше п!.
С другой стороны, если бы пт было больше и(, то по определению и! должно было бы существовать такое выполняю!цее распределение для 5 (з которое содержит распределение, изображенное числом и(, в качестве 1-компонеиты и которое для любого числа ч, большего 1, представляет собой (-компоненту некоторого выполняющего распределения для ~5„. Далее, так как п(~т, то число, изображающее это распределение, в силу ранее упомянутого свойства нашего изображения распределений истинностных значений числами, должно было бы быть меньше л(, Таким образом, т должно совпадать с и!, и, значит, распределение, изображенное числом п является 1-компонентой распределения, изображенного числом п .
!. Итак, получается, что все соответствующие различным числам выделенные распределения объединяются в единое, однозначно определенное распределение истиниостных значений между элементарными формулами 4)„ф„... А теперь это распределение истинностных значений мы можем без труда дополнить до некоторой модели формулы 5. Действительно, элементарные формулы фз, !Р„...
образуются из фор- 243 пРименение к пРОБлеме РАЗРешимОяти мульных переменных с цифрами в качестве аргументов и, быть может, еще из формульных переменных без аргументов, причем все входящие в 5 формульные переменные, вообще говоря, встречаются здесь не со всеми возможными наборами значений аргументов, но со всеми теми наборами, которые встречаются в какой- либо из формул !у!. Итак, этим распределением истинностных значений между элементарными формулами $„!4)„..., во-первых, устанавливаются истиниостиые значения для всех входящих в !! элементарных формул без аргументов и, во-вторых, определяются подставляемые на место формульных переменных с аргументами логические функции как функции„заданные в области натуральных чисел для тех наборов значений аргументов, которые фигурируют в формулах 5!. Для прочих наборов значений аргументов истинностные значения этих функций можно определить произвольно, взяв, например, всюду значение «истина».
Так мы получим некоторую совместную модель формул 9(пь(, ..., и,(, д 1+1, ..., 6 )+6) в виде логических функций, определенных в области натуральных чисел, а также некоторых истинностных значений, играющих роль замен для формульных переменных без аргументов. Но так как теперь среди наборов пь р ..., и,; (! =О, 1, ...) встречаются все возможные с-членные наборы цифр, то мы получаем модель формулы 'з'йз ° " '((3Дрт ° ° =)!)зез (йы ~ йт. т7ы ° '7з) в области натуральных чисел. Зго доказательство геделевской теоремы о полно;е заодно дает нам и новое доказательство теоремы Левеигейма о том, что всякая выполнимая формула выполнима в области натуральных чисел. Действительно, из неопровержимости формулы 5 мы сделали вывод не только о ее выполнимости вообще, но и о выполнимости в области натуральных чисел; с другой стороны, из выполнимости формулы, как мы знаем, вытекает ее неопровержимость.
Замечание 1. В этом втором доказательстве теоремы Левенгейма ') применение принципа выбора„которым начинается первое ') Упоминание об исчислении предккатов яз этого доказательства можно устранить, так что у вас получится чисто теоретико-модельное доказательство. 7)оказательство такого рода, освовавкое ва соображении о том, что кз выполнимости формулы 6 вида (3) следует выполнимость каждой вз формул )т!, было дано т.кодекам в его работе: зйо! езп ТЬ. ()Ьег е)епйе Стопа)ахеп(таяеп бег Мацзетпа(ис — зйт. потзйе Н)б.-Акай., Оз)о, 1 Ма!.-Ха!. К!., !929, )м 4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
