3. Рекурсивные определения.

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

пояснениях — это метод рекурсивных определений. Давайте постараемся понять, в чем заключается этот метод.

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

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

может определяться равенствами

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

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

Если то заменим в этом выражении цифрой а; в противном случае снова имеет вид с и тогда мы заменим выражением

Снова либо либо с имеет вид . В первом случае заменим цифрой а, во второхм — выражением

Выполнение этого предписания обязательно завершится, так как цифры

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

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

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

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

где суть известные функции. Например, рекурсией

определяется функция

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