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

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

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

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

Мы покажем здесь несколько больше, а именно, что может быть указана некоторая рекурсивная формула 6 (1, т, и), не содержащая переменных, отличных от 1, т и п, и обладающая тем свойствам, что для любых цифр 1, п« и и отношение 6(1, п», и) имеет место тогда и только тогда, когда в нашей нумерации ! и а являются номерами списков формул, и является номером некоторого равенства 6 и список с номером а представляет собой вывод равенства Ж из равенств списка с номером ! при помощи правила подстановки и схем замены и перестановки.

Построение такой рекурсивной формулы 6(1, и», п) мы начнем с рекурсивного изображения предиката «число и является номером некоторого термам Такое изображение на основе нашей нумерации может быть дано следующей„ равносильной изображаемому высказыванию альтернативой: «и= 8 или и является простым числом « 11 или и= 3 т, где п« отлично от 0 и является номером некоторого терма, или п имеет вид 5 р", .... р ', где р„ ..., р„— различные пррстые числа ) 7, а и„ ..., и, — номера каких-либо тер мовы Исходя из этой альтернативы и применяя способ, аналогичный тому, который мы применяли в гл.

1Ч') в связи со сходной задачей для рассматривавшегося там формализма, мы действительно получим рекурсивное определение некоторой функции 1(п), с помощью которой высказывание «число п является номером некоторого терма» изобразится равенством 1(п)=0. Вслед за этим мы немедленно получим рекурсивное изображение предиката «число п является номером некоторого равенства между термами», так как этот предикат, как мы знаем„может быть сформулирован в виде высказывания «и является числом вида 10 7«11»„где а и Ь суть номера некоторых термов». Далее, отсюда мы получим изображение предиката «число и является номером некоторого списка формул» в виде некоторой ») См.

«. 278-279, 496 ппиложение и! рекурсивной формулы Е)(и). В самом деле этот п е ик ~~О~~Ф~~" ной о м л предикат Рав дога числа х„удовлетворяющего ело ческому высказыванию: « для кажго условию х()((и), число у(и, х) ' номером некоторо О равенства между термами». еперь мы можем рекурсивно изо «числа ги р ур изобразить и высказывание р р нств, второе из которых из первого в результате применения схемы перестасамом деле, это высказывание а р внозначно следуют числа х и у, меньшие т и такие, что т = а и = 10 7» 11а», а это после нее п в некоторую рекурсивну ф О ю формулу ,(и, и). Для того чтобы дать реку сини о р ую формулировку правила з1(т, й, 1), рекурсивное опр схемы замены, мы введем реку сини р аную функцию следующей альтернативы'): е определение кото ой изв р " лекается из «Если ги = 3« .

