Гильберт, Бернайс - Основания математики. Логические исчисления и формализация арифметики (947375), страница 90
Текст из файла (страница 90)
Таким образом, в формализме системы (В) верифицнруемость также совпадает с выводимостью. Ив полученных результатов вытекает, что если формула, принадлежащая нашему формализму, не содержит свободных переменных, то либо она сама, либо ее отрицание выводимо. Проверка того, какой именно из этих двух случаев имеет место, проивводится при помощи процедуры редукции; при этом в случае выводимости соответствующей формулы она дает нам также н способ, позволяющий найти вывод атой формулы. В частности, если выводимая формула без свободных переменных имеет вид Зх Я(х), то процедура редукции ведет к нахождению такой цифры 3, что будет выводимой формула Я (3) (это последнее вытекает иэ теоремы о частичной редукции).
Что же касается формул вида 1~х Я(х), не содержащих свободных переменных, то каждая такая формула выводима тогда и только тогда, когда для каждой цифры 3 выводима формула Я(3). Таким образом, система (П) обладает теми же самыми свойствами полноты, что и системы (А) и (В), н в той же самой мере позволяет производить проверку разрешимости всех формулируемых в пей проблем. Однако с этим преимуществом связана и определенная недостаточность в отношении изобразительных способностей этого формализма. Действительно, рассмотрим в формализме системы (В) (подобно тому, как это делалось в системе (В)) формулы, содержащие а в качестве единственной свободной переменной.
Каждая такая формула либо сама является своей собственной редукцией, либо переводима в нее. Эту последнюю снова можно перевести (методами, которые использовались в процедуре редукции) либо в истинную формулу О = О, либо в ложную формулу О ( О, либо в дизъюнктивную нормальную форму, члены которой суть конъюнкции составных частей вида а=— р(шойи), 1(а р, а.р(1 ') См. соответствующие сообрая<ения в гл. Ч1, с.
310 — 314. предстлвнмость Рекурсивных Функции 451 гдер,1.1 — ифы п ц ьр ричем в каждан ив этих конъюнкции встречается не более о видов. диого члена каждого иэ трех указанных Далее, неравенство 1(а р переводимо в некоторую нижнюю оценку т«а, а неравенство а р ( 1 в свою очередь переводимо в некоторую верхнюю оценку а ( 3. ем самым наша исходная формула переводима либо в некоторую истинную,, либо в некоторую ложную нумерическую фо м л представляет б " ую форму, каждый член которой ля а н зляет со ои конъюнкцию не более одной ни жнеи оценки д , е более одпои верхней оценки для а б сравнения а и не олее одного а =— р (шой и).
Для такои дизъюнктнзной нормальной формы име ая а меет место следуюжится некото ая ве щ льтернатива. Либо в каждом ее дизыонкт ктивном члене содере оторая верхняя оценка для а; тогда прн всякой замене а цифрой, большей, чем входящая в эту верхи ерхнюю оценку циь а одной ве хне" жит по краинеи мере один член, в котором пе встречается н р й оценки, так что он состоит или из некото ой нн я ни ней оценки, нли из сравнения а = р (шой и), или из конъюнкции нижней оценки и с а тем самым и сравнения; тогда этот член, тем самым и вся дизъюнктивная нормальная фо а форма, перейдет у формулу, если а заменить достаточно большой цифрой, которая (при наличии сравнения) при делении на и самьш остаток что и р.
на и дает тот же р у Я ( ) отсюда теперь вытекает, т Для исходной фо м лы (а има ли о для всех достаточно больших цифр 3 ф Я ( ) д, либо можно указать трн такие ци ы ормула Я (3) выво- что для любой циф ы б Ры 3, ольшей 5ь и дающей п н елен на и остаток т, выводима фо и ла Я (" . ванная ал ормула (3). Таким образом, ука- фо мали я альтернатива имеет место для всякой ф р вма, содержащей единственную перемени ю а. Эт сякой формулы нашего руживает се ьевн ю ог ан р у раниченность ивобравительных возмож- ностей нашего формализма. 29* пгедстлвиыость РекуРсиВных Функций 453 (ГЛ, У11 РЕКУРСИВНЫЕ ОПРЕДЕЛЕНИЯ 452 В частности, отсюда следует, что функция а Ь не представима в формализме системы (О). Действительно, если бы равенство а Ь=с было представимо некоторой формулой й(а, Ь,с), принадлежащей формализму системы (О), то эту формулу можно было бы выбрать так, чтобы в ней не встречалось никаких свобод- ных переменных, кроме а, Ь и с, а также чтобы в нее не входила связанная переменная х.
Эта формула й (а, Ь, с) должна была бы ф 1 ( Ш обладать тем свойством, что для любой тройки цифр для которой вычисление аначения 5 ( дает цифру ш, средства- ми системы (О) выводима формула й(5, (, ш), а для любой тройки, у которой вычисление 1.( дает аначение, отличное от ш, выводима формула ) й(1, (, ш). Формула Зхй(х, х, а) содержит одну-единственную свободную переменную а, и для нее должна жна была бы иметь место указанная альтернатива, т. е. либо для любой достаточно большой цифры 1 должно было бы бы ть выводимым отрицание формулы Лхй(х, х, Ь), а потому и формула чх ~ й (х, х, 3), либо можно было бы указать также цифры и и т, что т мень ше и и что для любой достаточно большой цифры Ь, дающей при делении на и остаток т, была бы выводимой формула Вх й (х, х, 3).
ин из этих двух случаев не может иметь места, так Однако ни один и как в первом случае для достаточно большой цифры з и для любой цифры г была бы выводимой формула 1З($, Р, 3) и поэтому, на о на основании предположенного свойства формулы й (а, д, с), для любой достаточно болыпой цифры 3 и для лю о цифры 5 аначение 1 5 должно быть отлично от 3, в то время как сколь угодно далеко имеются цифры, допускающие представление в виде 1 1. Во втором случае для всякой достаточно большой цифры 3, дающей при делении на и в остатке 1, (по теореме о частичной редукции) можно было бы указать цифру г, такую что формула й(Р, 1, 3) выводима, и тем самым значение 1 1 было бы равно 3. Таким образом, для всякой достаточно большой цифры р значение Р и + т было бы представимо в виде г.й Однако это очевидным образом неверно.
Действительно, если в качестве р мы возьмем цифру, ббльшую и, н если Р.и+1=1 1, то цифра 1 больше и и значение р' и + 1, с одной стороны, больше 1 1, а с другой — меньше 1 1'. Но между 1-1 н 1' 1' нет цифр, представимых в виде значения какого-либо произведения вида 1 й Таким образом, Р' и + 1 не представимо в виде 1 г. Тем самым получается, что добавление к системе (О) функции а Ь и ее рекурсивных равенств ведет к существенному расширению нашего формализма.
Таким образом, система (О) во всех отношениях ведет себя аналогично системам (А) и (В). Попутно отметим также, что все это рассмотрение, в том виде как мы провели его для системы (О), может быть проведено н для системы (О1), получающейся из (О) путем присоединения функции а — ' Ь вместе с формулами а — '(а+Ь) =О, (а + Ь) — ' Ь = а. В формализме этой системы функция а. Ь также оказывается непредставимой 1). 4. Изменение ситуации в случае добавления рекурсивных равенств для умножения; система (Ц. Можно было бы думать, что при добавлении новых рекурсивных функций всегда будет повторяться ситуация, аналогичная той, с которой мы встретились при рассмотрении систем (А), (В) и (О).
Тем не менее это не так; уже при добавлении функции а Ь и ее рекурсивных равенств ситуация оказывается в корне иной. В результате добавления ) Это получается, впрочем, уже Вз того факта, что функция ° 5 цредсталнма в формалнамв снстемм (Р) (см. с. 439 — 440). РВКУРСИВНЫК ОПГНДНЛЯНИЯ ;1гл. Уп првдстАвнмость РзкуРсивных Функций 455 функции а Ь к системе (П) получается следующая система аксиом: а = Ь- (А (а) -«А (Ь)), а'~ О, а' = Ь' — «а = Ъ, а+О=а, а+Ь'=(а+Ь)', а 0=0, а Ъ'=а Ь+а, А (0) де )(х (А (х) — «А (х')) -«А (а).
(Е) Чх Зу (х( у дг фт (у) де '81т (у")) соответствует утверждению о том, что за любым числом имеются пары простых чисел с разностью, равной двум. Оба зти утверждения знамениты тем, что вопрос об их справедливости представляет собой нерешенную математическую проблему. Если бы мы располагали процедурой редукции для системы (Е), аналогичной Если мы попытаемся доказать непротиворечивость этой системы (Е) нашими прежними методами с помощью процедуры редукции, то заметим, что эти методы здесь уже пе применимы. Именно, в случае рассмотренных нами до сих пор формализмов систем (Л), (В) и (П) выполнимость процедуры редукции существенным образом основывалась на том, что мы полностью овладевали вырааимыми в них арифметическими соотношениями.
Метод редукции как раз в том и заключался, что мы осуществляли полный математический контроль над тем фрагментом арифметики, который формализуется рассматриваемой системой. Поэтому и неудивительно, что этот метод позволял нам ответить на любой математический вопрос, формулируемый в рамках этого фрагмента. Но для формализма системы (Е) в нашем распоряжении уже не будет такого средства, позволяющего контролировать все выразимые в этом формализме математические соотношения. Эту мысль можно пояснить на примерах. Рассмотрим формулу 'у и 'з'о (и чь 0' дг и чь 0' -«ы Р =~ и), выражающую тот факт, что и является простым числом (если число 1 также считать простым).
Если мы для краткости обозначим эту формулу посредством 811 (и), то формула 'зх(х~ 0 — «Лунг(З»т(у) й'З»г(г) дех+ х=у+г)) будет изображать утверждение о том, что всякое четное число является суммой двух простых, а формула процедурам для предыдущих систем, то в результате ее применения мы получили бы решение этих проблем. Заметим, далее, что степень о для любого фиксированного показателя 1 может быть( изображена посредством 1-членного произведения (... '- и) ° ...), и если мы воспользуемся записью о как сокращением для этого произведения, то утверждение великой теоремы Ферма для фиксированного показателя степени г ) 2 в формализме системы (Е) будет изобра каться по редством формулы з ух(туев(х~~ О",де"у"~ 01-«;х1+ у ~(~~г1) .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
