Гильберт, Бернайс - Основания математики. Логические исчисления и формализация арифметики (947375), страница 72
Текст из файла (страница 72)
Формулы Я, (а) и Д, (а) имеют вид а < ю й а < ю', а = «[ ')/ а = «['. В процедуре редукции должна быть модифицирована операция 3. Рассматриваемая формула а <Ь~%Ь <с-+-а <с при замене переменных а, Ь и с цифрами «[, «[' и «[ оказывается ложной. 3. Независимость формулы 7(а <0).
Цифрами второго рода являются фигуры ( — 0(Р))(1). Равенства ( — О( ))(1)=0([) и 0([)=( — 0(Р))(1) считаются истинными или ложными в зависимости от того, совпадает число Ь с числом 1+ р или жв нет. Из неравенств ( О(Р))([)<ОР) и ОП) -( О(Р))(1) первое истинно, а второе ложно, если число $ меньше, чем 1 + р, и второе истинно, а первое ложно, если число 1 больше, чем 1+ р; оба неравенства ложны, если число 1 совпадает с 1+ р. Равенство ( — О(Р))1 = ( — О(«))([) истинно, если число Ь + [[ совпадает с 1+ р, и ложно в противном случае. Неравенство О(Р))(1)<( О(«))([) истинно, воли число 1 + [[ меньше, чем 1 + р, и ложно в противном случае.
В определении операции редукции рааличие между цифрами первого и второго рода нв проявляется. Рассматриваемая формула [(а<0) при замене а цифрой — 0' превращается в ложную. 4. Независимость формулы а~Ь вЂ” ~-а -Ь )('Ь<а. Цифрами второго рода являются фигуры и(1), причем и, обозна- Р' чает символ и, а и для р, отличного от О, обозначает фигуру, получающуюся иэ и навешиванием нижнего индекса в виде р звездочек.
Равенство и() =и( Р « истинно, если число $ + [[ совпадает с ( + р, и ложно в против- ном случае. Неравенство и() <и Р [[ истинно, если число 1 + [[ меньше, чем 1 + р, и ложно в противном случае. Если а — цифра первого рода, а Ь вЂ” цифра второго рода, то равенства а = Ь и Ь = а, а также неравенства а Ь и Ь < 0 всегда ложны; если же а отлично от О, то Ь <а истинно. Формулы 8, (а) и Д, (а) имеют вид 0 <а', а'<О.
В процедуре редукции должны быть модифицированы операции 2 и 4. Рассматриваемая формула а чь Ь -Р а < Ь [/ Ь < а при замене переменных а и Ь цифрами 0 и и оказывается ложной. Тем самым для системы (А), так же как и для системы (В), нами установлена независимость кан[дой из ее аксиом от всех остальных. 4 Л иэовРАженпе ПРинципА нАименьшего числА 349 348 [Гл ЧЪ ИА галА АгиФметпки й 7. Изображение прп. ципа наименьшею числа при помощи выражающей его формулы; равносильность этой формулы аксиоме индукции на основе прочих аксиом системы (В) Для характеристики системы аксиом (В) мы приведем еще один вывод, а именно вывод из атой системы следующей формулы: А (а) -~- лх (А(х) сс )/у (А (у) -+ х = у ~/ х < у)), которав выражает принцип наименьшего числа, т.
е. предложение, говорящее о том, что для любого высказывания, выполняющегося для какого-нибудь числа, всегда имеется наименьшее число, для которого это высказывание имеет место. Кроме исчисления предикатов, мы используем для етого вывода аксиомы (Х,), а<а', выводимые формулы 1 (а < О), а < Ъ' -э а < Ь ~/ а = Ь, 1(Ь<а)-+а =Ь~/а<Ь и схему индукции, которая, как мы внаем, равносильна аксиоме индукции. Схему индукции мы будем применять к формуле Эх (А(х) бс х < а) — Вх (А(х) бс Чу (А(у) -ь х = у ~/ х < у)). Посылку и заключение этой формулы мы для краткости обозначим символами В (а) и (э соответственно.
Тогда рассматриваелюе применение схемы индукции будет иметь вид 3(0)-ьчэ (В (а) - 6) — (В (а') -+ 6) В (а) -г- чэ Нам нужно вывести формулы В (О) -г-чэ и (В (а) -ь Ж) -э (В (а') -+. 6). Первая из них получается иэ формулы ~3 (О), т. е. из формулы 1Лх (А (х) бс х - О), которая может быть получена из ~ (а<0). Для того чтобы получить вторую формулу, мы сначала с помощью а < Ь' -~. а < Ь ~/ а = Ь выведем формулу 3х (А(х) бс х < а') -+ Лх (А(х) бс х < а) ~/ Вх (А(х) й х = а), которая сокращенно может быть записана в виде 3(а')-~.3(а) ~/ Вх(А(х) бс х=а). Далее, из аксиомы (г,) мы получим Вх (А(х) ос х = а) -+ А(а), а отсюда, в сочетании с предыдущей формулой,— В (а') -ь В (а) ~/ А (а).
Теперь, формула В (а) ~/ А (а) по правилам исчисления выскаэывавий переводима в 3(а) Ч (А(а) бс $ 3(а))) далее, формула ~3 (а), т, е. 1 Лх (А (х) бс х < а), переводима в )/у (А (у) — 1(у <е)), и потому, используя формулу 1(Ь <а)-+а =Ь ~/ а <Ь, мы получим ~ 3(а) -+. 'Уу (А (У) -+ о = У Ч е < У).
Но на основной формулы (Ь) подстановкой получается формула А(а) бс 'Уу (А(у) -э. а = у ~/ а < у) — ьэ. В реаультате мы приходим к формуле 3(а')-~-3(а) ~/ э, а из нее средствами исчисления высказываний получается формула (В (а) г- 6) -~. (В (а') -ь 6). После этого можно применить схему индукции и получить формулу В (а) г. б. От атой формулы мы легко можем перейти к искомой. Действительно, искомая формула имеет вид А (а)-~6, 350 НАНАлА АРНФмвтини ГЛАВА У11 [ГЛ, 71 т.
е. а иэ полученной нами формулы, если вместо а подставить а', полу- чается формула В (а') «[э. Таким образом, будет достаточно вывести формулу А (а) -« )В (а'), А (а) -«лх (А(х) А х <" а'). Но эта формула может быть получена с испольаованием фор- мулы а (а и основной формулы (Ь). Тем самым мы завершили вывод формулы А (а) -«йх (А(х) А1 Чу (А(у) — «х = у [/ х ( у)). Заметим, что верно также н обратное, т.
е. иэ атой формулы в сочетании с формулами (3,), а'Фа, 1(а' (а) и аФΠ— «Зх(х' =а) может быть выведена аксиома индукции. Для этого надо в фор- мулу, выражающую принцип наименьшего числа, вместо именной формы А (с) подставить [А (с), а затем к импликации, стоящей в области действия квантора всеобщности ву, применить правило контрапознцни.
Тогда с использованием перечисленных формул и формулы А(0)-«(Зх( ) А(х) б1В(х)) — «лх( [ А(х) б1 В(х) Ах~О)), которая выводится с помощью второй аксиомы равенства, мы полу- чим формулу ) А (а) А А(0) — «Лх( [ А(х') ЙА (х)), из которой с помощью простых преобразований и получается аксиома индукции. РЕКУРСИВНЫЕ ОПРЕДЕЛЕНИЯ 3 1. Некоторые пояснения принципиального характера 1.
Простейшая схема рекурсии; формалиаация интуитивной процедуры вычисления; сопоставление явных определений с рекурсивными. В системе (Б) ') нашли свою формализацию все пять аксиом арифметики Пеано '). Именно, две из них были формализованы введением символа 0 и символа штриха, две другие — выводимостью формул (Р,) и (Рэ) ') и, наконец, аксиома полной индукции — введеннем формальной аксиомы индукции. Поэтому можно было бы думать, что в теоремах, доказанных нами относительно системы (В), вопросы непротнво речивости и полноты арифметики нашли свое окончательное решение.
Однако, если мы вглядимся более пристально, то заметим, что нашего формализма никоим образом не хватает для изображения всех применяемых в арифметике понятий. И у Пеано ) видимость того, что сформулированных им пяти аксиом достаточно для развития арифметики, тоже существует исключительно потому, что, руководствуясь распространенным способом выражаться, он рекурсивные равенства, с помощью которых вводятся элементарные функции, — например, равенства для суммы а + Ь и произведения а Ь а+О=а, а + и = (а + и)', а 0=0, а и' = (а и) + а, называет определениями.
Этот широко распространенный способ выражаться соответствует точке зрения интуитивной, финитной ариусэетипи. Напомним, что при рассмотрении фннитной арифметики ') рекурсивные определения играют роль сокращенного сообщения ') См. с, 335. 1) См. с. 272, 325. е) См. с.
273. 1) Р е а и о 6. Еогпэи1аио Ма[Ьета[[со.— у Ед.— Тес[по, 1008, 1[, 1 и далее. 1) См. с. 51. 1 11 некотОРые пояснения принципиАльного хАРАктеРА 353 РЕКУРСИВНЫЕ ОПРЕДЕЛЕНИЯ ,(ГЛ. Чгг процедуры, посредством которой одной или нескольким заданным цифрам сопоставляется вполне определенная новая цифра. Эту процедуру мы сможем промоделировать и в нашем формализме, если допустим введение функциональных знаков в сочетании с рекурсивными равенствами.
При этом, подобно тому, как зто делалось в финитной арифметике, происходит расстановка рекурсий в определвыную иоследоеаигельность, в соответствии с которой для каждой рекурсии укааывается перечень тех рекурсий, которые вй предшествуют. В выборе этой последовательности может иметь место значительный произвол, однако мы заметно ограничим его, если будем обращать внимание ыа то, чтобы не проиаводилось ненужных рекурсий. Введение функционального знака при помощи рекурсии мы будем кратко называть рекурсивным введением этого знака.
Данный терм мы будем называть н е а а в и с и м ы м от рекурсивно введвыыого функциональыого знака (, если оы содержит только такив функциональные знаки, которые были введены еще до проведения рекурсии для (. Поначалу мы будем рассматривать только рекурсивные равенства одного очень простого типа, или, как мы вщв будем говорить, простейшую схему рекурсии, и понятие рекурсии мы пока этим н ограничим. В том случае, когда вводимый функциональный знак зависит только от одного аргумента, рассматриваемая схема рекурсии выглядит следующим образом: ((0)=а, ((и') = 5(и, ((и)). Здесь для ) следует ваять какой-нибудь вще нв использовавшийся в нашем формализме функциональный знак с одним аргументом.
В качестве таких знаков мы будем брать — эа исключением отдельных случаев, когда будем пользоваться общеупотребительными математическими символами,— строчные буквы греческого алфавита. Далее, а в втой схеме должно представлять собой терм без переменных, независимый от функционального знака ( (.), а Ь (и, ( (и)) должно получаться в результате подстановки ( (и) вместо т иэ герма Ь (и, т), также независимого от ( и ые содержащего переменных, отличных от и и т. (Мы не требуем, чтобы переменные и и т действительно присутствовали в Ь (и, т).) В случае введения функционального анака ) (а, и) с двумя аргументами аналогичная схема рекурсии имеет вид ((а, О) =а(а), 7 (а, и') =Ь(а, и, 1(а, и)).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
