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