й — и й является простым числом )7, то з1 (и[, й, 1) = 3" 1; если т=2' 3» 5» и, с'=»О и и се235 Ф з1 (т, )г, 1) =2' 3» . 5«. Ц 1»»1(»(е, к[, а, (Р к<ге если ни один из названных случаев места не имев, имеет, то з[(т, Й, 1) =т.» С помощью этой функции для любого числа щ являю номером какой-либо формулы, можно б ет формулы в результате подстановки поручается фощего рекурсивного предиката, зависящего от пе ем «для некоторого про р стого числа х такого, что 11.с некоторого числа у( и имеет место отношение з1(ги х у = , являющегося номе ом н двх ф" мл Лля любых чисел 1 и ш, яв вляющихся номерами некоторых вух формул, условие, что из этих формул по правил зам получается формула с номером мощью следую[цего рекурсивного п е и, может ыть вы ажено с менных 1, ги и и': «с предиката, зависящего от переги и и ): «существует число х(т, обладающее тем ОБШЕРЕКУРСИВИЫЕ ФУНКЦИИ 497 своиством что з1(х, 7, у(1, 3))=ги и з1(х, 7, у(1, 4))=и».

Оба упомянутых предиката тоже могут быть изображены рекурсивными формулами, которые мы обозначим посредством Оз(т, и) и «зз(1, а(, и) соответственно. После того как мы таким образом получили рекурсивные изображения для всех содержащихся в понятии вывода терминов и отношений, искомую рекурсивную формулу 6(1, и[, и) мы построим путем рекурсивного перевода следующего арифметического высказывания: «имеет место к((1) и у(иг, ).((и)) =и и для лю'ого числа х( Х (иг) выполняется альтернатива: либо существует число у().(1), для которого Р(иг, х)4 У(1„у), либо существует число у ( х, для которого имеет место к(1 (у (т, у), у (а[, х)) или Оя (У (иг, у), У (иг, х)), либо существует число у ( х и число г (х, для которых имеет место Ов(у(иг, у), у(иг, г), у(иг, х))».

Этим закончено доказательство утверждения о том, что любая квазирекурсивная функция одного аргумента вычислима в некотором формализме, для выражений которого можно построить нумерацию, удовлетворяющую трем условиям рекурсивности, или, короче, что любая каазиргкурсивная функция одного аргумента является регулярно аычислимой.

Этот результат вместе с ранее установленной квазирекурсивностью всякой регулярно вычислимой функции одного аргумента позволяет сделать вывод, что класс регулярно вычиглимых арифметических функций одного аргумента совпадает с классом квазирекурсивных функций одного аргумента. Проведенное нами рассуждение дает еще один результат, В самом деле, пусть [(и) — какая-либо квазирекурсивная функция одного аргумента, и пусть 1 — номер какого-либо представляющего собой нормированное квазирекурсивное определение функции [ списка формул только что рассмотренного нами формализма, или — что короче — номер некоторого квазирекурсивного определения г.

Пусть и — цифра, 1 — значение [ (и), а ч — функциональный знак, который в этом квазирекурсивном определении представляет функцию (. Тогда номер формулы Ч(п) 1 будет равен числу 1[), 7».гз з" 11» з[ щем ек 1) Переход от одной сове ш н р е но аналогичной альтернативы к соогвег ему рекурсивному определению проделан в гг. [Ч на с, г60— го обсгоягел ') В втой арифметической фо м ян ьсгво, яго число 7, явля ееся н фор у нровке данного условия проявляет ся ющееся номером яменяой переменной а также меньше номера нмвола О допускаемой в качестве те ма нн нв р, Далее, можно указать цифру щ, являющуюся номером некоторого списка формул, представляющего собой вывод формулы ([(и) 1 из формул списка с номером 1. Вывод этот, как мы знаем, производится с помощью правил подстановки и схем замены и пере- ПРИЛОЖЕНИЕ ОБШЕРЕКУРСИВНЫЕ ФУНКЦИИ п! становкн.

Прн этом выполняется условие 6(! ~и, !0.7'"'~" 1Ро!). Если числа г равно 2' Зо', то 1Ф у(г, 0), а=у(г, 1), и, значит, имеет место отношение 6 (1, у(г, 1), 10 7о го'зо ! !о з (о о)) При этом 5(1, у(г 1) !0.7огохо !!о оооо о!) является рекурсивной формулой, не содержащей отличных от1, и и г переменных, и, следовательно, имеет внд некоторого равенства 1!(1, и, г) =О, где й(1, и, г) — рекурсивный терм, не содержащий переменных, отличных от 1, п и г. Если 1 является номером норми ов квази ек сн р ур вного определения какой-либо функцнйодного аргумента, то для некоторой, подходящим образом выбранной цнф ы г найденное нами соотношение ной цн ры г ()(1, и, г)=0 имеет место прн произвольном выборе цифры и. Тогда для любой цифры г, для которой выполняется отношение 1)(1, и, г) =О, значенне у(г, 0) будет равно значению((и) определяемой этим квази- рекурсивным определением функции !.

Для фигурирующей здесь рекурсивной функции У(т, 0) мы будем употреблять функциональный знак уо(гп). Если мы теперь объединим полученный нами результат с тем, чтб было установлено относнтельно выводов в формализме (Хо), то получится, что для цифры 1, являющейся номером какого-либо нормированного квазнрекурснвного определения, и для произвольной цифры и в формализме (Р) выводимо равенство р 1) (1, и, х) = г, где о — наименьшая нз цифр г таких, что значение ()(1, и, г) равно 0; нз этого равенства, далее, в (Ло) выводимо равенство уо(ро()((, и, х)) =1, где 1 — цифра, являющаяся значением квазирекурсивной функции, определяемой системой равенств с номером 1, при значении арг- мента, равном и.

С другой стороны, вследствие нумернческой и а гу- непротиворечивости формализма (Ео) нн для какой нф д, какой цифры д, отличной от 1, равенство уо(Ро() (1, И, Х)) = о невыводнмо в (Хо). Тем самым для любой квазнрекурсивной, а значит, и для любой регулярно вычнслнмой функции одного аргумента в (Ео) получается некоторое нормальное представление в виде уо(р-()(1, и, х)). Прн этом произвольная отдельно взятая регулярно вычнслнмая функция характеризуется цифрой 1, а сама функция 1)(1, п, а) определяется независимо от функций, которые ей надлежнт изображать.

Впрочем, терм уо(р„()(1, а, х)) изображает квазнрекурснвную (а тем самым и регулярно вычнслнмую) функцию не только прн цифре 1, являющейся номером какого-либо нормированного квази- рекурсивного определения. Это имеет место всякий раз, когда для любой цифры и может быть указана такая цифра г, что имеет место равенство ()(1, и, г) =О. В самом деле, в конце 5 1 мы показали, что любой терм нз (Ео), нмеющнн внд а (р„о (и, х)), где а (и) и 9(п, щ) суть рекурснвные термы, содержащие только указанные переменные, причем для каждой цифры и может быть указана цифра г, для которой имеет место равенство о(и, г) =О, всегда изображает регулярно вычнслнмую функцию; это верно, в частности, и для терма уо(р„() (1, п, х)), если цифра 1 удовлетворяет указанному условию.

В формализме (Х') в роли терма уо (р„() (1, п, х)) выступает терм уо(р„(() (1, и, х)=0)), т. е. терм вида уо(роЯ(1. и, х)) с рекурсивной формулой И (1, и, гп). Этим термом каждая регулярно вычнслнмая арифметическая функция одного аргумента также представляется в анде»,(р„Я(1, и, х)) в том смысле, что имеет место выводимость равенств о„(р„.й! (1, и„х)) =1, когда цифра 1 является номером какого-либо цормнрованного квазнрекурснвного определения этой функции; с другой стороны, терм Уо(р И(1, п, х)) представляет регулярно вычнслнмую функцию всякий раз уже тогда, когда для любой цифры и можно указать такую цифру г, для которой имеет место отношение Я(1, и, г).

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

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

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

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