Гильберт, Бернайс - Основания математики. Логические исчисления и формализация арифметики (947375), страница 89
Текст из файла (страница 89)
Тем не менее мы можем добиться, чтобы у каждого сравнения рассматриваемого типа справа стояла некоторая цифра. В самом деле, сравнение х р=1 (шоап) может быть заменено и-членной днзъюнкцией (!=О (шоан)б х.р'=О ( ак)) Ч(! О'( оаи)а .р=О ( оак)) ~/ ... !/ (1 = 0'" 11 (шоа и) й х. р 0'" '! (1ноа п)). После выполнения этой замены мы должны будем позаботиться о том, чтобы структура дизъюнктивной нормальной формы снова была восстановлена. После того как все это будет проделано, каждый дивъюнктивный член нашей нормальной формы будет представлять собой конъюнкцию членов, либо не содержащих х, либо имеющих один из следующих) видов: х р+т(з, 11(х-р+ 3, х р 11 (шоа',и), где ь -- цифра, а 1 с 5 не обязаны быть цифрами.', Р) Для конъюнкции сравнений вида х р|— = 1 (шоа п) (у различные сравнений цифры р, з, и могут быть разными) имеет место следующая элементарно-арифметическая альтернатива: либо эти сравнения не имеют общего решения, либо опи равносильны одному единственному сравнению вида ат), где д Снова является'; цифрой.
В том, какой из этих двух случаев имеет место на самом деле, можно разобраться злементарными средствами, причем во втором случае можно будет отыскать и сами цифры ц и ш. В первом случае мы заменим рассматри- ") в — ! здесь обовиававт ссстввтствующую циФру. РЕКУРСИВНЫЕ ОПРЕДЕЛЕНИЯ !ГЛ. У11 ваемую конъюнкцию неравенством О ( О, а во втором случае мы ааменим ее соответствующим равносильным ей сравнением хм д (шод ю). В случае конъюнкции, состоящей иэ неравенств, содержащих х, мы прежде всего можем добиться того, чтобы в каждом иэ неравенств этой конъюнкции переменная х встречалась в одном и том же сочетании х.Р+1. Действительно, если у нас имеются два неравенства х Р1+ 21(В1 и Р.
(-; ((В„ то вместо чих мы можем написать два других неравенства х'(Р1'Рг)+(21'Рг+ гг'Р1) < В1'Рг+ 22 Р1 и х'(Р1'Р2)+(21 Р2+22'Р1)(В2'Р1+21'Рг! аналогичным обрааом мы можем поступить и в случае двух неравенств х Р1+21(В1~ Вг<х'Рг+гг или соответственно В12(гх'Р1+ го Вг(1х Рг+12. Тем самым число различных сочетаний х*Р+1, в которых х встречается внутри рассматриваемой конъюнкции неравенств, уменьшится на единицу, и путем повторения этой операции оно в конце концов будет доведено до !. Если теперь у нас имеется конъюнкция неравенств, имеющая вид ;х.Р+1<В1б1 ° ° ° П1х Р+1<ВЫ то мы можем эаменить1 2ее Ь-членной диэъюпкцией,!-й член которой будет иметь вид В1<В1+! б1В! <Вг+! б1 ...
81 В!<Вь+1йх Р+1<В!. Аналогично, конъюнкцию г,(х-Р+1б2 ... б,г,„<х.р+! 6Ч пРедстьвимость РекуРсивкых Функций мы эаменим П1-членной диэъюнкцией с общим членом 447 г, (гВ+1 А г,<г!+ ! б1 ... б г„(г!+1 А 2!<х Р+1. В результате этих эамен вид нашей диаъюнктивной нормальной формулы нарушится. Если эатем снова восстановить его, то каждый диэъюнктивный член будет содержать переменную х самое болыпее в трех членах конъюнкции — а именно, не более чем в одном сравнении вида Хм— и Д (ШО11 П) (с цифрой а) и не более чемг в одном иа неравенств каждого иэ следующих двух видов: а<х.Р+1! и х. Р+ 1((,"Ь, Эх(х =,'д (шой п)о1а(х Р+1о1х.р+1( Ь), либо отличаются от него только отсутствием одного или двух членов стоящей под квантором конъюнкции.
Случай, когда член а(х.Р+1 отсутствует, мы можем специально и не рассматривать, так как вместо неравенства х Р+1< Ь мы всегда можем написать конъюнкцию О < х Р+ 1' б1 х Р+1' ( ь'. Если у конъюнкции отсутствует член х-Р+1<Ь, причем в том случае, когда оба этих вида встречаются одновременно, выражение х Р + 1 в обоих случаях будет одно и то же. После того как выражение 1Л (х) операциями а), б) и в) будет преобраэовано в диэъюнктивную нормальную форму, обладаюгцую указанными простыми свойствами, мы поставим перед ним квантор существования лх и распределим этот квантор на все члены диэьюнкции в отдельности, если они еще содержат х.
Затем у каждого члена, начинающегося квантором Эх, мы вынесем из-под Эх конъюнктивные члены, не содержащие х. Теперь нам осталось исключить переменную х только иа таких выражений, которые либо имеют вид % 4) предстлвимссть РекуРсиВных а4ункций ч49 $Г4Ь У13 РЕКУРСИВНЫЕ ОПРЕДЕЛЕНИЯ то мы все выражение в целом заменим истинной нумерической формулой 0 (0'. Если в конъюнкции отсутствует сравнение и 44 равно 1, то у нас оказывается формула Зх(а(.а+Г8 х+14 -Ь) и вместо нее мы можем написать аи( Ь84 1 ( Ь. Если же сравнение отсутствует, а цифра р больше х, то выра- жение Зх(а((~х Р+184х ° )4+1(Ь) может быть заменено формулой Зх (х = 0 (шоб Р) 8 а ( * + 1 8с х + 1 ( Ь), что и возвращает нас к основному случаю конъюнкции с тремя членами, с той особенностью, что р равно 1.
Эта специализация может быть достигнута и в случае полного выражения Зх(х — 9 (шойп)84а(х )4+18сх )4+1((Ь), если мы заменим его формулой Зх(х= — р р (шобп р) йа(х+184х+Г(Ь) и подставим в нее вместо терман 9 р и и р цифры, являющиеся их значениями. Таким образом, нам осталось рассмотреть только выражение Зх(хж 9 (шос)п) 84а<х+184х+1(Ь), где Ь вЂ” цифра, в то время как а, Ь и 1 цифрами быть не обя- заны.
При этом относительно цифры Ь можно предполагать, что опа представляет собой одну ив цифр от 0 до а — 1; действитель- но, если бы в сравнении первоначально стояла цифра, превосхо- дящая и — 4, то вместо нее мы могли бы ваять остаток, получаю- щийся при делении ее на и. Каждое такое выражение мы заменим теперь дизъюнкцией (а (1841+ Ь (Ь) )/ З)4 Ч)ше ~/ ° . ° ')/ Эа, где В4 сокращенно обоаначает конъюнкцию Р 1( а484а+Р(Ь84а+Р— 1+Ь (шобп). После того как рассматриваемая подформула Зх Я(х) будет указанным образом заменена выражением, не содержащим переменной х, мы сможем, в случае надобности конъюнктивно присое- динив члены вида а = а, добиться того, чтобы в выражении, фигурирующем теперь вместо Зх Я(х), встречались Все те отличные от х переменные которые встречаются в Я (х).
Тем самым мы описали процедуру замены внутренних подформул вида.Зх Я(х), а вместе с пею и процедуру редукции. Отправляясь от этого описания, мы можем теперь констатировать наличие у процедуры редукции перечисленных выше свойств 4 — 8. Свойства 4 — 6 усматриваются непосредственно. Проверка свойства 7 протекает аналогично докааательству леымы 2 из гл. 4'1 путем точной имитации процедуры редукции с помощью рассмотрений, относящихся к области элементарной интуитивной арифметики.
Существенно более трудной является проверка свойства 8, Здесь нужно будет показать, что каждый шаг процедуры редукции представляет собой преобразование в смысле переводи- мости '), причем, в частности, придется существенным образом использовать аксиому индукции. Основываясь на свойствах 1 — 7 нашей процедуры редукции, теперь можно будет полностью перенести из гл. 4гг те рассуждения, с помощью которых мы получили т е о р е и у о б о д н означности и теорему о частичной редукц и и е).
Из теоремы об однозначности вытекает, что если из двух редукций какой-либо формулы одна является зерифицируемой, то тогда верифицируемой будет и другая. Формулу со связанными переменными (но без формульных переменных), как и прежде, мы будем называть вврифицируемой, если она имеет верифицируемую редукцию. Имеет место теорема о том, что всякая формула, выводимая средствами системы (В) (с добавлением явного определения для а ( Ь), является вврифицируемой. Для докааательства этого факта изменения по сравнению с соответствующим докааательством иа гл. у'4 потребуются лишь постольку, поскольку теперь среди наших аксиом заранее имеется аксиома индукции. Тем не менее в результате этого не возникает никаких трудностей. В самом деле, аксиому индукции мы по- прежнему можем свести к схеме индукции.
Исключение формульных переменных тоже, как и в предыдущем случае, может быть произведено с соблюдением необходимых мер предосторожности. Нам остается теперь только показать, что если две формулы Я (О) и Я (г)-4-Я (г') верифицируемы, а переменная г (вместо которой, разумеется, может фигурировать и какая-нибудь другая свободная индивид- ') Перееоппмость будет, конечно, иметь место лишь в тоы случае, если к системе (П) будут добавлены явные определения для ( и длл сравпеллй. е) Сы.
с. 295 — 301. 29 д. Гельверт, Н. Верлеае 1гл. чп РЕКУРСИВНЫЕ ОПРЕДЕЛЕНИЯ 50 ная переменная) входит только на местах, указанных в качестве аргумента, то Я (а) также будет верифицируемой. Но это вытекает нз того, что при указанных предположениях формула Я (3) верифицируема для любой цифры 3. Ив теоремы о том, что всякая выводимая формула бев формульных переменных является верифицнруемой, в частности, вытекает непротиворечивость системы (В). Обратное утверждение, что всякая верифицируемая формула является также и выводимой, может быть получено ив свойства 8 процедуры редукции, если воспользоваться выводимостью всякой истинной нумерической формулы системы (В), выводимостыо истинных неравенств и сравнений, а также теоремой о частичной редукции ').
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
