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