Гильберт, Бернайс - Основания математики. Логические исчисления и формализация арифметики (947375), страница 96
Текст из файла (страница 96)
А (Ь) сгс (А (а) е- Ь = а ~/ Ь ( а); если мы подставим в яее вместо Ь терм р„А (х), то, используя сокращепие ~<, получим формулу % (рнА (х)) -е- (А (р„А (х)) сй (А(а) -+. р 4 (х) ~( а)), зс Д. Гнньйерт, П. Бернайс 432 понятие «тот, котОРыйа и его устРАнимость 1гл. чтлв а эта последняя вместе с упоминавшейся выше формулой ЗхА (х) — 1- И (1«„А (х)) с помощью основной формулы (Ь) и средств исчисления высказываний даст следующие две формулы: ЗхА (х) -+ А (12,А (х)), А(а)-»)2„А (х)<а. (1 ) (122) ()22) 'Фх 1А (х) -» )2 4 (х) = О, которая выражает тот факт, что для свойства Я (а), которое не выполняется ни для какого числа, 12„'21 (х) принимает в качестве значения О. Таким образом, рассматриваемая функция р„А (х) Формализует понятие числа, наименьшего среди обладающих определенным свойством либо равного О, если чисел, обладающих этим свойством, нет.
Введенное нами понятие идет существенно дальше, чем то, которое в рекурсивной арифметике было формализовано нами посредством выражения М1п Я (х), О:*<А так как это последнее, во-первых, применимо лишь к предикатам специального типа и, кроме того, оно содержит ограничение на интервал фигурирующих здесь чисел, которые должны не превосходить й. Иа содержательного смысла функции 12„А (х) можно немедленно заключить, что связанное с предикатом Я (а) число 12„Я(х) однозначно определяется множествол2 тех чисел, для которых этот предикат выполняется. Фант атой однозначной определенности «объемом» предиката формально выражается формулой \Ух (А (х) В (х)) — Р„А (х) = 12„В (х). Для установления выводимости этой формулы (в силу дедукционной теоремы) достаточно с помощью формулы Ух (А (х) ° В (х)) при незатронутых формульных переменных вывести равенство раА (х) = р„В (х).
Будучи истолкованы содержательно, эти формулы выражают тот факт, что для всякого числового предиката Ч (а), выполняющегося хотя бы для одного числа, символ )2„Я(х) изображает наименьшее число, для которого выполняется этот предикат. Для полного определения функции 12,С1 (х) нужна еще упоминавшаяся выше фор- мула »ПРАВИЛО И ОПЕРИРОВАНИЕ С НИМ Для этого мы сначала получим из ()2 ) формулы А (12„В (х)) — 12„А (х) < Д„В (х), В (р,А (х)) — «1«,В (х) < 12,А (х), которые совместно друг с другом дадут А (12„В (х)) А В (12,А (х)) — 1- 12„А (х) = р„В (х). Теперь мы воспользуемся формулой чх (4(х) — В (х)), из которой могут быть получены формулы ЛхЛ (х) — ЗхВ (х), А (а) — » В (а), В (а) — » А (а).
11ервая нз ннх в сочетании с формулами ЗхА (х) -» А (12„А (х)), ЗхВ (х) — » В (1«„В (х)), получающимися нз (рг), дает формулу ЗхА (х) -» А (12„А (х)) 42 В (р„В (х)); вторая и третья подстановкой вместо переменной а дают формулы А (12„А (х))-«В (12„А (х)), В (12„В (х))-» А (12„В (х)), так что в целом мы получим ЗхА (х) — » А (1«„В (х)) 8с В (р„А (х)), а ва нее, в сочетании с выведенной выше формулой А (12„В (х)) А В (12„А (х))-» 12„А, (х) = р„В (х), получим формулу ЛхА (х)-» )2 4 (х) = 12„В (х).
С другой стороны, применив еще раз формулу 'Фх(А (х) В (х)), мы получим 15х 1А (х)-» 'Фх 1В (х), а эта формула в сочетании с получающимися вз (122) формулами 'Фх 1А (х)-» р .А (х) = О, Чх 1В (х) -«- )2,В (х) = О и с формулой П,А (х) = О й р,В (х) = Π†» р„А (х) = р В (х) 22* РПРАВИЛО И ОПЕРИРОВАНИЕ С НИМ 4З4 ПОНЯТИЕ «ТОТ, КОТОРЫЙ» И ЕГО УСТРАНИМОСТЬ 1ГЛ, ЧП1 дает нам дает Ъ'х 1А (х) -~ р А (х) = р„В (х). Но две полученные нами формулы ЗхА (х) ».
р .А (х) = р,В (х) Ъ'х 1А (х) -+. р„А (х) = р„В (х) совместно друг с другом дают искомое равенство р 4 (х) = р„В (х). Однозначность, аналогичная той, которая для функции р„А (х) иаображается выводимой формулой Ъ'х(А (х) В (х))-«- р 4 (х) = р„в (х), имеет место также и для того соотнесения индивида предикату, которое формализуется с помощью ь-символа. Однозначность эта формально выражается в том, что для произвольных формул 91 (а) и В (а) с выводимыми формулами единственности окааывается выводимой формула 'Ух (Я (х) В (х)) -» ~„Я (х)= ~,.В (х).
Мы докажем адесь и этот факт. Для этого достаточно будет показать, что в том случае, когда для Я (а) и для В (а) оказываются выводимыми формулы единственности, из формулы Чх(Я(х) В(х)) при незатронутых входящих в нее свободных переменных может быть получена формула ~АЯ(х) = ~„В(х). Прежде всего, с учетом выведенных формул единственности, ыправило дает нам формулы Я(ь,Я(х)) и В(~ В(х)). Из формулы чх (Я (х) В (х)) может быть получена формула 'Фх(Я (х) -«-В (х)), откуда, далее, получаем Я (ь . Я (х)) -«В (ь.Я (х)); а эта формула вместе с формулами Я(ь;Я(х)) и В(~.В(х)) В (ь„Я (х)) Й В (ьлВ (х)).
С другой стороны, иэ второй формулы единственности для В(а) мы получаем формулу В (~„.Я (х)) Ь В (~,В (х)) -~- ь,Я (х) = ~,В (х), которая вместе с предыдущей формулой дает равенство ~„Я (х) = ь„В (х). Заметим, что в этом выводе формулу 'чх (Я (х) В (х)) мы использовали только для получения формулы ч х (Я (х) -» В (х)). Из атого обстоятельства вытекает, что в случае выводимости фор- мул единственности для Я (а) и для В (а) формула 'ч х (Я (х) -+ В (х)) -1- ~„Я (х) = ~„В (х) также является выводимой. Заметим, что вывод этой формулы иа формул единственности для Я (а) и для В (а) протекает бев использования аксиом равенства, при помощи одного лишь ~-правила и средств исчисления предикатов.
На примере рассмотренных нами формул однозначности обнаруживается то преимущество, которое дает нам введение функции р 4 (х) по сравнению с оперированием с ь-символом: в то время как доказуемость формул однозначности для ь-символа мы можем констатировать лишь в каждом отдельном случае, для функции р„А (х) у нас оказывается общая формула одноаначности, которая включает в себя все эти частные случаи. Зто различие возникает вследствие того, что р„А (х) является терь~ом независимо ни от чего, в то время как при введении ь-термов мы оказываемся связанными выводимостью формул единственности.
С этой точки зрения важно уяснить себе, что функция р„А (х), после того как она однажды была введена с помощью ~-символа, начиная с этого места вообще может быть использована для замены ысимвола, так что любое дальнейшее применение ыправила оказывается ненужныль. Именно, если для формулы Я (а) окажутся выводимыми формулы единственности, то будет выводимым и равенство ~„Я (х) «= рвЯ (х). Действительно, в этом случае, согласно ыправилу, мы получим Я (ь„Я (х)). 433 пОнятие «тот. кОтОРыи» и его устРАнимость 1гл, чп« 1 21 дедуктивное постгокник АРИ»метики 437 Далее, из формулы (р,) н из первой формулы единственности для Я (а) можно получить Я (р„Я (х)), так что ыы будем иметь Я (ззЯ (х)) б> Я (рзЯ (х)).
С другой стороны, из второй формулы единственности для Я(а) получается формула Я (»„Я (х)) А Р( (р„Я (х)) -«- >зЯ (х) = рзЯ (х), так что мы действительно приходим к равенству >зЯ (х) = )з Я ( )- Таким образом, в случае формул Р[ (а), для которых ыправило допускает введение терма»„Я (х), роль этого терма в известной мере берет на себя терм р и Я (х), и тем самым, используя функцию )>„А (х), мы можем обойтись без введения ытермов по >-правилу, т. е. без вывода соответствующих формул единственности.
Разумеется, такая возможность имеется только в арифметике, где действует принцип наименьшего числа, в то время как формализованное с помощью з-символа понятие «тот, который» обладает универсальной применимостью. 3 2. Дедуктивное построение арифметики на основе системы аксиом (Х) с добавлением формализованного понятия наименьшего числа 1. Понятие «меньше»; сравнения; деление с остатком; делимость; взаимно простые числа. Для введения функции )з„й(х) мы из арифметики использовали здесь только аксиомы системы (В). Теперь мы добавим рекурсивные равенства для сложения и умножени и таким образом перейдем от системы (В) к системе (Х).
Значение функциональной конструкции («„А (х) полностью раскроется только в рамках этого формализма. В частности, мы покажем, что с помощью функции )ззА (х) все остальные рекурсивные определения можно будет гаменить явными определениями. В качестве подготовки мы должны будем проследить за формалигацией некоторого фрагмента арифметики в том виде, как она получается на основе аксиом системы (Е) с добавлением функционального гнака )>зА (х) и относящихся к нему формул ()з>) ()зз) и ((»з). Этот способ изложения арифметики представляет собой полную противоположность рекурсивной арифметике; то, что там удавалось достичь при помощи рекурсивных определений, здесь получится в результате использования связанных переменных, в частности, с помощью функции рзА (х).
Поэтому те «ке самые арифметические отношения и функции теперь появятся в новом формальном изложении; но все же ыы позволим себе сохранить для них прежние символы, как мы уже делали это в отношении символа (. В самом деле, символ а < Ь мы сначала (в гл. 171) ввели в качестве основного знака, затем в рекурсивной арифметике мы ввели его при помощи функции а -'- Ь посредством определения 2) ас Ь Ь вЂ” 'а~О, а после этого, используя связанные переменные, мы ввели его прн помощи функции а + Ь посредством определения а < Ь Лх(х ~О «ха + х = Ь).
Это последнее определение мы и возьмем аа основу для дальнейшего. Из этого определения могут быть получены (как мы показали в гл. >(11 2) при рассмотрении системы (П)) формулы ((>), ((2), ((,), а также а(Ь- а' = Ь 1/ а'(Ь, из которых дальше (как было установлено в гл. ч'> з)) могут быть выведены формулы а = Ь 1/ а(Ь >/ Ь<а и а(Ь-«-'1(Ь<а'). Кроме того, к этому могут быть добавлены формулы а(Ь-«-а+ с< Ь+ с, с ~ 0 — ~ (а .
Ь а.с < Ь с), которые получаются с помощью законов для сложения и умножения '). Далее, из определения для а ( Ь получается эквивалентность а < Ь Лх (а + х = — Ь). Мы начнем теперь с определения сравнения по модулю и а = — Ь (шой и), которое формулируется следующим образом з): а = Ь (шо«( и) Лх (а = и х + Ь 1/ Ь = и х + а). ') См. с. 370. з) См. с.
439. з) См. с. 332. «) См. с. 379. з) Следует сравнить с этим приведенное в гл. Ч11 (см. с. 441) опредвлепие для а»в Ь (п>о«( 1) при фиксированной цифре 1. В рамках системы (1«) мы были вынуждены ограничиваться цифраии 1, тли иаи в вашем распоряжепип ие было фуииции а 6. в»89 Ь + г = р (а, Ь) -э р (а, Ь) ( г, Затем из равенства а = Ь О+ а 1»99 ПОНЯТИЕ»ГОТ, КОТОРЫЙ» И ЕГО УСТРАНИМОСТЬ 1ГЛ, Чгн Иа этого определения, в силу законов для сложения и умножения, а также формул а+с= Ь+с — ~а = Ь, а=6~а<Ь~/Ь<а могут быть получены следующие формулы: а =— а (шоб п), а в— м Ь (шой п) А а = с (шой и) -». Ь = — с (шо1) и), а= 6(пкн) п) а+ с= 6+с(шойп), а = Ъ (шой п) -з- а.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
