Гильберт, Бернайс - Основания математики. Логические исчисления и формализация арифметики (947375), страница 71
Текст из файла (страница 71)
3. Заменив неравенство а <Ь вырая<еннем С=Ь<йаФ 5 мы получим, что если бы аксиома (< ) была выводима из осталь- ных аксиом систем (А) и (В), то формула а = а' б< а Ф а' должна была бы выводиться из аксиом (1?), (1»), а ~ 0 -«Вх (х' = а), аксиомы индукции и формулы а Ф Ь -«(а = Ь б< а ~ Ь) ?/ (Ь = а Ь Ь ~ а) (с' использованием символа штриха). Однако в результате этой замены они дают, как легко убедиться, лишь такие формулы, которые, будучи рассмотрены в индивидной области, состоящей только из 0 (при этом значение 0 считается равным 0), при замене входящих в них формульных переменных логическими функциями, а свободных индивидных переменных символом 0 всегда принимают значение «истина», в то время как формула а=а'б а~а' принимает значение «ложь». Тем самым аксиома ((,) оказывается независимой от всех остальных аксиом систем (А) и (В).
4. Независимость аксиомы (<,) от остальных аксиом систе'мы (В) доказывается с помощью замены а (Ь выражеыием а Ф Ь. 5. Независимость формулы а = а от остальных аксиом системы (В) доказывается с помощью замеыы а = Ь выражением а = Ь <к а ~ О. 6. Независимость формулы а (Ь -«? (Ь (а') от остальных аксиом системы (А) доказывается с помощью замены а (Ь выражением (а = 0 ??' а чь О) б< Ь ~ О. Тем самым для систе»?ы (В) все необходимые доказательства независимости проведены.
У системы (А) пока отсутствуют дока- эатвльства независимости для формул а~Π— «Зх(х' =а), а <Ь б Ь <с«а <с, ? (а (0) а Ф Ь вЂ” «а ( Ь ?/ Ь (а. 3. Установление ряда других независимостей с помощью модификации процедуры редукции. Для проведения этих докааательств мы применим следую?ций прием: сначала мы расширим совокупность нумерических формул путем введения соответствующих ц и ф р в т о р о г о р о д а; затем мы определим истинностпые значения нумерических формул и, производя для каждого из этих определений соответствующие изменения в процедуре редукции, мы так определим понятие в е р и ф н ц и р у е м о с т и, сохранив первоначальную схему его определения '), чтобы каждая выводимая из используемых аксиом формула без формульных переменных была вврифицируемой в смысле этого определения, а формула, независимость которой устанавливается, была неверифицнруемой, откуда и будет следовать ыеэависимость рассматриваемой формулы от укаванных аксиом.
Для задания проводимых этим способом доказательств независимости мы можем использовать то обстоятельство, что изменение процедуры редукции определяется уже тем, как мы вводим истипныв аначения нумерическнх формул. Действительно, в тех подготовительных операциях ? — 4 процедуры редукции '), которые отличны от преобразований исчислеыия высказываний, речь идет о том, чтобы исключить, во-первых, отрицания равенств и неравенств, во-вторых,— такие равенства и неравенства, у которых х стоит в обеих частях, и, в-третьих, — такие равенства и неравенства, у которых х фигурирует с меньшим, чем максимальное встречающееся, числом штрихов. При этом — чтобы можно было доказать теоремы о редукции — указанное исключение должно производиться путем таких преобразований, при которых выражение ?3, получающееся иэ выражения Я, при каждой замене цифрами переменных, входящих в Я и ?л?, должно принимать то же самое истинностное значение, что и выражение Л.
На последнем шаге процедуры редукции, при рассмотрении вырая<ений Эх<в< (х(?)), речь идет о том, чтобы для каждого такого выражения найти не содержащее переменной х вырая<е- ') Си. с. 289 и далее, а также с. 305. ") Си. с. 291 и далев. 344 НАЧАЛА АРИФМЕТИКИ [гл. Рс ДОКАЗАТЕЛЬСТВА НЕЗАВИСИМОСТИ ние 6«, которое содержало бы все остальные фигурирующие в )э,(х(с)) переменные и не содержало никаких других и которое при каждой замене этих переменных цифрами переходило бы в истинную или в ложную формулу в зависимости от того, возможно или невозможно указать такую цифру Ь, чтобы выражение ««(Ь(с)) при той же самой замене переменных переходило в истинную формулу, чем заодно устанавливается финитный характер атой альтернативы. То, что эти задачи оказываются разрешимыми для каждого из подлежащих рассмотрению расширений запаса цифр в сочетании с соответствующими определениями истинностных значений нумерических формул, по существу обусловливается тем, что свойства «быть цифрой первого рода» и «быть цифрой второго рода» в тех случаях, когда в редукции используется различение обоих родов цифр, выразимы при помощи некоторых формул Я, (а) и Д» (а) в том смысле, что для любой цифры а первого рода 8,(а) истинно, а Д«(с) ложно, а для любой цифры а второго рода 3,(а) ложно, а (5«(а) истинно.
Для каждой из рассматриваемых нами систем цифр и истинностных значений к решению упомянутых выше задач мы приходим, с помощью определенного соответствующими соглашениями истолкования формул, некоторым, по существу (т. е. отвлекаясь от несущественных подробностей) единообразным способом. Поэтому для проведения этих четырех доказательств независимости мы можем ограничиться тем, что введем цифры второго рода, а также новые, дополнительные по отношению к обычным, определения истинностных значений нумерических равенств и неравенств (другие элементарные формулы у нас не встречаются), а кроме того, в тех докааательствах независимости, где в процедуре редукции проводится различение цифр первого и второго рода, мы приведем соответствующие формулы Я, (а) и Д«(а). Ради большей ясности в тех случаях, когда в соответствии с определением истинностных значений будет требоваться изменение одной или нескольких подготовительных операций 2 — 4, входящих в процедуру редукции, мы будем специальяо это подчеркивать.
(Изменение„всякий раз требующееся на последнем шаге редукции, специально оговариваться не будет.) Для формулы, независимость которой мы будем доказывать, всякий раз будет указываться некоторая замена ее свободных переменных цифрами, в результате которой эта формула, в соответствии с текущим определением, будет оказываться неверифицируемой. Установление того факта, что каждая формула, выводимая иэ остальных аксиом системы (А), является верифицируемой, протекает способом, аналогичным тому, которым соответствующее доказательство проводилось в случае обычной процедуры редукции, т.
е. при помощи теорем о частичной редукции и об однозначности '). При атом, в частности, используются следующие общие свойства цифр и истинностных значений. Цифра а(") является цифрой первого рода тогда и только тогда, когда а является цифрой первого рода. Для любой цифры а равенство а = а является истинным. Для произвольных цифр а и Ь равенство а = Ь имеет то же самое истинностное значение, что и равенство Ь = а. Если для каких-либо цифр а и Ь равенство а Ь является истинным, то для любой цифры с формулы а=с, а .,с и с(а соответственно имеют те же самые истинностные значения, что и формулы Ь=с, Ь(с и с(Ь.
Для равенств и неравенств между цифрами первого рода, а также для соответствующих истинностных функций исчисления высказываний справедливы обычные определения их истннностных значений. Теперь, с учетом этих предварительных замечаний, упомянутые четыре доказательства независимости могут быть представлены в следующем сокращенном виде: 1. Независимость формулы а Ф О -~ 3 х (х' = а). Цифрами второго рода являются фигуры со~ 1. (с) Для равенств между произвольными цифрами и для неравенств между цифрами одного и того же рода берется обычное определениеистинности и лая«ности. Если а — цифра первого рода, а Ь вЂ” цифра второго рода, то неравенство а (Ь считается истинным, а неравенство Ь (а — ложным. Формулы 31 (а) и 8» (а) имеют вид а ( со и со ( а .
Редукцией рассматриваемой формулы а Ф О «- 3 х (х' = а) является формула а Ф О -~ (а ( со бс (О' = а )/ О' ( а)) ~ (со (а'бс (со' = а )/ со' (а)) «) См. с. 295, 300. 346 Е[АЧАЛА АРИФМЕТИКИ [гл. ч[ ДОКАЗАТЕЛЬСТВА НЕЗАВИСИМОСТИ 347 При замене а посредством [о зта формула оказывается ложной, так как «[ Ф 0 истинно, «[ < «[ лен[но и [« = [« '[/ «[' = «[ лон[но. 2. Независимость формулы а < Ь Ь Ь < с -э а < с. Цифрами второго рода являются фигуры «[(1). Равенство «[() = ю( ) является истинным, а неравенство «(1) < (1) ([) ««[ [ — ложным, воли числа Г и 1 либо совпадают, либо отли- (1) чаются друг от друга на четное число; в противном случае укаванное равенство считается ложным, а неравенство — истинным. Если а — цифра первого рода, а Ь вЂ” цифра второго рода, то неравенство а <Ь считается истинным, а равенства а = Ь, Ь = а и неравенство Ь < с — ложными.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
