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