Главная » Просмотр файлов » Гильберт, Бернайс - Основания математики. Теория доказательств

Гильберт, Бернайс - Основания математики. Теория доказательств (947376), страница 89

Файл №947376 Гильберт, Бернайс - Основания математики. Теория доказательств (Гильберт Д. - Основания математики и прочие работы) 89 страницаГильберт, Бернайс - Основания математики. Теория доказательств (947376) страница 892013-09-15СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 89)

Затем, используя символ М (и, й), мы с помощью эквивалентности У1)(п) (г(грай М(п, г)) строим изображение 8)1! (л) высказывания «число л является номером некоторой истинной предваренной формулы без свободных переменных». Затем с помощью эквивалентности 8)[ (а) У12 (рг (и)) мы получаем изображение У1 (а) высказывания «число л является номером некоторой истинной формулы без свободных переменных» и, наконец, получаем общее определение истинности с помощью формулы Я (л) й )Ух (51 (а, х) й 8, (х) -+ У1 (х)), которую мы будем обозначать посредством У(о (и). Рекурсивное определение формулы У1«(а) получается из сле- дующей эквивалентности: У1«(п)-а=70, 11»са, «).13«!.

»)й~о(ч(а, 4)) йф,(ч(п, 5)) й(ч! (ч(п, 4)) =ч1 (ч(п, 5))) ~/ Зх(х~лйп=З хй(О)(х) й 1У1«(х)) ')/ 1м),(а) Й.ИХЭу[х(п*у(пй ((х = 20 7" 1!" Й У1о (х) Й У1« (у)) ~/ (х= 40 7» 11" й(У)о(х) ~/ У)о(у))) ~/ (х = 80 7". 11" й (У1« (х) -)-У1о (у))) ')/(х=160 7" 11" Й(У[о(х) У1«(у))))[1.

Определение предиката М(п, й) мы сначала поясним нефор- мально. Истинная предваренная формула без кванторной при- ставки представляет собой истинную формулу без переменных. Истинная предваренная формула с Г-кванторной приставкой является либо формулой вида )Ууй[(~) и тогда для любой цифры [ формула 'А (!) является истинной предваренной формулой с 1-кван- торной приставной, либо формулой вида Зхб(х) и тогда по край- ней мере для одной цифры 1 формула 4[(!) Является истинной предваренной формулой с 1-кванторной приставкой. Это определение в арифметической формализации изображается следующим образом: М(п, О) — У)1«(п), М(а, й') (а=50 (ох~с„") '"лй) (п))ЗЙ (ж) Ухм(з[(ч(п, л(п)), 1»А(а)„2 3"), й)~ Ц [а=100 Ксс,") """й 2(п))ЗЙ ЗХМ(З1(ч(л, ). (а)), (РА[„), 2 За), й)1 С помощью формулы М (и, й) мы, как было замечено ранее, можем получить следующие явные определения для формул 8)1 (п) и У[а (а): У) (л):-)г (г ~ рг (л) Й М (рг (а), г)), У[а (и) С (и) й 'рх (31 (и, х) й «Оо (х) — ю- У1 (х)).

Итак, мы получили искомое определение истинности для формализма (Х). Рассматривая его с учетом планируемого применения теоремы Тарского, мы должны напомнить, что в формализме (ЕР) все рекурсивные функции допускают явные определения, причем таким образом, что на основе этих определений рекурсивные равенства являются вьводимыми формулами. Значит, в частности, в (ХР) рекурсивное определение функции рг (а) может быть заме- 4 2! ФОРМАЛИЗАЦИЯ АРИФМЕТИЧЕСКОГО ФОРМАЛИЗМА 47З 4!2 ВЫХОП ЗА РАМКИ ТЕОРИИ ДОКАЗАТЕЛЬСТВ [ГЛ.

У нено явным. Равным образом, и рекурсивное определение предиката И, (и) тоже может быть заменено прямым построением соответствующей формулы из (ЕР) и даже из (3.). Отметим далее, что для любой конкретной цифры 1 из формул (Ж) выводима эквивалентность М(п, 1) Й(п), где Й(п) — некоторая (зависящая от 1) формула из (20). Поэтому при любой заданной цифре и формула И(п), ввиду эквивалентности Чз(георг(п)З7М(рг(п), г)) М(рг(п), 0) !7 М(рг(п), 0') )( ... ~/ М(рг(п), 1), где ! — значение терма рг(п), переводима в некоторую формулу из (470). Затем, если и является номером некоторой формулы Я из (Е) без свободных переменных, то рассматриваемая формула переводима в формулу Я. Действительно, для любой такой цифры и значение 1 герма рг(п) является, как мы знаем, номером некоторой переводимой в формулу 'Л предваренной формулы Л„ а формула М(рг(п), О) ~/...

~( М(рг(п), !), в которую переводима формула И(п), со своей стороны, может быть переведена в такую предваренную формулу %, у которой кванторная приставка совпадает с приставкой формулы Я„а стоящее после кванторной приставки выражение имеет внд Из(й (ге %7)); здесь 31, ..., ес — Различные входЯщие в фоРМУЛУ Я, связанные переменные, и если Я, (х„..., хс) — выражение, стоящее в Я, после кванторной приставки, то й(а„..., а,) представляет собой арифметическое функциональное выражение, которое сопоставляется формуле Л, (а„..., а,) относительно переменных а„..., а,. А теперь, опираясь на определение формулы И,(п) и исполь.

зуя выводимую формулу 91(2 3') = а, можно вывести эквивалентность Ие(й(аы " а,)) Яе(аы " а„),' а из этой эквивалентности средствами исчисления предикатов можно вывести формулу й) Я„ которая вместе с выводимыми формулами И(п) И и 1Л Яз дает нам искомую эквивалентность И(п)-Я. Замечание. Если формула 1Л не содержит кванторов и, значит, является формулой без переменных, то непосредственно получаются эквивалентности И (и) И, (и) и Из (и) Я.

Описанную здесь лишь вкратце выводимость формулы И(п) Я мы поясним на примере, когда Я представляет собой формулу Чх(х~О-~-Чу(х у=у')), которая очевидным образом является ложной. Если и — номер этой формулы, то имеет место равенство зр (и) = и, а рг (и) является номером формулы 97хпу( ) (х=О)'Т,с'х у=у'). Этот номер представляет собой число 50 7100'и' ' 40 79,70.ИЕ13з И70.113 11'17~~.!33 И Мы обозначим его буквой !. Формула И(п) переводима в дизьюнкцию М (3, О) )7 " ~~ М (1, 1), которая с помощью выводимых формул М(1, О) Из(1), )И,(1), 1,(!)=7, Л(1)=3, 1=30 Р,"„;" "0 л(0) переводима в 'формулу (1) 1!схМ(31(ъ (7, Л(1)), 7, 2 3'), 0) !/ ...

... ~( 107хМ(31 (т(й Л(1)), 7, 2 3"), ! — 1). Легко видеть, что Л ( )) 100 11еь79.70.11'13',1170 110' ' 13 ' а из определения 31(т, й, 1) получается, что 2.3 31(9(1 Л(!) 7 2,3е) 100.1140.79'0 ' '. з*,п70 И " "оз Выражение, стоящее в правой части этого равенства, мы обозна. чнм посредством с (а). Э 3! ФОРМАЛИЗАЦИЯ АРИФМЕТИЧЕСКОГО ФОРМАЛИЗМА 4!Э сгл.

ч ВыхОд ЗА РАмки теоеии докАЗАтельстВ Из рекурсивных определений функций') 13„, 7.(п) и ч(п, й) могут быть выведены формулы ч (с (а), гс (с (а))) 131(с(а))=11, Л(с(а))=4, с(а)=100.133(с(а)) Из этих формул мы сначала получим формулу ) Ио (с (а)), а затем формулу М(с(а), й') ЭуМ(31(ч(с(а), )с(с(а))), 11, 2 3"), й). Поэтому дизъюнкцию (1), которая переводима в формулу ЧхМ(с(х), 0) ~/ ... 'ч' 'чхМ(с(х), ! — 1), можно перевести в формулу (2) УхЗуМ(з!(ч(с(х), 7 (с(х))), 11, 2 3"), 0) 3/ ... ... з~ Чхзум(31(ч(с(х), Х(с(х))), 11, 2 3"), 1 — 2) По определению функции 3!(и, й, !) мы получаем равенство 31(ч(с(а), )с(с(а))), 11, 2 3') = 40 73 70.113 3 !Зс 1113 113 11 ' ° 1Т ' .!Зг 3 Выражение, стоящее в правой части этого равенства, мы обозначим посредством 9(а, Ь).

С помощью выводимой формулы 3(а, Ь) чь ~50 п мы получим 1М(й(а, Ь), 73'), а отсюда средствами исчисления предикатов получим формулу )згх)уМ(3(х, у), й'). Поэтому формула (2) переводима в формулу 'охЛуссс!о (3 'х, у)). А теперь, чтобы убедиться в переводимости этой формулы в формулу чсх)у( )(Х=О) ~/ х у=у'), достаточно установить выводимость эквивалентности (3) И, (9 (а, Ь)) ! ! (а = 0) 37' а Ь = Ь'.

Эта эквивалентность легко может быть получена следующим образом. Пользуясь определением формулы И,(п), мы сначала с помощью выводимых формул 3(а Ь) — 40.7 (оежы,з) 11 (ос,ы,с) и Яг(Ч(а, Ь)) получим эквивалентность (4) Ио(й(а, Ь)) Ио(ч(9(а, Ь), 3)) Ч' И,(ч(3(а, Ь), 4)). 1) См. с, 272.

Затем, опираясь на выводимые равенства ч(3(а, Ь), 3) =9.70 !1'3' 13', ч(9(а, Ь), 4)=70 1Р'Иг'3 'Тг3 13333 и снова пользуясь определением И,(и), получим формулы 3)!3(ч(й(а, Ь), 3)) )(~о(2 3')йЖ(2)йч!(2 3') =ч1 (2)) Ио(ч(3(а, Ь), 4)) "®о(5,113'3'.173'3 ) йсъо(2 3"') й ч! (5 11.'3' 17'3 ) = ч1 (2 33').

Но формулы, стоящие в правых частях этих эквивалентностей, с помощью определений формулы ч.о и функций ч! Могут быть переведены в формулы ) )(а — 0) и а Ь-Ь', так что из эквивалентности (4) мы получаем формулу 3)!3(9(а, Ь)) ) )(а=О) ~/а Ь Ь', т. е. искомую эквивалентность (3). Показанная на этом примере выводимость формулы И(п) И средствами формализма (Х ), к которому добавлены формулы (А1), имеет место всякий раз, когда 6 является формулой без свобод- ных ' переменных, а и — ее номером. На основание предыдущего рассуждения это позволяет нам сделать вывод о том, что невоз- можно указать такую формулу 6 (и, й), принадлежащую форма- лизму (Е„), — если, конечно, этот формализм иепротиворечив,— чтобы прй замене символа М(п, й) этой формулой эквивалентно- сти (Ж) становились выводимы формулами.

Действительно, в про- тивном случае формула Зг(г( рг(и) й6 (рг(и), г)) была бы формулой Ио (п) из формализма (Е„), удовлетворяющей условию, что для любой формулы 6 без свободных переменных и для ее номера и в (Ха) выводима эквивалентность Ио(п) 111; но, как мы уже убедились в свое время, возможность построения такого рода формулы не совместима с непротиворечивостью (7Ф) ').

Характеристики

Тип файла
DJVU-файл
Размер
7,04 Mb
Тип материала
Предмет
Учебное заведение
Неизвестно

Список файлов книги

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6418
Авторов
на СтудИзбе
307
Средний доход
с одного платного файла
Обучение Подробнее