3. Делимость; деление с остатком; наименьший отличный от 1 делитель; последовательность простых чисел; разложение числа на простые множители; нумерация конечных последовательностей чисел; нумерация числовых пар; наибольший общий делитель; наименьшее общее кратное.

Полученные в результате этого формально-изобразительные и дедуктивные возможности позволяют нам без особого труда перевести в наш формализм многие понятия и доказательства элементарной арифметики. Проиллюстрируем эту мысль на нескольких примерах.

Начнем с понятия делимости. Высказывание «а делится на b» или «b делит a» выражает ту мысль, что существует число с, не превосходящее а и такое, что имеет место равенство

По виду этого высказывания мы без труда можем догадаться, что в нашем формализме оно изобразимо посредством равенства

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

Такого рода терм мы будем кратко называть рекурсивным термом, а равенство

или

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

Для понятия делимости представление при помощи рекурсивной формулы мы можем получить очень просто, формализовав деление с остатком введением двух рекурсивных функций и Чтобы написать рекурсивные равенства для этих функций, мы сначала введем следующие явные определения:

и

в которых функции, уже ранее введенные нами посредством рекурсивных равенств

Для функций а и могут быть выведены следующие формулы:

Теперь мы напишем рекурсивные равенства для и

Из этих рекурсивных равенств индукцией по а мы выведем формулы

а из них — формулу

Функция изображает остаток от деления на . В соответствии со сказанным, делимость числа на изображается равенством

Равенство

выражает тот факт, что при делении на к дают один и тот же остаток. Для этого в теории чисел обычно применяется запись

Таким образом, эту запись мы можем ввести посредством явного определения

Понятие делимости ведет нас к понятию простого числа. Высказывание является простым числом» означает отлично от 1 и от 0, и для всякого числа а из ряда чисел от 1 до имеет место альтернатива

Легко видеть, что это высказывание выразимо посредством некоторой рекурсивной формулы

Теперь мы покажем, что всякое число, начиная с 2, делится по крайней мере на одно простое число и что для всякого числа существуют простые числа, большие

С этой целью мы сначала сформулируем определение для наименьшего из тех чисел от которые делят отличны от 1, если

Это понятие тоже может быть изображено посредством некоторой рекурсивной функции Исходя из определения этой функции и пользуясь равенством мы получим формулы

Кроме того, можно вывести импликацию

Две последние формулы выражают тот факт, что при является простым числом и одновременно делит Кроме того, из этих формул мы можем также получить

Далее, введем функцию с помощью рекурсивных равенств

Из этих равенств можно вывести формулы

которые в сочетании с приведенными для формулами дают формулы

Эти формулы выражают тот факт, что есть простое число, большее и не превосходящее

Теперь при помощи некоторого рекурсивного терма мы можем изобразить также и наименьшее из тех чисел от 1 до которые превосходят и одновременно являются простыми числа . С помощью этого терма мы определим последовательность простых чисел посредством рекурсии

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

Для того чтобы получить разложение чисел на простые множители, мы сначала с помощью обычной рекурсии

введем степень На основе этой рекурсии индукцией по с можно вывести следующие законы, которым подчиняется эта операция:

затем индукцией по может быть получена формула

Затем мы определим функцию которая в том случае, когда среди чисел, меньших имеется число а, такое что является делителем это всегда имеет место), дает наибольшее из таких чисел, а в противном случае принимает значение 0. Это определение (в соответствии с нашим предшествующим изложением) также может быть формализовано с

помощью рекурсивных равенств, и из этих равенств и формулы

получаются формулы

которые выражают тот факт, что (для ) наибольшая степень числа делящая равна [Если не делится на то ]

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

а однозначность разложения изображается формулами

При выводе указанных формул существенную роль играет формула

Она соответствует теореме о том, что если произведение а делится на простое число, то по крайней мере один из сомножителей делится на это простое число. Для того чтобы вывести эту формулу, нам надо будет формализовать содержательное доказательство этой теоремы, которое сводится к доказательству того, что если а не делится на простое число то каждое число с такое, что делится на само делится на наименьшее из чисел от 1 до обладающих тем же свойством.

