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


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

400 РЕКУРСИВНЫЕ ОПРЕДЕЛЕНИЯ {ГЛ. VIF
такое число п, для которого имеют место сравнения п = г-Ь(а, 6) (mod а), п = s-b(a, b) (mod 6),
где г и s фигурируют в качестве произвольных параметров.
Если теперь дополнительно наложить условие Ь(а, Ь) — 1, которое выражает взаимную простоту чисел а и Ь, т. е. отсутствие у них общих делителей, отличных от 1, то в этом случае мы получим, что среди чисел, меньших а-Ь, существует число п, удовлетворяющее сравнениям
п = г (mod a), п == s (mod 6)
при произвольных г и s.
Еще проще, чем приведенные нами теоремы о наибольшем общем делителе, получаются теоремы о наименьшем общем кратном. Наименьшее общее кратное чисел а и Ь может быть рекурсивно определено как «наименьшее из тех чисел, не превосходящих а -Ь, которые делятся на а и на Ъ и отличны от 0 при а -Ъ =5"?= 0». Можно привести формальное доказательство того, что всякое число, делящееся на а и на 6, делится также и на наименьшее общее кратное чисел а и Ъ.
Этих примеров достаточно для того, чтобы составить себе представление об этом методе, следуя которому можно осуществить формальное построение арифметики с помощью рекурсий и схемы индукции, но абсолютно без какого бы то ни было использования связанных переменных. Такой способ изложения арифметики называется рекурсивным изложением этой теории, или, для краткости, просто рекурсивной арифметикой.
Эта рекурсивная арифметика находится в тесной связи с интуитивной арифметикой, в том виде как мы рассматривали ее в гл. II, поскольку все ее формулы допускают финитное содержательное истолкование. Возможность такого содержательного истолкования вытекает из ранее установленной нами верифицируемое™ всех выводимых формул рекурсивной арифметики. В самом деле, верифицируемость носит в этом случае характер прямой содержательной интерпретации. Вот почему установление непротиворечивости оказалось здесь таким легким делом.
§ 3. Некоторые обобщения схем рекурсии в индукции
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 401 402 403 404 405 406 407 408 409 410 420 430 440 450 460 470 480 490 500 510 520 530 540 550


Математика