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