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


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

420 РЕКУРСИВНЫЕ ОПРЕДЕЛЕНИЯ [ГЛ, VII
а также схему еще более общего вида:
Я(Ь, 0)
1(6, а) Здесь t, ti, . . ., t обозначают какие-либо термы, которые
могут также содержать и переменные а, Ь; единственным условием применимости этой схемы является отсутствие переменных а и & в формуле Я (с, г).
Заметим, что если допустить использование связанных переменных, то эта обобщенная схема индукции сведется к обычной. Действительно, средствами исчисления предикатов из формул
Я (Ь, 0),
можно получить формулы
V.r2T (z, 0), Vxty (x, a) -*- V#2[ (x, a'),
из которых с помощью обычной схемы индукции мы получим формулу
Vxty (х, а), а из нее — формулу
Я (Ь, а).
Но сведение к обычной схеме индукции может быть осуществлено, как это впервые показал Сколем 1), и без привлечения связанных переменных.
Сперва рассмотрим схему
Я (Ь, 0)
Ж*(а, Ь), а)-»- Ж&, а') Я (Ь, а)
'(в которой возможность наличия в t переменных а и b указана теперь явным образом). Пусть функция if (a, b, k) вводится еле-
l) S k о 1 е m Th. Eine Bemerkung iiber die Induktionaschemata in der rekursiven Zahlentheorie.— Monatsh. Math., Phys., 1939, 48, S. 268—276. Первоначально здесь использовалась еще одна схема рекурсии, которая непосредственно вида примитивной рекурсии не имеет; однако, как это было указано Р. Петер в реферате работы Сколема (J. Symbolic Logic, 1940, 5, № 1, p. 34—35), она может быть сведена к примитивной рекурсии.

 

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 421 422 423 424 425 426 427 428 429 430 440 450 460 470 480 490 500 510 520 530 540 550


Математика