§ 2. Рекурсивная арифметика

1. Вывод законов для сложения, вычитания, умножения и для символа ...

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

Такой способ изложения арифметики был предложен Сколемом в 1923 г..

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

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

и

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

Закон ассоциативности сложения

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

Затем, используя закон ассоциативности сложения, а также формулу

которая получается из формулы

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

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

Используя эту формулу и формулу

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

Закон правой дистрибутивности

получается полной индукцией по с с использованием закона ассоциативности сложения.

Из закона правой дистрибутивности и закона коммутативности умножения получается закон левой дистрибутивности

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

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

С помощью последней из них мы индукцией по с получим

Подставив в эту формулу вместо , а затем вместо с и пользуясь равенством

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

Далее, индукцией по с мы получим

а отсюда, в частности,

Кроме того, индукцией по может быть выведена формула

Для этого надо воспользоваться формулами

только что упоминавшейся формулой

и формулой

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

Из формул

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

а из нее в сочетании с законом коммутативности сложения получается

а тем самым и формула

Соответствующая формула для произведения имеет вид

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

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

и формулы

Основываясь на определении отношения

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

и

Первая из них получается из равенства

а вторая — из равенства

в сочетании с формулой

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

Из нее, если учесть определение для с помощью элементарного преобразования получается формула

из которой мы затем получаем

а потом и

Из формулы

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

С другой стороны, из и определения для получается формула

Тем самым мы получаем эквивалентность

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

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

Отметим также, что из ранее выведенной формулы

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

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

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

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

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