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