x + (a — 1).
Тогда операция х + а будет определена равенством
| х + а = [x + (a — 1)] + 1. | (1) |
Таким образом, мы узнаем, что такое х + а, когда будем знать, что такое x + (a — 1); а так как я вначале предположил, что известно, что такое x + 1, то можно определить последовательными «рекурренциями» операции x + 2, x + 3 и т. д.[2]
Это определение заслуживает некоторого внимания, так как оно имеет особенную природу, отличающую его от определения чисто логического; в самом деле, равенство (1) содержит бесчисленное множество различных определений, и каждое из них имеет смысл только тогда, когда известно другое, ему предшествующее.
Свойства сложения. Ассоциативность. Я утверждаю, что
a + (b + c) = (a + b) + c.
В самом деле, теорема справедлива для c = 1, в этом случае она изображается равенством
a + (b + 1) = (а + b) + 1.
А это — помимо различия в обозначениях — есть не что иное, как равенство (1), при помощи которого я только что определял сложение.
Предположим, что теорема будет справедлива для c = γ; я говорю, что она будет справедлива и для c = γ + 1; пусть, в самом деле,
(a + b) + γ = a + (b + γ);
отсюда следует
[(a + b) + γ] + 1 = [a + (b + γ)] + 1
или в силу определения (1)
(a + b) + (γ + 1) = a + (b + γ + 1) = a + [b + (γ + 1)],
а это показывает с помощью ряда чисто аналитических выводов, что теорема верна для γ + 1.
Но так как она верна для c = 1, то последовательно усматриваем, что она верна для c = 2, для c = 3 и т. д.
Коммутативность. 1. Я утверждаю, что
a + 1 = 1 + a.
Теорема, очевидно, справедлива для a = 1; путем чисто аналитических рассуждений можно проверить, что если она справедлива для а = y, то она будет справедлива для a = γ + 1; но раз она справедлива для a = 1, то она будет справедлива и для a = 2; для a = 3 и т. д.; это выражают, говоря, что высказанное предложение доказано путем рекурренции.
2. Я утверждаю, что
а + b = b + а.
Теорема только что была доказана для b = 1; можно аналитически проверить, что если она справедлива для b = β, то она будет справедлива для b = β + 1.
Таким образом, предложение доказано путем рекурренции.
Определение умножения. Мы определим умножение при помощи равенств
a × 1 = a,
| a × b = [a × (b — 1)] + a. | (2) |
Равенство (2), как и равенство (1), заключает в себе бесчисленное множество определений; после того как дано определение a × 1, оно позволяет определить пси следовательно a × 2, a × 3 и т. д.
Свойства умножения. Дистрибутивность. Я утверждаю, что
(а + b) × c = (а × с) + (b × с).
Мы проверяем аналитически справедливость этого равенства для c = 1; а потом проверяем, что если теорема справедлива для с = y, то она будет справедлива и для c = γ + 1.
Предложение опять доказано рекурренцией.
Коммутативность. 1. Я утверждаю, что
a × 1 = 1 × а.
Теорема очевидна для a = 1.
Проверяем аналитически, что если она справедлива для a = α, то она будет справедлива и для a = α + 1.
2. Я утверждаю, что
а × b = b × а.
Теорема только что была доказана для b = 1. Аналитически проверяем, что если она справедлива дли b = β, то она будет справедлива и для b = β +1
Здесь я прерываю этот монотонный ряд рассуждений. Но именно эта монотонность и способствовала лучшему выделению того однообразного процесса, который мы находим на каждом шагу.
Этот процесс есть доказательство путем рекурренции. Сначала формулируется теорема для n = 1; при этом доказывается, что если она справедлива для n — 1, то она справедлива и для n, и отсюда выводится заключение о справедливости ее для всех целых чисел.
2
Термином «рекурренция» (recurrence) обозначается логическая операция возврата к своему началу. —