Избранное
ЭБ Нефть
и Газ
Главная
Оглавление
Поиск +
Еще книги ...
Энциклопедия
Помощь
Для просмотра
необходимо:


Книга: Главная » Гильберт Д.N. Математическая логика и основания математики
 
djvu / html
 

500 ПОНЯТИЕ «ТОТ, КОТОРЫЙ» И ЕГО УСТРАНИМОСТЬ [ГЛ, VIII
Мы можем здесь считать, что входящие в а (а, . . ., k) и в Ь (а, . . ., k, n, т) рекурсивные функции уже заменены соответствующими термами, так что правые части обоих равенств, если не считать функции ф и сокращенных обозначений (т. е. явно определенных символов), не содержат никаких символов, кроме функциональных знаков а', а + Ь, а-Ь, символа цхА (х) и логических символов [которые могут, например, встречаться внутри какого-либо выражения ц,хУ[(х)].
Задача теперь заключается в том, чтобы найти такой терм f(a, . . ., k, n), что для него выводимы формулы
f(a, . . ., k, 0) = а (а, . . ., k) и
|(а, . . ., k, п) = Ъ(а, . . ., k, n, |(а, . . ., k, n)).
Здесь в записи термов параметры а, . . .,k, можно всюду опустить, так что эти равенства могут быть записаны просто в виде *)
Сначала мы изложим основные идеи ре'шения этой задачи. Мы будем следовать Дедекинду, который в своем сочинении «Was sind und was sollen die Zahlen?» впервые показал разрешимость рекурсивных равенств, рассматриваемых как определяющие равенства для вводимой в рассмотрение функции, не пользуясь наглядными соображениями. Его доказательство заключается в том, что сначала он показывает, что для каждого числа п имеется функция /п (а), обладающая тем свойством, что
/п (0) = а и что для всякого числа х < п
/„(*') = Ь (я, /„(*))•
Доказательство это производится индукцией по п. Далее он устанавливает, что указанными условиями значение /„ (х) однозначным образом определяется для всех х ^ п, так что если х -^ п и х ^. т, то
/„ (х) = fm(x).
1) Требование явно указывать параметры в схеме рекурсии проистекает — по крайней мере в случае простейшей схемы рекурсии — исключительно от того, что для функциональных знаков мы условились явно выписывать все их аргументы. То, что в левых частях рекурсивных равенств стоит вновь вводимый функциональный знак с соответствующими аргументами, а не произвольные термы с теми же самыми переменными, является существенной особенностью'вида нашей схемы рекурсии.

 

1 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200 210 220 230 240 250 260 270 280 290 300 310 320 330 340 350 360 370 380 390 400 410 420 430 440 450 460 470 480 490 500 501 502 503 504 505 506 507 508 509 510 520 530 540 550


Математика