Гильберт, Бернайс - Основания математики. Логические исчисления и формализация арифметики (947375), страница 77
Текст из файла (страница 77)
С атой целью мы прежде всего воспользуемся формулами а — Ь = а' — ' Ь' и а — ' Ь' = б (а — ' Ь), из которых, произведя подстановки и применив аксиому равенства, получим равенство Ь вЂ” ' а = 6(Ъ' — а). Далее, с помощью аксиомы равенства из выводимой по схеме индукции формулы а ~ 0 -е- б (а)' = а мы получим вспомогательную формулу б (а) = 0 81 а чь 0-+ а = 0'. Произведя подстановку в зту вспомогательную формулу и воспользовавшись предшествующим ей равенством и аксиомой (э"в), мы получим Ь вЂ” ' а = 0 8т Ь' — ' а -ь 0 -~ Ъ' — а = 0'. Тем самым все сводится к выводу формулы 1) е) Ь' — 'а~=08т Ь' — 'а=О'-е Ь=а. Сначала выведем формулу Ь' — а ~ 0 е- Ь' †' (Ь' †' а) = а, которую сокращенно обозначим через В(Ъ, а).
При помощи аксиомы равенства ив формул Ь' — ' 0 = Ь' и Ь' — ' Ь' = 0 получим равенство Ь' †' (Ь' †' 0) = О. Следовательно, выводима формула В (Ь, 0). Если мы сможем вывести еще и В (Ъ, а) -~ В (Ь, а'), то с помощью схемы индукции получим искомую формулу В (Ь, а).
Вывод формулы В (Ь, а) -+. В (Ь, а') получается разбором двух случаев: а = 0 и а чь О. Действительно, с одной стороны, из формулы В (Ь, 0'), которая получается аналогично В (Ь, 0) в реаультате формализованного вычисления терма Ь' — ' (Ъ' — ' 0') (с использованием формул Ь' — '0'=Ь вЂ” 'О, Ь вЂ” 'О=Ь, Ь' — Ь=О'), мы, польвуясь аксиомой равенства и преобразованиями исчисле- ния высказываний, выведем формулу а = 0-»- В (Ь, а').
Для вывода формулы а -ь 0 -э (В (Ь, а) -е. В (Ь, а')), ') Посылка Ь' — ' а ф О, сама но себе лишняя в этой формуле, добавляетен для унрощення дальнейших выводов. РЕКУРСИВНЫЕ ОПРЕДЕЛЕНИЯ (гл. Уц 374 с 1) некОтОРые пОяснения пРинципиАльнОГО хАРАктеРА 375 т. е. (после соединения посылок) а чь 0 & (Ь' — ' а чь 0 -» Ь' — ' (Ь' — ' а) = а) -» (Ь вЂ” 'а'~0-»Ь' — '(Ь ' а) =а), мы сначала с помощью формул д' — 'а' =6(Ь' — 'а) и 6(с)„-АО-»С~О (во второй из которых вместо с надо будет подставить Ь' — ' а) выведем формулу Ь' — ' а' ~ 0 -~- Ь' — ' а ~ О.
Легко показать, что нам остается вывести формулу а чь 0 & Ь' — ' а ~ О & Ь' — (Ь' — ' а) = а -» Ь' — ' (Ь' — ' а') = а'. Для вывода атой формулы мы испольэуом слодующио две формулы: Ь' — ' а Ф О вЂ” » Ь' — ' (Ь' — ' а) = 6 (Ь' — ' (Ь' — ' а')) И а чь 0 & 6 (Ь' — ' (Ь' — ' а')) = а -» Ь' — ' (Ь' — ' а') = а', первая иэ которых получается с помощью формул а ~ 0 -» 6 (а)' = а и Ь' — с' = 6 (Ь' — ' с), а вторая — с помощью формулы а ~ О & 6 (с) = а -~- с = а', Искомая формула теперь может быть выведена из двух полученных нами формул при помощи аксиомы равенства и средств исчисления выскааывапий.
Теперь, после того как индукцией по а мы завершили вывод формулы й) (Ь, а), т. е. Ъ' — ' а чь 0-» Ь' — ' (Ь' — а) = а, мы с помощью аксиомы равенства и средств исчисления высказываний получим формулу Ь' — ' а ~ 0 & Ъ' — а = 0' -~- Ь' — ' 0' = а, а отсюда, ввиду того, что Ь' — ' 0' = Ь,— формулу Ь' — 'ачьО&Ь' — 'а=О' -»Ь=а. Но это и есть та формула а), которой яам не хватало для вывода формулы Ь вЂ” ' а~О& с — ' ЪчйО-»с — 'а~О, с) См.
формулу (с) ка с. 373.— Прим. рад. а эта последняя по определению выражения а < Ь переводится в формулу (<,). Следует, впрочем, отметить, что иэ формулы Е (Ь, а) с помощью формул 0 — 'а=О, Ь~Π— »Ь=6(Ь)', (1х) разбором случаев Ь = 0 и Ь Ф 0 без труда получается формула Ь вЂ” ' а ~ 0 -» Ь вЂ” ' (Ь вЂ” ' а) = а. Выводя нашу формулу й (Ь, а), мы попутно получили и формулу Ь вЂ” ' а = 0 & Ь' — ' а ~ 0 -» Ь = а х); из этой формулы, производя подстановку а' вместо а и пользуясь равенством Ь' — ' а = Ь вЂ” ' а, формулой Ь = а'-» а = Ь, а также средствами исчисления выскааываиий, мы получаем формулу Ь вЂ” а ~ 0-» а' = Ь )/ Ь вЂ” ' а' чь О, которая, с одной стороны, по определению неравенства а < Ь переходит в формулу а < Ь -» а' = Ъ ')/ а' < Ь, а с другой стороиы, дает формулу Ь вЂ” ' а = 0' — » а' = Ь.
Из выведенных формул (<,), (<х) и (<,) и только что упомянутой формулы а < Ь -~- а' = Ь ~/ а' < Ь с помощью аксиом равенства и схемы индукции, но без использования связанных переменных можно вывести формулы ") (а<0), а<Ь-» ~(Ь<а'), а~Ь- а<Ь )/ Ь<а, как это было установлено в гл. У1 х). Таким образом, все формулы систем (А) и (В), не содержащие связанных переменных, могут быть выведены средствами элементарного исчисления со свободными переменными с добавлением 1) Вывод атой формулы, а теы самым к вывод формулы (<,), в первом кадавкк получался с привлечением рекурсивного окределеккя суммы а + Ь, которое было Использовано для вывода формулы Ь вЂ” ' а = 0' » а' = Ь; то, что его обрашекке к сумме является вэлвшкик, было замечено Г.
Крайээаоы, к письменному сообшавкю которого (февраль (962 г.) и восходит вышеУпоыявутый вывод. х) См. с. 330 — 333. 377 !Гл. Уп РЕКУРСИВНЫЕ ОПРЕДЕЛЕНИЯ $ 31 376 РЕКУРСИВНАЯ АРИФМЕТИКА схемы индукции из аксиомы равенства (7 ), формулы О' ~ О и рекурсивных равенств для функций б и а — ' Ь с иснользованием явного определения для а ~ д. При этом подходе арифметические аксиомы, касающиеся штрих- функции и првдиката а ( Ь, ааменяются рекурсивными равеы., ствами, к которым дополнительно присоединяется нумеричвская формула О' ~ О.
$2. Рекурсивная арифметика 1. Вывод законов для сложения, вычитания, умножения и для символа (. Возможности рекурсивных определений вще больше проявляются при систематическом развертывании формализма, который получается, если за основу взять алементарнов исчисление со свободными переменными, аксиому равенства и формулу О' ~ О, при широком использовании рекурсивных определений (наряду с явными) и схемы индукции. При помощи этого формализма можно строить понятия элементарной арифметики и формально выводить различныв ее теоремы — например теоремы о наибольшем общем делителе и об одыозыачности разложения чисел на простые множители.
Такой способ изложения арифметики был предложен Сколемом в $923 г.г). Мы продемонстрируем адесь несколько характерыых результатов этих рассмотрений. Дальнейшему иаложвнию мы првдпошлвм обзор арифметических законов, которым подчиняются операции сложения и умножеыия, а также функция а — ' Ь; вместе с этим мы рассмотрим некоторые отыосящиеся 'сюда формулы и кратко наметим их выводы.
Прежде всего, для суммы а + Ь при помощи рекурсивных равенств с использованием схемы индукции могут быть выведены формулы О+а=а а'+Ь=а+Ь'. С помощью этих двух формул мы получим, пользуясь полной индукцией, закон коммутативности сложения а+ Ь = Ь+ а. Закон ассоциативности сложения а+(Ь+с) =(а+Ь)+с, г) Я Ь о 1 е га Т. Веягйпйппя йег е1ешеп!агеп Аг!гЬше!!Ь йпгсЬ 6!е геЬпгт!егепйе 17епЬггеше оЬпе Апчепйппх есЬе!пЬегег Ъ'егепйег1!сЬеп ш!! ппепд1!сЬеп АпейеЬпппзчЬеге!СЬ.
— УыепеЬерые1е1гареге ЯЬг!!гег, 1, Ма!.-!Чаы К1., !323, Рз 6. как уже было упомянуто, выводится индукцивй по с. Для умыожвния а Ь с помощью полной индукции мы сначала получим Оп=О. Затем, используя закон ассоциативности сложения, а также формулу а + Ь' = Ь + а', которая получается из формулы а' + Ь = а + Ь' и закона коммутатнвности сложеыия, мы полной индукцией по Ь получим формулу а' Ь=(а Ъ)+Ь. Эту формулу мы будем писать также и без скобок, пользуясь п инятым в математике соглашеыием о том, что произведение Р а Ь, являющееся членом суммы, не обязательно заключать в скобки. Используя эту формулу и формулу О а=О, мы можем получить — полной индукцией по какой-либо иэ переменных — закон коммутатявности умножения а Ь = Ь а.
Закон правой дистрибутнвыости а (Ь + с) = а Ь + а.с получается полной индукцией по с с использованием закона ассоциативности сложения. Иэ закона правой дистрибутивности и закона коммутативности умножения получается закон левой дистрибутивности (Ь + с) а ~ Ь а + с а. С помощью закона правой дистрибутивыости полной индукцией по с мы получаем, наконец, закон ассоциативности умножения а.(Ь с) = (а Ь) с. Ввиду наличия законов ассоциативности сложения и умноже- ния, цвлвсообравно,— как это общепринято в математике,— опус- кать в многочленных суммах и проивведениях скобки, Для а —" Ь ужв была установлена выводимость формул Π— а=О, а — 'а=О, а' — ' Ь' = а — ' Ь. 379 РВКУРСИВНЫВ ОПРВДВЛВНИЯ 378 и'л уп РИКУРСИВНАЯ АРИФМЕТИКА С помощью последней из них мы индукцией по с получим (а+с) — (Ь+с) =а — 'Ь.
Подставив в эту формулу О вместо д, а затем Ь вместо с и пользуясь равенством О+а=а, мы получим формулу (а + Ь) — ' Ь = а. Далее, индукцией по с мы получим а — ' (Ь + с) = (а — ' Ь) — ' с, а отсюда, в частности, а — ' (а + Ъ) = О.
Кроме того, индукцией по Ь может быть выведена формула а с — Ь с = (а — Ь) с. Для этого надо воспользоваться формулами Оа=О, а' Ь=аЬ+Ь, только что упоминавшейся формулой а — '. (Ь+с) =(а — . 'Ь) — с и формулой а с — 'с=(а —.0') с, которая получается индукцией по а с использованием равенства (а+Ь) —:Ь а. Иа формул (а + Ь) — '. Ь = а, 0 —: а = 0 получается формула а+ Ь =О-ьа=О, а из нее в сочетании с законом коммутативности сложения получается а + Ь = 0 -э а = 0 А Ь = О, а тем самым и формула а+Ь =0 ° а =08сЬ =О. Соответствующая формула для произведения имеет вид а Ь=О а=0)/Ь=О.
Она выводится из формулы Ь ~ О -+- (а Ь = 0-+. а = О), которая получается с помощью уже упоминавшейся выводимой формулы а ~ 0 -~- а = б (а)' и формулы а + Ь = О -»- Ь = О. Основываясь на определении отношения а ( Ь а(Ь Ь вЂ”:аФО и используя арифметические законы, выведенные для а — ' Ь, мы можем для этого отношения, кроме уже упоминавшихся ранее формул '), получить следующие две формулы: а<Ь а+с<Ь+с и с ~ 0 -~- (а ( Ь а с ( Ь. с). Первая из них получается иэ равенства (а+с) — '(д+с) =а — „' Ь, а вторая — из равенства ос —:Ьс=(а — 'Ь) с в сочетании с формулой а Ь=О а=ОгнЬ=О. Как мы недавно установили '), с помощью рекурсивных равенств для б (л) и а — Ь может быть выведена формула а чь Ь - а ( д )/ Ь < а.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