Номер наибольшего простого делителя числа можно рекурсивно определить как наибольшее из чисел к таких, что если такие числа существуют, и число в противном случае. Если эту функцию от «обозначить к то мы получим

Функция устанавливает взаимно однозначное соответствие между числами, большими единицы, и конечными последовательностями чисел с последним членом, отличным от 0.

С содержательной точки зрения это соответствие состоит в следующем: всякому числу однозначно соответствует последовательность значений функции для последнее из которых к отлично от 0, и, обратно, каждая последовательность чисел которой однозначно определяет число

такое, что

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

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

В этом перечислении номер пары изображается следующей явно определенной функцией:

а функции обращающие функцию определяются следующим образом. Сначала дается рекурсивное определение для функции значение которой равняется

наибольшему из тех чисел, квадрат которых не превосходит Это определение может быть дано с помощью равенств

Теперь, используя функцию для можно дать следующие явные определения

На основании этих определений могут быть выведены следующие формулы:

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

В самом деле, рассмотрим произвольную функцию от двух аргументов. Выбрав какой-нибудь функциональный знак с одним аргументом, например положим

Тогда имеем

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

тогда получится

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

параметрами

Тогда мы можем свести ее к рекурсии с двумя параметрами, введя сначала с помощью рекурсивных равенств

некоторую новую функцию и применив затем явное определение

Действительно, если в рекурсивные равенства для функции вместо подставить терм и воспользоваться равенствами

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

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

Для определения используемых при этом функций тоже требуются рекурсии не более чем с одним параметром, а именно рекурсии для функций

[Встречающиеся в определениях функций ] функции и могут быть явно определены через с помощью равенств

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

где функция вводится рекурсивными равенствами

Теперь рассмотрим вкратце теорию наибольшего общего делителя. Понятие наибольшего общего делителя двух чисел (из которых хотя бы одно отлично от 0) прямым путем ведет нас к рекурсивному определению. Однако для того, чтобы добраться до существенных свойств наибольшего общего делителя по возможности более просто, целесообразно исходить из некоторого другого определения. Пусть Среди чисел от 1 до мы рассмотрим те числа с, для которых существуют числа к и I такие, что к а и

При условии, что такое число с имеется всегда; в качестве такого числа можно взять, например, а. Мы построим рекурсивный терм, который изображает наименьшее из таких чисел с, если и число в противном случае. Прибавлением терма мы можем еще добиться того, чтобы при получалось значение а при значение . Обозначим полученный таким образом терм

Основываясь на выводимости формулы

и используя формулы

мы получим формулу

Затем можно получить формулу

и с ее помощью вывести формулу

из которой, ввиду того, что можно получить и равенство

Кроме того, оказывается выводимой формула

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

Определение непосредственно дает нам представимость наибольшего общего делителя в виде

где — некоторые числа такие, что к . Фигурирующее в этом представлении число к удовлетворяет сравнениям

и

В то же самое время мы получаем

Отсюда получаем следующие сравнения с переменными

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

можно заменить термом

мы придем к выводу формулы, соответствующей высказыванию о том, что при среди чисел, меньших имеется

такое число для которого имеют место сравнения

где фигурируют в качестве произвольных параметров.

Если теперь дополнительно наложить условие которое выражает взаимную простоту чисел т. е. отсутствие у них общих делителей, отличных от 1, то в этом случае мы получим, что среди чисел, меньших существует число удовлетворяющее сравнениям

при произвольных

Еще проще, чем приведенные нами теоремы о наибольшем общем делителе, получаются теоремы о наименьшем общем кратном. Наименьшее общее кратное чисел может быть рекурсивно определено как «наименьшее из тех чисел, не превосходящих а которые делятся на а и на и отличны от при . Можно привести формальное доказательство того, что всякое число, делящееся на а и на делится также и на наименьшее общее кратное чисел

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

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