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


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

470 ПРИЛОЖЕНИЕ П
определения могут быть выведены1). Формулировка такого явного определения производится с использованием ji-символа.
Из факта сводимости рекурсивных определений к явным и с учетом теоремы об устранимости i-правила получается следующее утверждение о заменимости рекурсивных определений в формализме (Z):
Всякой рекурсивной функции f(rtb ..., пс) может быть сопо-
ставлена такая построенная из символов формализма (Z) и индивидных переменных формула g(nb ..., nt, п), где п1( ..., п,., п — встречающиеся в ней свободные переменные, что для любого набора цифр fb . . . , f,., f в формализме системы (Z) будет выводима формула g (flr . . . , fc, f) или ее отрицание в зависимости от того, равно или не равно цифре f значение этой функции для набора значений аргументов fi, . . . , fr Далее, при помощи эквивалентности
f(«i ..... nf) = n~$(nlt .... nt, п)
и соответствующих эквивалентностей для всех функций, встречающихся в рекурсивном определении функции f (n1( . . . , /гс) (если эти эквивалентности добавить к нашему формализму в качестве аксиом), могут быть выведены рекурсивные равенства для функции \(nlt ..., nt).
Так, в случае рекурсивных равенств Ф(а, 0) = а(а), Ф(а, /г') = Ь(а, п, ф(а, я))
это выглядит следующим образом. Термам а (с) и b(c, d, т) соответствуют некоторые формулы Si (с, k) и S3 (с, d, m, k) системы (Z), а двуместной функции ф в (Z) соответствует некоторая формула @(а, Ь, К). Это соответствие имеет место в том смысле, что если указанные рекурсивные определения присоединить к системе (Z), то станут доказуемыми формулами следующие эквивалентности:
33 (с, d, т, k)~b (с, d, т) = k,
@(а, Ь, &)~ф(а, b) = k.
В самой системе (Z) будут выводимы формулы @(а, 0, с)~Ш(а, с),
&(а, п, Ь)~(@(а, п', с)~23(а, п, Ь, с)), соответствующие рекурсивным равенствам для функции
См, в связи с этим т. I, с. 499—510.

 

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 471 472 473 474 475 476 477 478 479 480 490 500 510 520 530 540 550 560 570 580 590 600 610 620 630 640 650


Математика