Гильберт, Бернайс - Основания математики. Логические исчисления и формализация арифметики (947375), страница 70
Текст из файла (страница 70)
К прежним пунктам определения и с т и н н о с т и и л о ж н о с т и мы добавим следующие новые. Любая формула вцда О( ) ~ <о( ) Р истинна. Формулы вида <о(р) ( О( ), 0( ) = <й( ) и <й( ) =- 0( ) Р Р ложны. Формула О) (О <ар <й истинна, если число 3 + <) совпадает с (+ р, и ложна в противном случае. г (О') всегда истинна, всегда ложна. Для произвольных нумерических формул истинностные значения получаются на основе этих, а также прежних пунктов определения.
В качестве следствия из этого определения истинностных значений отметим, что для всякой цифры второго рода <о(О н для Р произвольного числа < всегда можно указать такую цифру второго рода а, для которой будет истинным равенство й ( < ) щ ( ( ) Р Действительно, такой цифрой является <в(О Р+<' Теперь, чтобы процедуру построения р е д у к ц и и формулы беэ формульных переменных привести в соответствие с только что сформулированным определением истинностных значений нумери- 22 д.
Гнльйере, Б. Бернайс ДОКАЗАТЕЛЬСТВА НЕЗАВИСИМОСТИ ЗЗ0 НАЧАЛА АРИФМЕТИКИ (гл. Тс ческих формул, в обычной процедуре редукции нужно будет произвести лишь следующую модификацию: 1. В четвертом преобрааовании иэ числа тех, которым мы подвергаем выражение Я (х) [при устранении квантора существования в какой-либо из самых внутренних составных частей вида ЛхЯ (х)[, каждый входящий в Я (х) член Я (х()), где $ меньше, чем максимальное число с навешенных на х штрихов, мы заменим посредством я (х(с)) и в соответствии с этим )Л (х(~)) ааменим посредством )у (х(с)). Если в результате этого несколько членов конъюнкции или диаъюнкции окажутся совпадающими, то возникшие при атом повторения мы удалим.
2. При рассмотрении членов 3 хб (х(с)), в ноторых 6с(х(с)) не содержит в качестве кокъюнктивного члега никакого равенства х(') = а после вынесения из-под квантора существования членов, не содержащих х, для оставшегося выражения 3 хй (х(']) мы долнспы будем различать следующие случаи: а) В конъюнкцию к' (х(с)) входят одни только неравенства; в атом случае мы поступим прежним образом. б) В конъюнкцию [1 (х(с)) в качестве члена входят как 7 (х(с)), так и )я (х(с)); в этом случае выражение Лхй (х(с)) мы заменим формулой О ~ О. в) Выражение Лхк (х(с)) имеет вид Зхя (х(с)) или 3х -) Е (х(')); в этом случае мы заменим его равенством О = О. г) й (х(с)) имеет один из следующих двух видов: Я (х(с)) & й*(х(с)), ч я (х(с)) & йч (х(О), где кч (х(")) представляет собой конъюнкцию неравенств а, < х(с) &...
& а( < х(с) & х(с) < Ь & & х(с) < Ь ° Тогда мы прежде всего заменим Зх(г(х('))&й ( (')В конъюнкцией Я(а,) &... & Я(а() &ахи(х(с)), 3х(~ У(х(с)) & $" (х(с))) соответственно конъюнкциеи ) А(Ьс) & ° .. & (А(ЬЕ)& дхя(х(С)) и после этого заменим лх к (х(с)) так же, как и раньше, причем в последнем из упомянутых случаев, когда имеется конъюнктивный член ~я (х(с)), члены О(с) <Ь, &...
& О(с) <Ь могут быть опущены. Для этой процедуры редукции снова можно будет доказать обе прежние леммы и с их помощью доказать теорему об однозначности и теорему о частичной редукции '). Кроме того, мы можем дословно перенести наше прежнее определение понятия в е р ифицируемости, причем под цифрами теперь надо будет понимать цифры первого и второго рода.
С помощью элементарных рассуждений о числах теперь легко будет убедиться, что в соответствии с этим определением все аксиомы системы (А*), за исключением (1,), являются верифицируемыми. Для аксиомы (У,) также можно будет, аналогично предыдущему '), показать, что всякая формула беа формульных переменных, получающаяся из нее в результате подстановки, является верифицируемой.
При этом возникнет некоторое расхождение с пренсним рассуждением (как, впрочем, уже и в доказательствах теорем о редукции), поскольку иэ истинности нумерического равенства а = Ь теперь нельзя будет сделать вывод о совпадении а с Ь, а вместо этого нужно будет пользоваться теоремой о том, что если а и Ь суть цифры, для которых а = Ь истинно, а с — произвольная цифра, то формулы а=с, с=а, а<с, с<а соответственно имеют те же самые истинностные аначения, что и формулы Ь=с, с=Ь, Ь<с, с<Ь.
Опираясь на зти утверждения об аксиомах, с помощью теоремы о частичной редукции можно будет показать, что всякая формула, ') См. с. 300. 2) См. с. 303. 1гл, ч< 34О НАЧАЛА АРНФМЕТНКИ ДОКАЗАТЕЛЬСТВА НЕЗАВИСИМОСТИ 341 выводимая из системы (А*) и не содерн<ащая формульных переменных, является верафицируемой '). 11о отсюда Задует, что формула 2 (а) не может быть выведена из системы (А*), так как она не верифицируема. Действительно, если мы заменим в ней переменную а цифрой ю, то она перейдет в ложную формулу 2 (ю). Тем самым невыводимость аксиомы индукции иэ системы (А) установлена.
В качестве следствия мы можем получить отсюда и независимость аксиомы индукции от остальных аксиом системы (В); действительно, все эти аксиомы, как мы анаем, выводимы из системы (А). 2. Доказательства пезавксимости с помощью метода подстановок. После этого мы для обеих систем (А) и (В) установим независимость входящих в их состав аксиом. Для большей части аксиом доказательство нам удастся провести с помощью одного очень простого приема, основанного на следующем соображении. Пусть в рамках нашего формализма дан вывод какой-либо формулы Я из определенных аксиом Я„..., Яп осуществленный при помощи исчисления предикатов.
Пусть, далее, 1Ь (а, Ь)— некоторая формула нашего формализма, не содержащая переменных, отличных от а и Ь. Заменим в рассматриваемом выводе всякое равенство а = Ь формулой 6 (а, Ь) и обозначим посредством Я,", ..., Я1, Яе формулы, которые в результате атой замены получатся из формул Я„..., Яр Я. Тогда у нас получится вывод формулы Я* из формул Я,*, ..., Я1. Действительно, в рамках исчисления предикатов анак равенства используется не иначе, как с привлечением правила подстановки и аксиом. Однако в отношении подстановки формула 15 (а, Ь) обладает теми же самыми возможностями, что и формула а = Ь, а в аксиомах нами была проиаведеиа замена знака равенства с аргументами а и Ь соответствующим ему выражением (г (а, Ь).
Аналогичное рассуждение может быть проведено и тогда, когда описанная замена производится не для равенств а = Б, а для неравенств а < Ь. Такое положение вещей позволяет нам пользоваться следующим приемом для установления независимости тех или иных аксиом. Для того чтобы показать, что в рамках рассматриваемой нами совокупности формул какая-либо формула Я не выводится иэ данных аксиом Я„ ..., Я1, достаточно так подобрать формулу <ь (а, Ь), не содержащую переменных, отличных от а и Ь, чтобы при замене каждого равенства а = Ь (или же каждого нераВенства а <Ь) соответствующим ему выражением 6 (а, Ь) фор- <) См.
с. 305. мулы Я Ям ° °, Я1 переходили в формулы Я*, Я~, ..., Я* такие, что можно констатировать невыводимость формулы Яе,из Я <',, Я1. Пользуясь этим методом, мы сможем доказать независимость всех аксиом системы (В) (за исключением аксиомы индукции, независимость которой уже установлена) от остальных аксиом системы. Далее, мы сможем тем же самым способом установить и независимость ряда аксиом системы (А) от остальных аксиом этой системы. 1.
Для аксиомы равенства (У ) мы покажем, что она не зависит от всех остальных формул систем (А) и (В), даже если их взять вместе. В самом деле, если бы она выводилась из этих формул, то иа них выводилась бы и получающаяся из (У ) подстановкой формула а = а-+. (а <а'-<- а <а). Нсли мы теперь вместо равенства а = Ь всюду подставим выражение С=Ь 1/ С ~Ь, то только что упоминавшаяся формула перейдет в а' = а </ а' чь а -э (а < а'-+. а < а), а остальные аксиомы систем (А) и (В), содержащие анак равенства, перейдут в формулы, выводимые с помощью исчисления предика- тов, в то время как остальные останутся беэ иаменения. Таким обрааом, в результате произведенной замены все эти аксиомы дадут нам такие формулы, которые выводятся иэ системы (В). Поэтому и формула а' = а ~/ а' ~ а <- (а < а' -~ а < а) также должна была бы выводиться из системы (В), а тем самым, согласно доказанному нами относительно системы (В), она должна быть верифицируемой.
Однако зто не так, вчем можно убедиться, подставив 0 вместо а. 2. Независимость аксиомы (<,) от остальных аксиом системы (В) может быть установлена путем аамены а <Ь выражением а=Ь \/ ЗФ 3. Действительно, в результате этой замены те формулы системы (В), исключая (<,), которые этой заменой подвергаются каким-либо изменениям, переходят в такие формулы, которые выводятся средствами исчисления предикатов, в то время как формула (<,) переходит в формулу 1(а =а </а~а). в в] 343 ДОКАЗАТЕЛЬСТВА ??ЕЗАВИСКМОСТИ ?гл. ч? НАЧАЛА АРИФМЕТИКИ 342 Если бы аксиома ((,) была выводимой из остальных аксиом системы (В), то зта формула выводилась бы из системы (В) (даже иэ одних только аксиом равенства и аксиомы индукции), в то время как на самом деле оыа не верифицируема.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
