f
МАТЕМАТИЧЕСКАЯ БИБЛИОТЕЧКА
Л. ГЕНКИН
О МАТЕМАТИЧЕСКОЙ
ИНДУКЦИИ
Перевод с английского
М. Д. ГРИНДЛИНГЕРА и Е. И. ГРИНДЛИНГЕР
Под редакцией
И. М. ЯГЛОМА
ш
ГОСУДАРСТВЕННОЕ ИЗДАТЕЛЬСТВО
ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ
МОСКВА 19 62

512
Г 34
¦Л*
# • .щ
ON MATHEMATICAL INDUCTION
LEON HENKIN
**4Wu
i MathematicsW<wmuv
•¦¦&¦
СОДЕРЖАНИЕ
Вступительная статья А. С. Есенина-Вольпина . . г . . . 4
Введение 11
1. Модели и аксиомы Пеано 12
2. Операции, определенные по математической индукции . 14
3. Сложение и умножение в произвольных индукционных
моделях 22
4. Операции в моделях Пеано, получаемые путем прими-
примитивной рекурсии 23
5. Отношение между моделями Пеано и индукционными
моделями . . . . 26
6. Отношения конгруэнтности 30
7. Характеризация моделей Пеано 34
Заключение 36
; ¦ . ¦ . ¦¦¦¦;„. ' г-. \ ,¦¦ ."¦' ¦=:¦¦ . , ¦ -.к<
Леон Генкин.
О математической индукции.
М., Физматгиз, 1962 г., 36 стр.
Редакторы Ф. Л. Варпаховский и А. Н. Копылова.
Техн. редактор К. Ф. Брудно. Корректор А. С. Бакулова.
Цена книги 6 коп. Заказ № 332С.
Государственное издательство физико-математической литературы.
Москва, В-7 1, Ленинский проспект, 15.
Первая Образцова* типография имени А..А.,Ж
Московского городского совнархоза. Москва, Ж-54,
аловая. 28.
2 Л. Геиьсий

ВСТУПИТЕЛЬНАЯ СТАТЬЯ
Предлагаемая вниманию читателя работа Л. Генкина
«О математической индукции» относится к основаниям
арифметики.
Все знают о математике, что это — очень важная и очень
сложная наука, но даже специалисты не всегда ясно пред-
представляют себе пути ее развития. И, к сожалению, до сих
пор лишь немногим известно, что развитие математики
вызвало к жизни новую науку — науку об основаниях
математики. Эта наука, значительную часть которой
составляет ядро так называемой математической логики,
анализирует и совершенствует те методы, которыми поль-
пользуется математика при доказательстве своих теорем. Именно
этой науке математика обязана верой в незыблемость своих
результатов.
Математическая логика, о которой мы упомянули, изу-
изучает, кроме того, исчисления, применяемые в современных
математических машинах и многих сложных автоматах. В этой
связи некоторое, правда довольно поверхностное, знакомство
с математической логикой распространяется за последние годы
среди инженеров, и название этой области науки ассоциируется
с названием еще очень молодой, но многообещающей науки —
кибернетики. Эта связь между абстрактной теорией и прак-
практикой объясняется в данном случае тем, что в основаниях
математики доводится до крайних пределов логический
анализ методов математических доказательств и вычислений
и только после этого анализа становится возможной авто-
автоматизация этих методов.
Хотя Л. Генкин в своей работе не пользуется специфи-
специфическим языком математической логики, эту работу следует
отнести к одному из "разделов математической логики, а
именно к теории моделей.
Для того чтобы помочь неспециалисту разобраться
в работе, укажем характерные черты современного аксиома-
аксиоматического метода, имея прежде всего в виду его примене-
применения к арифметике.
Аксиоматический метод, правда, отнюдь не в его совре-
современном виде, известен широкой публике из школьного курса
геометрии. Основная черта этого метода состоит в том, что
каждое утверждение — теорема — доказывается чисто умо-
умозрительным путем, а именно посредством логического вывода
этой теоремы из ранее доказанных теорем. Но так как этот
процесс должен с чего-то начинаться, то некоторые утверж-
утверждения, именуемые аксиомами, принимаются без доказатель-
доказательства, а уже остальные теоремы доказываются затем логи-
логическим путем. Аксиомы при этом обычно обосновываются
ссылкой на очевидность.
Такой способ построения теории сообщает каждому ее
результату ту же степень очевидности, которая присуща
аксиомам, и, по мере развития математики на протяжении
последних столетий, он распространялся с геометрии и.на
остальные ее разделы. Однако до конца прошлого столетия
аксиоматический метод существовал скорее в теории, чем
на практике. Аксиомы формулировались далеко не полностью,
и в доказательства, наряду с ними, вторгались недока-
недоказанные предложения, считавшиеся очевидными.
Так продолжалось до последних десятилетий прошлого
столетия, когда, наконец, в концепции аксиоматического
метода наступил переломный момент. Это было в большой
мере связано с появлением неевклидовой геометрии Лоба-
Лобачевского—-Больаи и возникшей в связи с этим задачей
обоснования этой геометрии: нужно было доказать, что
евклидова аксиома о параллелях не вытекает из остальных
аксиом. Для этого, конечно, потребовалось установить точ-
точный перечень аксиом геометрии (такой перечень был пред-
предложен Гильбертом1)), и наступила новая эпоха в понимании
аксиоматического метода, характеризующаяся более высоким
уровнем строгости.
Не только теоремы должны аккуратно выводиться друг
из друга и, в конечном счете, из аксиом, но и все понятия
теории должны вводиться не иначе, как посредством опре-
определений, выражающих их через ранее введенные понятия.
1) См., например, статью П. К. Рашевского «Геометрия
и ее аксиоматика», сб. «Математическое просвещение», вып. 5, 73—98
(I960). (Прим. ред.)

Но так как этот процесс тоже должен иметь начало, то
какие-то понятия, именуемые первоначальными, должны
считаться с самого начала известными — скажем, из интуиции.
В известной степени это, конечно, осознавалось и раньше,
и тем не менее до конца прошлого столетия перечень пер-
первоначальных понятий математических теорий не уточнялся,
и в основаниях математики царила путаница.
Всякое предложение (т. е. аксиома или теорема) перейдет
в равнозначное ему по смыслу, если мы выразим посредством
определений все входящие в него понятия через ранее
введенные и, в конечном счете, через первоначальные.
Аксиомы приобретут при этом такую формулировку, в кото-
которую входят только первоначальные понятия и соединяющие
их логико-грамматические связки (такие, как «если», «на»,
«каждый» и т. п.; эти связки употребляются в рассуждениях
в соответствии с правилами, устанавливаемыми в математи-
математической логике). И так как кроме аксиом мы не можем поль-
пользоваться в доказательствах никакими другими недоказанными
предложениями, то аксиомы содержат в себе все сведения
о первоначальных понятиях, которые нам даны для построе-
построения аксиоматической теории. В этом смысле на аксиомы
следует смотреть как на определения первоначальных по-
понятий. (Это суть, впрочем, неявные определения, в отличие
от тех явных, о которых мы говорили выше.)
Всякая аксиоматическая теория, по определению, зани-
занимается выводом следствий из определенных аксиом. Изме-
Изменение этих аксиом есть вместе с тем изменение аксиомати-
аксиоматической теории.
Среди первоначальных понятий теории могут иметься:
собственно понятия, характеризующие род изучаемых
объектов (например, точки, прямые, числа и т. п.);
отношения между объектами одного и того же или раз-
различных родов (такие, как: точка Л лежит между точками
В и С, точки А и В лежат на прямой с, число а меньше
числа Ь и т. п.); термины, служащие для обозначения
конкретных объектов [например, число 0 (нуль)], и опера-
операции или функции, определенные над изучаемыми объектами
[скажем, движение — в аксиоматике геометрии, групповая
операция (сложение или умножение), сопоставляющая
двум элементам группы третий элемент,— в аксиоматике
группы]. Индивидуальные объекты, роды объектов, отноше-
отношения и операции, определенные над объектами, образуют то,
что принято кратко называть системой объектов.
Всякая система объектов, удовлетворяющая аксиомам
какой-либо аксиоматической теории (в том смысле, что из
аксиом должны получиться истинные предложения, если
вместо первоначальных понятий подставить названия этих
объектов, родов, отношений и операций), называется интер-
интерпретацией или моделью этой аксиоматической теории.
Изучение моделей аксиоматической теории составляет пред-
предмет теории моделей; этой теории (в применении к аксио-
аксиоматической теории Пеан о, о которой мы скажем ниже)
и посвящена статья Генкина.
Предметом изучения аксиоматической теории может
служить любая ее модель. Благодаря этому применимость
аксиоматической теории шире, чем применимость соответ-
соответствующей не строго аксиоматизированной теории.
Не имеет смысла говорить об «очевидности» аксиом
аксиоматической теории просто потому, что первоначальным
понятиям не придается никакого другого смысла, кроме того,
что они удовлетворяют аксиомам. Очевидность есть интуи-
интуитивное понятие, и очевидными (в интересующем нас сей-
сейчас смысле) могут быть лишь предложения, относящиеся
к таким системам объектов, которые даны нам в интуитивном
восприятии. Но благодаря нашей интуиции мы действительно
можем строить такие «интуитивные» системы объектов и
говорить об очевидности того, что они удовлетворяют
аксиомам какой-либо аксиоматической теории.
Теоретически приходится рассматривать и такие системы
аксиом, для которых вовсе не существует интерпретации.
Имея дело с конкретной аксиоматической теорией, мы зара-
заранее не можем знать, допускает ли она интерпретацию.
Важнейшими проблемами, которые встают при изучении
аксиоматической теории, являются:
а) Доказательства непротиворечивости, т. е. невоз-
невозможности прийти в ней к логическому противоречию. Про-
Противоречивая теория, конечно, не может иметь модели, в то
время как существует классическая теорема о том, что вся-
всякая непротиворечивая аксиоматическая теория имеет
модель. Это — знаменитая теорема Геделя о полноте
классического исчисления* предикатов, доказанная им
в 1930 г. Заметим, что самое простое и наиболее совер-
совершенное в логическом отношении доказательство этой тео-
теоремы было дано Л. Генкиным в 1949 г.').
!) L. Н е п k i п, The completeness of the firstorder functional
calculus, The Journal of symbolic logic 14, 1949, стр. 159—166.

б) Решение вопроса о полноте аксиоматической теории.
Теория называется полной, если всякое предложение, кото-
которое можно в ней сформулировать, может быть доказано или
опровергнуто на основе ее аксиом. Для большинства аксио-
аксиоматических теорий, охватывающих аксиоматическое построе-
построение обыкновенной арифметики натуральных чисел 0, 1, 2, ...,
вопрос о полноте решается отрицательно (теорема Геделя
о неполноте, 1931 г.).
в) Решение проблемы разрешения, т. е. указание метода,
позволяющего для каждого конкретного предложения аксио-
аксиоматической теории установить, доказуемо ли оно в этой
теории. Этот вопрос для большинства аксиоматических тео-
теорий также решается отрицательно (теорема Черча, 1936 г.).
Имеются и другие проблемы, о которых мы здесь не
будем говорить. Подробное обсуждение основных проблем
аксиоматических теорий возможно только на языке матема-
математической логики.
Арифметика сравнительно поздно стала аксиоматической
теорией. Хотя первые попытки аксиоматизации арифметики
встречаются уже в XVIII в. (Христиан Вольф), но более
или менее стройная картина, дошедшая до наших дней,
возникла только в XIX в. В 40-х годах XIX в. Г. Грассман
свел теорию рациональных чисел — положительных и отри-
отрицательных — к теории натуральных чисел; эта последняя
изучалась затем в ее основах Дедекиндом 1) A888 г.), кото-
который еще раньше A872 г.) построил свою знаменитую теорию
действительных чисел, связанную с теорией множеств.
Затем известный итальянский математик Пеано A889 и 1891 гг.)
построил систему аксиом для арифметики натуральных чисел.
Приводим (с небольшими второстепенными изменениями)
систему аксиом Пеано:
Первоначальные понятия: нуль @) и число,
следующее за; число, следующее за числом а, обозначается
через а'.
Аксиомы:
I. 0 есть число, не следующее ни за каким числом.
II. Если число а' равно числу I/, то и число а равно
числу Ь.
III. Если число 0 обладает некоторым свойством Р
и для всякого числа а из того, что а обладает свойством
!) R. Dedekind, Was sind und was sollen die Zahlen, Braun-
Braunschweig, 1888.
8
P, следует, что и число а' обладает свойством Р, то
всякое число п обладает свойством Р.
Отношение «равенство», о котором идет речь в аксиоме II,
рассматривается как относящееся скорее к логике, чем
к арифметике. Оно характеризуется аксиомами:
1) для любого числа а имеем а = а;
2) если а = Ь и верно некоторое предложение Р, то
верно и всякое предложение, получающееся из Р путем
замены в каком-нибудь месте а на Ь.
Из этих аксиом следует, в частности, что если а = Ь,
то a' — bf (но не то, что из равенства а! = Ь' следует
а = Ь, — это есть аксиома II Пеано), иными словами, что
для всякого числа имеется только одно число, следующее
за ним. В самом деле: по аксиоме 1) а' = а', и еслиа = ?,
то по аксиоме 2) a' = t>\ так как это равенство получается
из а'=-а' путем замены второго а на Ь. Аналогично дока-
доказывается и то, что если а = Ь, то Ь = а (так как равенство
b — а получается из аксиомы 1) путем замены первого а на
Ь), и что если а = Ь и Ь = с, то и а = с (так как если
а — Ь, то утверждение «если Ь=с, то а = су> получается
из логически очевидного предложения «если а = с, то а = с»
путем оа.ме;;ы первого а на Ь).
Последнюю аксиому Пеано, аксиому III, часто называют
аксиомой индукции. Ей иногда придают другую форму.
Именно, считается, что в связи с каждым свойством Р можно
рассматривать множество (т. е. совокупность или систему)
тех чисел, которые обладают свойством Р и обратно —
в связи с каждым множеством чисел можно рассматривать
их свойство, состоящее в том, что число является элемен-
элементом этого множества (т. е. принадлежит ему). С помощью
понятия множества аксиому III можно сформулировать так:
ИГ. Если 0 является элементом некоторого мно-
множества G и для всякого числа а из того, что а является
элементом О (в принятых обозначениях: а?О), следует,
что и число а' является элементом G (т. е. а! ? G), то
всякое число п является элементом G.
Заметим, что аксиома III «содержит термин «свойство»,
а равносильная ей аксиома ИГ — термин «множество». Эти
термины не принадлежат к числу первоначальных и
не были введены посредством определения. Поэтому систему
аксиом Пеано можно положить в основу арифметики только
в том случае, если понятия «свойство натуральных чисел»
или «множество натуральных чисел» считаются известными

из логики, что связано с глубокими трудностями принципи-
принципиального характера. Л. Генкин в своей работе избирает
именно этот путь, не останавливаясь на связанных с ним
трудностях. Не будем на них здесь останавливаться и мы.
Леон Генкин ,известен как автор ряда работ по матема-
математической логике. Ему принадлежат важные исследования
о полноте логических исчислений; об одном из этих ис-
исследований мы упоминали выше. Последние годы он много зани-
занимался применениями математической логики — точнее, теории
моделей—к проблемам абстрактной алгебры. Эта алгебра-
алгебраическая тенденция нашла выражение и в помещаемой ниже
работе.
Эта работа, написанная Л. Генкиным для «Математиче-
ского просвещения», не потребует от читателя никаких
предварительных познаний. Неспециалист получит из нее
верное представление о характере многих рассуждений
современной теории моделей. Специалисту также интересно
будет познакомиться с некоторыми свежими соображениями,
относящимися к связи между теорией рекурсивных опреде-
определений (т. е. определениями по индукции) и теорией моделей,
изучение которой составляет предмет работы Генкина.
Л. С. Есенин-Вольпин
ВВЕДЕНИЕ
Согласно современным критериям логической строгости
каждая ветвь чистой математики должна быть обоснована
одним из двух способов: или все ее основные понятия должны
быть определены в терминах понятий некоторой пред-
предшествующей ветви математики, в таком случае ее теоремы
могут быть выведены из теорем предшествующей ветви
математики с помощью этих определений; или ее основные
понятия берутся как неопределяемые, и ее теоремы
выводятся из совокупности аксиом, включающих в себя эти
неопределяемые термины.
Натуральные числа 0, 1, 2, 3, ... относятся к тем ма-
математическим объектам, которые мы изучали в раннем воз-
возрасте, и наши знания об этих числах и их свойствах,
вообще говоря, имеют интуитивный характер. Тем не менее,
если мы желаем построить точную математическую теорию
этих чисел, мы не можем полагаться на несформулированную
интуицию как на основу теории, и нам необходимо обосно-
обосновать теорию одним из двух способов, упомянутых выше.
Фактически возможны оба эти способа.
Так, немецкий математик Фреге показал, как, отправляясь
от чистой логики и самых элементарных частей теории
множеств, определить основные понятия теории чисел таким
образом, чтобы затем вся теория могла быть построена,
исходя из этих определений. С другой стороны, итальянский
математик Пеано, принимая в качестве первоначальных не-
неопределяемых понятий напТуральные числа, нуль и сле-
следующее за, дал систему аксиом, на базе которой также
может быть построена вся теория натуральных чисел.
В настоящей работе мы рассмотрим понятие определение
по математической индукции в рамках основных идей
U

Пеано. В нашем изложении мы принимаем в качестве пред-
предпосылки только логику и самые элементарные части теории
множеств; однако мы увидим, что наш предмет сильно
прояснится после введения терминологии, идущей от совре-
современной абстрактной алгебры, хотя для построения наших
определений и доказательств мы не используем соответст-
соответствующий алгебраический материал.
1. МОДЕЛИ И АКСИОМЫ ПЕАНО
Нам будет удобно пользоваться словом модель для обо-
обозначения системы, состоящей из некоторого множества N,
некоторого элемента 0 из TV и унарной операции 5 на /V1).
Модель <Л/, 0, ?> будем называть моделью Пеано,
если она удовлетворяет следующим трем условиям (или
аксиомамJ):
Р1. Для всех x?N Sx=?0.
Р2. Для всех х, y?N, если хфу, то Sx=^=Sy.
РЗ. Если G — подмножество множества N, такое, что
(а) О С G и (Ь) всякий раз, когда x?G, также и Sx?G,
то G=N3).
Если /V* есть множество натуральных чисел в том виде
как мы его знаем по интуиции, 0* есть число нуль и S*
г) Унарная операция на N —это функция, имеющая N в каче-
качестве своей области определения, область значений которой является
подмножеством множества N. Для любого x?N Sx означает элемент
из N, полученный применением операции S к х.
2) Ср. с формулировкой тех же аксиом в предисловии (стр. 8).
(Прим. ред.)
8) По терминологии теории множеств, Р1 и Р2 соответственно
выражают условия, что 0 не принадлежит области значений S и
что операция S взаимно-однозначна. О подмножестве G из N, кото-
которое удовлетворяет условию (Ь) из РЗ, говорят, что оно замкнуто
относительно S.
[Если рассматривать C/V, 5> в качестве алгебраической
системы, то подмножество G из N, замкнутое относительно 5,
называется подалгеброй системы. Таким образом, условие РЗ выра-
выражает тот факт, что единственная подалгебра <W, S>, содержащая
элемент О, есть само N. В алгебраической терминологии это усло-
условие формулируется так: элемент О порождает алгебру <W, S).
Можно также рассматривать саму систему <А/, 0, 5> в качестве
алгебраической системы. В этом случае, чтобы подмножество G из
N рассматривалось как подалгебра, оно должно содержать 0 и быть
замкнутым относительно S. Таким образом, РЗ означает, что един-
единственной подалгеброй из <N,~0, S) является само N.]
12 *
есть операция «следующее за» (т. е. такая операция, что
для любого числа х S*x есть следующее за ним число),
то </V*, О*, S*> — пример модели Пеано. Именно этот при-
пример в первую очередь привел к рассмотрению аксиом Пеано.
Заметим, однако, что есть много других моделей Пеано,
например система <ЛЛ, О', S'>, где N' — множество всех
положительных четных чисел, 0' — число два и S' — опера-
операция прибавления двух.
Условие РЗ называется аксиомой математической
индукции. Будет полезно ввести термин индукционная
модель, обозначающий любую модель, которая удовлетво-
удовлетворяет этой аксиоме. Таким образом, мы видим, что каждая
модель Пеано является индукционной моделью. Но обратное
утверждение неверно.
Например, пусть N" — множество, содержащее един-
единственный элемент 0", и S" — единственно возможная
унарная операция на ЛГ', т. е. такая операция, что S"=0".
Тогда ясно, что <Л/", О", S"> является индукционной мо-
моделью; однако это не есть модель Пеано, потому что она
не удовлетворяет аксиоме Р1. Другой пример: пусть а0 и
ах—два различных объекта и пусть N'" является парой
{а0У а,} (т. е. множеством, элементами которого являются
только а0 и ах). Пусть унарная операция S'" на N'" имеет
постоянное значение ах (т. е. S"fx=^al для всех x?N).
Тогда <ЛГ", а0, S'"> является индукционной моделью, но
не моделью Пеано, потому что она не удовлетворяет ак-
аксиоме Р2.
Читатель может заметить, что модель <ЛГ, О", S"> удо-
удовлетворяет Р2, а модель <ЛГ"/, а0, Sf"> удовлетворяет Р1.
Естественно возникнет вопрос, существуют ли индукцион-
индукционные модели, которые не удовлетворяют ни Р1, ни Р2?
Оказывается, нет: каждая модель, которая удовлетво-
удовлетворяет РЗ, должна также удовлетворять или Р1,
или Р2.
Прямое доказательство этого факта, если использовать
только законы логики и элементы теории множеств, найти
довольно трудно — предоставим эту работу читателю. Впо-
Впоследствии мы увидим, что цюсле построения теории опреде-
определения по математической индукции этот результат можно
будет получить достаточно просто.
Теперь рассмотрим следующие два предложения:
Р4. Если у есть такой элемент N, что y=^=Sx для
всех x?N, то у = 0.
id

P5. Для всех x?N
Очевидно, что оба эти предложения верны для модели
Пеано (N*, 0*, 5*> натуральных чисел, известных нам по
интуиции; более того, мы можем легко вывести их из
аксиом Р1—РЗ и тем самым показать, что каждое из них
верно для всех моделей Пеано.
Но есть важное различие между предложениями Р4 и
Р5: доказательство Р4 использует только аксиому РЗ, так
что Р4 верно для всех индукционных моделей, в то время
как доказательство Р5 опирается как на аксиому РЗ, так и
на аксиомы Р1 и Р2, и наш пример <ЛГ, О", S") показывает,
что Р5 верно не для всех индукционных моделей.
2. ОПЕРАЦИИ, ОПРЕДЕЛЕННЫЕ
ПО МАТЕМАТИЧЕСКОЙ ИНДУКЦИИ
Предложения Р4 и Р5 являются примерами теорем, отно-
относящихся к учению о натуральных числах, но мы обычно
считаем их математическое содержание довольно тривиаль-
тривиальным. Чтобы построить более содержательную теорию, необ-
необходимо познакомиться с другими понятиями кроме первона-
первоначальных понятий «число», «нуль» и «следующее за»; в пер-
первую очередь определим такие центральные понятия, как
сложение, умножение, возведение в степень,
простое число и т. д.
Рассмотрим сначала операцию сложения и исследуем,
как она может быть определена.
Сложение есть бинарная операция, определенная в мно-
множестве натуральных чисел, т. е. функция «-[-» двух пере-
переменных, сопоставляющая любой упорядоченной паре <лг, уу
натуральных чисел новое натуральное число, обозначаемое
через х-\-у. По идее Пеано, эта функция «-{-» опреде-
определяется двумя условиями:
A.1)
A.2)
*) Для модели Пеано </V*, О*, S*> (множество натуральных
чисел) эти предложения означают: Р4. Число, не следующее ни за
каким числом, есть 0. Р5. Ни одно из чисел не следует за самим
собой. (Прим. ред.)
14
Интуитивные представления об операции сложения убеж-
убеждают нас, что эти условия выполняются для всех нату-
натуральных чисел х и у.
Но в каком смысле условия A.1) и A.2) составляют
определение сложения? В частности, определяется ли этими
условиями некоторая удовлетворяющая им бинарная операция
в случае произвольной модели Пеано?
Чтобы получить ясный ответ на эти вопросы, мы рас-
рассмотрим сначала одну связанную с ними более общую
проблему.
Введение операции при помощи двух равенств A.1) и
A.2) является примером определения по математической
индукции. Чтобы описать это понятие в общих терминах,
мы должны задать модель Пеано <N, 0, Sy и вторую мо-
модель <Nj, Op 5j>, которая, однако, не обязана быть мо-
моделью Пеано (или даже индукционной моделью). Мы скажем,
что два равенства
• , * *@) = 01Э B.1)
= Sl(hy)
B.2)
определяют (по математической индукции) функцию /г,
отображающую N в Nx (т. е. такую, что hy ? Nx для
любого у ? N), если для всех у ? N удовлетворяются эти
условия *). Снова можно задать вопрос: в каком смысле эти
условия определяют функцию А? Ответ дает следующая
теорема.
Теорема 1. Для любой модели Пеано Jf= <N, 0, 5>
и для любой другой модели Jfl = <kNl, 0x, Sty существует
одна и только одна функция h, отображающая N в Nx1
которая удовлетворяет B.1) и B.2) для всех у ? N.
Прежде чем перейти к доказательству этой теоремы,
выясним ее связь с условиями A.1) и A.2).
Пусть оДГ — произвольная модель Пеано <Л/, 0, S> ; для
каждого х ? N образуем модель Пеано оН*х= <Afx, я» 5>»
где Nx — подмножество множества Л/, образованное элемен-
элементами ху Sxy S(Sx) и т. д. Применяя теорему 1 к моделям
сДГ и сЛГ*, мы видим, что «для каждого х ? N существует
единственная функция hx> отображающая N в себя так, что
!) Отображение h, удовлетворяющее условиям B.1) и B.2),
можно назвать гомоморфизмом, переводящим <#, 0, S> в <#1Э 0v Sx>.
(Прим. ред.)
15

выполняются условий
и (для всех у ? N)
hx(Sy) = S(hxy).
C.1)
C.2)
Из существования и единственности такой функции hx мы
и выведем существование единственной бинарной операции
сложения на <N, О, S> !).
Пусть /—бинарная операция на /V, сопоставляющая
любым х, у ? N третий элемент fxyt определяемый сле-
следующим образом: .
• ¦ hxy. D)
Используя равенства D), C.1), C.2), ашшЬем, что/
•влетвоояет у?ллвиям .• ^..
удовлетворяет условиям
fx(Sy) = S(fxy)
E.1)
E.2)
для всех х, у ? N.
Далее, / является единственной бинарной опера-
операцией на N, обладающей этими свойствами. В самом деле,
пусть g—некоторая бинарная операция на N, удовлетво-
удовлетворяющая условиям
gxO = x, F.1)
gx(Sy) = S(gxy) F.2)
для всех ху у ? N. Сопоставим каждому х ? N унарную
операцию gx на N, такую, что для всех у ? N
Из G), F.1) и F.2) заключаем, что прв любом х ? N вы-
выполняются условия
&0 = х, , ¦. (8.1)
gx(Sy) = S(gxy). > ;- (8.2)
Сравнивая C.1), C.2) с (8.1), (8.2), мы замечаем, что
gx = hx для каждого х ? N, так как из теоремы I выте-
вытекает единственность функции /гХУ определенной условиями
*) Для дальнейшего C, стр. 23) будет полезным отметить, что
соображения, на которых будет базироваться этот вывод, носят чисто
теоретико-множественный характер и никоим образом не зависят от
аксиом Р1 — РЗ.
16
C.1) и C.2). Но отсюда в силу D) и G) следует, что
fxy — gxy для всех х, у ? N, что и означает совпадение
бинарных операций / и g на N.
Итак, из теоремы I следует, что для любой модели
Пеано <N, 0, ?> существует единственная бинарная опера-
операция /на N, удовлетворяющая E.1) и E.2) для всех х, у ? N.
Эту бинарную операцию мы назовем сложением; если обо-
обозначить ее символом -|~» то мы заметим, что условия A.1)
и A.2) суть просто записанные другим способом E.1) и
E.2). Таким образом, теорема I показывает, что действи-
действительно сложение можно определить условиями A.1) и A.2).
Перейдем теперь к доказательству теоремы I.
Пусть <N, О, S> — любая модель Пеано и <ЛГ1, 0р S^ —
произвольная модель. Мы хотим доказать существование
единственной функции Л, отображающей N в Nv которая
удовлетворяет условиям B.1) и B.2) для всех у ? N. Иногда
для обоснования существования такой функции h (не каса-
касаясь пока вопроса единственности) приводят следующее рас-
рассуждение.
Ясно, что операция h определена для элемента 0, так
как /Ю = 0, в силу B.1). Далее, если операция h опреде-
определена для элемента у ?N, то она определена и для эле-
элемента Sy, поскольку, в силу B.2), h(Sy) = Sl(hy). Таким
образом, если мы положим, что G—множество всех таких
у g Л/, для которых операция h определена, то (а) 0 ? О
и (Ь) всякий раз, когда у ? G, Sy ^ G. Применяя аксиому
РЗ, заключаем отсюда, что G=N. Таким образом, h опре-
определено для всех у ? N.
На первый взгляд эти доводы представляются убедитель-
убедительными, но после некоторых размышлений возникают сомне-
сомнения. В самом деле, в этих рассуждениях мы ссылаемся на
некоторую функцию А. Но что такое Ю Очевидно, она яв-
является функцией, которая удовлетворяет условиям B.1) и
B.2). Вспомним, однако, что наши рассуждения и предна- *
значены для того, чтобы обосновать существование
такой функции; тогда станет ясно, что 'мы не имеем
права использовать в этом рассуждении допущение о том,
что мы такую функцию имеем.
Сначала можно подумать* что это возражение представ-
представляет собой простую придирку, которую можно устранить
путем несущественного изменения рассуждения. Однако на
самом деле в нашем рассуждении кроется существен-
существенная ошибка, поскольку единственное свойство модели
17

<N, 0, S>, которое здесь используется,— это аксиома РЗ!
Поэтому если бы это рассуждение было существенно пра-
правильным, то из него следовало бы, что для любой индук-
индукционной модели <N, 0, Sy и произвольной модели
<7VP 0,, 6\> существует функция h, отображающая N в Nx
и удовлетворяющая условиям B.1) и B.2) для всех у ? N.
Но, как показывает следующий пример, это утверждение
просто неверно.
Пусть <№'" — <N"\ а0, S'"> — рассмотренная в § 1 ин-
индукционная модель, где N'" состоит всего из двух различ-
различных объектов а0 и ах\ S'nx = al для всех х ? N"'; Т—-
унарная операция на Л/'", такая, что Тао = аА и Таг = а0,
и (№[" — модель <ЛГ", а0, Ту. Предположив, что теорема I
применима к моделям сЛР'" и <АГ"\ мы заключим, что сущест-
существует такое отображение /г, переводящее N'" само в себя,
что для всех у ? Л/'"
(9 2)
Из (9.2) следует, что h(al) = h(S'"a9)=T(ha0) и, сле-
следовательно, в силу (9.1), А(а1)=Га0 = а1. С другой сто-
стороны, применяя (9.2), по-другому получим, что h(ay) =
= h(S'"al)=T{haA), и так как мы уже доказали, что
h(al) = al, то h{ax) — Tax — ar Но из /г(ах) = а0 и
h(al) = al следует, что ао = а1, а это противоречит нашей
гипотезе, предполагающей, что а0 и а1 различны. Из по-
полученного противоречия следует, что теорема 1 неприме-
неприменима к индукционной модели о1\Г"'; это показывает a fortiori,
что любое доказательство этой теоремы должно использо-
использовать, кроме РЗ, также и аксиому Р2; фактически, как мы
увидим ниже, должны использоваться все три аксиомы.
Это обстоятельство можно выразить так: одной аксиомы
математической индукции недостаточно для определений
по математической индукции*).
Доказательство теоремы 1. Пусть с)\Р =
= </V, 0, 5> — любая модель Пеано и MX = <NV О,, ?,> —
некоторая произвольная модель. Подмножество И из N на-
называется сегментом, если 1) 0 ? И и 2) всякий раз, когда
l) Это замечание было ясно высказано Дедекиндом в его зна-
знаменитой книге «Was sind ujid was sollen die Zahlen ?» (См. Reraerk-
ungen, параграф 130, раздел 9.)
Л •
Sx ? Я, то и х ? Н1). Назовем частичной функцией такую
функцию у, которая 1) определена на некотором сегменте //,
2) принимает значения, принадлежащие множеству Nx, при-
причем условия
70 = 0^ (юл)
j(Sx) = Sl{jx) • A0.2)
выполняются для всех х, таких, что Sx ? Н.
Лемма 1. Каждый элемент из N принадлежит об-
области определения какой-либо частичной функции.
Доказательство. Пусть О—множество элемен-
элементов N, которые принадлежат области определения какой-
либо частичной функции. Ясно, что множество {0}, содер-
содержащее только один элемент 0, можно считать сегментом,
так как в силу аксиомы Р1, не существует такого х, что
Sx ? {0}. По той же причине функция j с областью опре-
определения {0} и значением у'0 —0, является частичной функ-
функцией. Следовательно, 0 ? G.
Теперь допустим, что у — любой элемент G и у — час-
частичная функция, область определения которой И содержит у.
Если Sy ? /¦/, то Sy также принадлежит к G; поэтому рас-
рассмотрим случай, когда Sy ? И2). Обозначим через И' под-
подмножество Л/, полученное из И прибавлением Sy, и пусть f
есть функция, область определения которой совпадает с Н'
и значения которой задаются следующим образом: если
х?Н, то fx=jx, и если x — Sy, то fx = Sl(jy). Ниже
мы покажем, что у' является частичной функцией и, следо-
следовательно, если Sy?H, то (так же как и в противоположном
случае, отмеченном выше) Sy ? G. Так как G содержит 0
и замкнуто относительно S, то, в силу аксиомы РЗ G=N.
Этим, согласно определению G, и доказывается наша лемма.
Таким образом, чтобы завершить доказательство леммы,
нам остается только показать, что у' является частичной
функцией. Для этой цели рассмотрим сначала область опре-
определения Н' функции у\ включающую множество И и эле-
элемент {Sy}. Так как И—область определения частичной
функции, то она является сегментом и, следовательно,
0 ? /У, а поэтому 0?#'. Далее, если х есть любой элемент
!) Очевидно, что для множества натуральных чисел любой сег-
сегмент представляет собой совокупность всех чисел от 0 до некоторого
числа /е^включительно.
z) ? означает — «не принадлежит». (Прим. ред.)

из /V, такой, что Sx ? Н\ то также и х?Н', ибо а) если
Sx?Hy то х?Н, потому что И—сегмент; б) если Sx = Syy
то х = у по аксиоме Р2, и опять х?Н (так как мы знаем,
что у ? Н). Эти рассуждения показывают, что И' является
сегментом.
Далее, у'О=уО = О1 и f (Sx)=Sl(/x) всякий раз,
когда Sx?H'. Последнее равенство базируется на раздель-
раздельном рассмотрении тех же двух случаев, что и выше:
а) если Sx?H, то х ? И; так что
/ (Sx) =j (Sx) = SY (jx) = S1 (j'x);
б) если Sx = Sy, то х=у и, следовательно,
J'(Sy)=sl(jy)=sl(j'y). ;
Так как область определения ) является сегментом и /
удовлетворяет условиям A0.1) и A0.2), то у" есть частич-
частичная функция. Таким образом, лемма 1 доказана.
Лемма 2. Если j\ и ]% — две частичные функции и х
принадлежит области определения каждой из них, то
Jlx=j2x.
Доказательство. Пусть G—множество таких эле-
элементов х из N, что j\x=J2x всякий раз, когда jx и у2 —
частичные функции, область определения каждой из кото-
которых содержит х. Ясно, что OgG, так как /0=»01 для
любой частичной функции у.
Пусть теперь х — произвольный элемент G, а у, и у2 —
произвольные частичные функции, область определения*
каждой из которых содержит Sx. Тогда Jl(Sx)=Sl(Jlx)
и Ji{Sx) = Sl(J2x). Но так как x?G, то j\x=j2x и, сле-
следовательно, j\(Sx)=j2(Sx). Поэтому Sx?G. Так как 0?G
и G замкнуто относительно 5, то по аксиоме РЗ, G=N.
На основании определения множества G мы заключаем, что
лемма 2 справедлива.
Из лемм 1 и 2 следует, что для любого х ? N имеется
один и только один элемент z?Nv такой, что z=Jx для
любой частичной функции /, область определения которой
содержит х (хоть одна такая функция найдется). Пусть
h — функция с областью определения N, такая, что для
любого x?N значение hx определяется именно этим z?Nv
Мы утверждаем, что эта функция h при всех у ? N удовлет-
удовлетворяет условиям B.1) и B.2) и что она есть единственная
функция с областью определения N, которая обладает этим
свойством.
20
Ясно, что h0 = 01, так как у'О == 0, для любой частич-
частичной функции у. Далее, для любого у ? N имеется такая
частичная функция у, что Sy принадлежит области опреде-
определения у (по лемме 1). Отсюда мы заключаем, что h(Sy) =
—j(Sy) = Sl(jy) = Sl(hy)i так что h действительно удов-
удовлетворяет условиям B.1) и B.2). Далее, если hx — любая
другая функция с областью определения N, которая удов-
удовлетворяет B.1) и B.2) для всех у ? N, то h1=h. Зто
вытекает из того, что Л/, очевидно, есть сегмент, так что
обе функции h и hx являются частичными и, следовательно,
в силу лемм:>1 2, hx = hlx для всех х ? N. А это и озна-
означает совпадение функций h и hx.
Этим завершается доказательство теоремы I.
Это доказательство гораздо сложнее приведенного вна-
вначале простого рассуждения, но зато оно имеет перед ним
то бесспорное преимущество, что оно правильно. Читатель
может заметить, что в этом доказательстве были использо-
использованы все аксиомы Р1—РЗ (в связи с леммой 1).
Построение h с помощью частичных функций, использованное
в этом доказательстве,— не единственный известный нам способ опре-
определения этой функции. Существует и другой метод построения h,
приводящий к другому доказательству теоремы I.
Наметим кратко этот другой процесс построения, предоставляя
читателю восполнить детали доказательства.
Исходя из данной модели Пеано <N, 0, S> и произвольной модели
<iV,, 0j, Sj>, рассмотрим подмножества А множества jVXN, (произ-
(произведения N и #,), т. е. такие множества Л, элементами которых
являются упорядоченные пары <х, у>, где x?N, y?Nx. Подобное
множество А мы назовем регулярным, если <0, 0,>?Л и если каж-
каждый раз, когда <*, у>?А, то и (Sx, S^yy^A. Очевидно, регулярные
множества существуют (например, само множество N X^i). Далее
легко видеть, что пересечение А* всех регулярных множеств А само
есть регулярное множество. Теперь, используя аксиомы Р1 — РЗ,
справедливые для модели </V, 0, S>, можно показать, что для каж-
каждого x?N есть один и только один «/?#,, такой, что (х, уУ?А*
(детали этого доказательства предоставляем читателю восполнить
самостоятельно).
Показав это, мы определяем h как функцию с областью опреде-
определения N, такую, что для любого x?N hx есть единственный элемент
#€^i> Аля второго <лс, уУ?А*. Из того факта, что А регулярно,
легко следует, что h удовлетворяет условиям теоремы I (т.е. h есть
гомоморфизм N в /Vj). Наконец, чтобы показать единственность Л, мы
рассмотрим любой гомоморфизм hl N в jV,. Нетрудно видеть, что
подмножество В из N\Nlt такое, что <#, уУ?В тогда и только
тогда, когда y=zhxxt регулярно, и следовательно, А* С В. Из того,
что для каждого *?/V имеется только один y?Nx, такой, что
<*> ^/>€^' мы заключаем, что А* = В, а из этого легко следует, что
Л, = h. Этим замечанием мы закончим изложение схемы второго
доказательства теоремы I.
21

3. СЛОЖЕНИЕ И УМНОЖЕНИЕ В ПРОИЗВОЛЬНЫХ
ИНДУКЦИОННЫХ МОДЕЛЯХ
Как мы заметили раньше, из теоремы I следует сущест-
существование в каждой модели Пеан о единственной операции
сложения [т. е. бинарной операции /, которая удовлет-
удовлетворяет условиям E.1) и E.2) для всех х, y?N]. Факти-
Фактически справедливо нечто большее, а именно:
Теорема II. В каждой индукционной модели имеется
единственная операция сложения.
Доказательство этой теоремы нельзя базировать на тео-
теореме I, так как последняя, как это было показано в § 2,
имеет место не для всех индукционных моделей. Вместо
нее мы воспользуемся следующей леммой:
Лемма. Если <А/, О, S> — любая индукционная модель,
то для каждого x?N существует единственная унарная
операция hx на N, такая, что условия C.1) и C.2)
справедливы для всех у ?N.
Доказательство. Сначала заметим, что для любого
x?N может существовать самое большее одна операция
hx, удовлетворяющая условиям C.1) и C.2). Действительно,
предположим, что hx и h'x — две операции, удовлетворяю-
удовлетворяющие этим условиям, и допустим, что G—такое подмноже-
подмножество iV, что у ? G тогда и только тогда, когда hxy = hxy.
Ясно, что 0?G, так как hx0 = x = hx0. Кроме того, мно-
множество G замкнуто относительно S, так как если у ? О
(так что hxy = hxy), то h(Sy)=S(hxy) = S(hxy) = tix(Sy),
откуда следует, что Sy ? G. Так как аксиома РЗ справед-
справедлива для <iV, 0, 5>, мы заключаем, что G=N, а значит,
K=h'x.
Пусть теперь И—подмножество N, состоящее из тех
элементов х, для которых существует операция hx. Обо-
Обозначим через h0 тождественную операцию на N (т. е. та-
такую, что hQy=y для всех y?N). Мы видим, что hQ0 = 0
[таким образом, выполняется C.1)], и для любого у ? N
hQ(Sy)=Sy = S(hoy) [таким образом, выполняется C.2)].
Следовательно, 0 ? И. Далее, И замкнуто относитель-
относительно S. Действительно, положим х ? И, так что операция hx
существует. Пусть hSx есть такая операция на N,
что hSxy = S(hxy) для^ всех y?N; в таком случае
hSx0 = S(hx0) = Sx [следовательно, для Sx выполняется
22
C.1)]; в то же время для любого у?Ы
hsx (Sy) = 5 (hx (Sy)) = S (S (hxy)) = S (hsxy\
[следовательно, для 5л: выполняется C.2)]. Отсюда выте-
вытекает, что Sx ? Н. Применяя аксиому РЗ, которая по пред-
предположению справедлива для <ЛГ, 0, 5>, заключаем, 4tg
H=stNt что и доказывает лемму.
Используя эту лемму, мы можем завершить доказатель-
доказательство теоремы II точно таким же рассуждением, какое было
использовано ранее для вывода существования операции
сложения из теоремы I. Пусть читатель обратит внимание
на то, что в 21) мы использовали теорему I, чтобы полу-
получить утверждение, аналогичное настоящей лемме; как там
отмечено, конец рассуждения носит теоретико-множествен-
теоретико-множественный характер, не зависит от аксиом Р1—РЗ и поэтому
может применяться к индукционной модели теоремы II.
При рассмотрении умножения мы оказываемся в по-
положении, совершенно аналогичном тому, с которым мы
встретились здесь для сложения. Под операцией умноже-
умножения для индукционной модели <Л/, 0, Sy мы понимаем
такую бинарную операцию «•» на N, что при всех х, ^^А/
имеют место условия:
х- 0 = 0, A1.1)
;, A1.2)
здесь «-)-» означает операцию сложения для этой модели.
Используя доказательство, аналогичное данному выше
для теоремы II, мы можем показать, что в каждой индук~
ционной модели имеется одна и только одна операция
умножения *). Предоставляем читателю самому провести до-
доказательство.
4. ОПЕРАЦИИ В МОДЕЛЯХ ПЕАНО, ПОЛУЧАЕМЫЕ
ПУТЕМ ПРИМИТИВНОЙ РЕКУРСИИ^
Когда мы переходим к операции возведения в сте-
степень, положение меняется.
Под операцией возведения в степень для индукционной
модели <N, 0, *S> мы подразумеваем такую бинарную
1) Стр. 16.
*) Напомним, что модели Пеано являются частными случаями
1Укционных моделей. (Прим. ред.)
) Напомним, что модели Пеано я
индукционных моделей. (Прим. ред.)
23

Операцию ехр *), что для всех х, у QN имеют место условия
х ехр 0 ==50,
х ехр (ty) = (х ех
A2.1)
A2.2)
Здесь знак «•» означает операцию умножения для этой
модели. На этот раз не существует теоремы, аналогичной
теореме II, так что утверждение «для каждой индукцион-
индукционной модели существует операция возведения в степень»
просто неверно. Противоречащим примером является рас-
рассмотренная в 22) модель <ЛГ", а0
двух различных объектов а0
0 состоящая из
в которой N'" — {a0, аг}
) = al, Tal = a0. В самом деле, если бы ехр было би
. нарной операцией на N'", удовлетворяющей условиям A2.1)
и A2.2) для всех х, y?N'", то из A2.2) следовало бы, что
а0 ехрао = (аоехра1)-ао и поэтому а0 ехрао = ао в силу A1.1);
с другой стороны, из A2.1) следует а0 ехрао = Тао = аг.
Это противоречие показывает, что <ЛГ", а0, Ту не имеет
никакой операции возведения в степень.
Однако, применяя теорему I, мы можем показать, что
каждая модель Пеано имеет единственную операцию
возведения в степень. В самом деле, можно получить сле-
следующий более общий результат, из которого данное утверж-
утверждение выводится как частный случай:
Теорема III. Пусть <7V, 0, Sy — любая модель Пеано,
f — унарная операция на N и g—тернарная операция
на N г). Тогда существует одна и только одна бинарная
операция j на /V4), такая, что для всех х, у ? N выпол-
выполняются условия
A3.1)
' A3.2)
*) В привычных символах: х ехр у = ху. Условия A2.1) и A2.2)
представляют собой: лс° = 1 (если назвать число SO, следующее за
нулем, единицей) и ху + 1 = х/ -х. (Прим. ред.)
2) На стр. 18.
а) То есть сопоставляющая каждым трем элементам из N чет-
четвертый элемент из N. (Прим. ред.)
4) Oj этой функции / говорят, что она получена из / и g путем
примитивной рекурсии.
Вообще, /i-арную операцию / (при любом п = \, 2, . . .) можно
получить из (п—1)-арной операции / и (п -f- 1)-арной операции g
(случай /1 = 2 мы выбрали-только для краткости, так как идея до-
доказательства одна и та же при любом п).
24
В частном случае, когда / такая унарная операция на
Ny что fx = S0 для всех х ? /V, и g — такая тернарная
операция на N, что gxyz = z-x для всех л:, у, z, получен-
полученная функция у, очивидно, будет степенной1).
Доказательство. Как было замечено в процессе
доказательства теоремы II ), достаточно показать, что для
каждого х ? N существует единственная унарная операция
/х на jV, такая, что для всех у ? N
Jx0=/x, ¦• ' (H.1)
¦ A4.2)
показав это, мы сможем вывести теорему III из общего тео-
теоретико-множественного рассуждения, которое справедливо
для всех моделей (т. е. не использует ни одной из аксиом
Р1 — РЗ). Рассмотрим теперь множество ЛГ1 = <Л^Х ^> всех
упорядоченных пар <у, г>, где у, z? N: пусть 0х (где л;? /V
произвольно) есть элемент <0, fxy из Л^, a Sx — унарная
операция на Nv такая, что Sx <<y, zy = <Sy, gxyzy для всех
х, y?N. Применяя теорему I к модели Пеано </V, 0, Sy и
модели <iVj, 0x, Sx>, мы заключим, что для каждого x?N
имеется единственное отображение hx N в Nv такое, что ра-
равенства
hx(Sy)=Sx(hx у)
A5.2)
имеют место для всех y?N.
Далее, пусть L и R — такие два отображения Nt в /V,
что для всех х, y?N L <ху уУ=х и R<x, yy=y и jx
и kx (где x?N произвольно) — такие две унарные опера-
операции на N, что jxy = R(hxy) и kxy = L(hxy) для всех у g N.
Мы покажем, что при всех у ? N операция /х удовлетворяет
условиям A4.1) и A4.2). Для этого предварительно надо дока-
доказать, что kxy = y для всех y?N. Допустим, что G— подмно-
подмножество N, состоящее из тех элементов у, для которых kxy=y.
Так как kx0 = L(hx0)=zL0x = L<0, /*> = 0, to0?G.
Далее, пусть у — любой элемент G. Тогда, в силу A5.2),
S = L(Sx(hxy)). По определению Sx
1) Точнее, показательно-степенной функцией jxy = xy. Действи-
Действительно, A3.1) и A3.2) дают /лгО = SO (т. е. д;° = 1); jx(Sy) =
= gxy(jxy) = j (ху)-х (т. е. ху+1==ху-х). (Прим. ред.)
г) Стр. 23.

(hxy) = <S (L (hxy)), gx (L (hxy)) (R (hxy))y =
имеем:
так что kx(Sy) = L(Sx(hxy)) = S(kxy). Так как у ? G, то от-
сюда kx(Sy) = Sy, поэтому Sy ? G.
Таким образом, мы показали, что множество G замкнуто
относительной, итак как аксиома РЗ справедлива для <7V, 0,5>,
мы заключаем, что G=Ny т. е. kxy=y для всех y?N.
Возвращаясь снова к полученной формуле
мы видим, что теперь ее можно упростить следующим об-
образом:
Sx(hxy) = <Sy, gxy(jxy)y.
Так как jx(Sy) — R(hx (Sy)) = R(Sx (hxy)), мы сразу по-
получаем, что jx(Sy) = gxy(jxy)y а это показывает, что jx удо-
удовлетворяет условию A4.2).
С другой стороны, jx0 = R(hx0) = ROx—fx, так что jx
удовлетворяет также условию A4.1).
Чтобы закончить доказательство теоремы III, остается
показать, что jx является единственной унарной операцией
на N, которая удовлетворяет этим двум условиям; это рас-
рассуждение можно провести по той же схеме, с помощью ко-
которой мы вывели из теоремы I существование единственной
операции сложения для любой модели Пеано, — проверить
это мы предоставляем читателю.
б. ОТНОШЕНИЕ МЕЖДУ МОДЕЛЯМИ ПЕАНО
И ИНДУКЦИОННЫМИ МОДЕЛЯМИ
Почему операции сложения и умножения существуют
в каждой индукционной модели, в то время как опера-
операцию возведения в степень можно гарантировать
только для моделей Пеано? Чтобы ответить на этот вопрос,
мы должны сначала понять, какое отношение существует
между моделями Пеано и более общими индукционными
моделями. Оказывается, с алгебраической точки зрения это
отношение является очень простым и естественным.
Пусть <ЛГ = <ЛГ, 0, ?>и 0)V1 = <iV1, 0,, $.,> — две любые
модели. Говорят, что <М*Х есть голоморфный образ <ЛГ,'
за '
если существует гомоморфизм h модели Ж на модель <jfl9
т. е. функция /г, область определения которой есть N и
область значений — все множество Nv такая, что Л0 = 01
и h (Sx) = Sl (hx) для всех x?N.
Теорема IV. Пусть J\r = <iV, 0, Sy— модель Пеано
и c)\ri==<iV1, 0v Sx> — произвольная модель. Чтобы модель
<Af\ была гомоморфным образом <АГ, необходимо и доста-
достаточно, чтобы она являлась индукционной моделью.
Доказательство необходимости. Предполо-
Предположим, что сЛР,— гомоморфный образ gN\ и пусть h — гомо-
гомоморфизм off на о!\Г1. Пусть Gj — любое подмножество Л^,
такое, что 0 ? Gt и О1 замкнуто относительно Sv Чтобы
доказать, что сЛГ, является индукционной моделью, доста-
достаточно показать, что G1 = N1.
Для этой цели мы рассмотрим подмножество G из N,
содержащее те и только те элементы х, для которых
hx?Gv Так как Л0 = 01? то 0?G. Множество G замкнуто
относительно 5. Действительно, пусть x?G таково, что
hx?Gv Тогда S1(hx)?Giy так как G, замкнуто относи-
относительно Sx. Но h (Sx) = Sl (hx), так как отображение h есть
гомоморфизм. Таким образом, h (Sx) ? Gt и, значит, Sx?G;
следовательно, G замкнуто относительно S. Так как
<Л/, 0, 5> удовлетворяет аксиоме РЗ, то G=N. Это зна-
значит, что hx ? Gt для всех x?N. Из того, что область
определения h совпадает с N, а область значений — с Nv
мы заключаем, что G1 = Nl.
Доказательство достаточности. Предполо-
Предположим, что <Л/1? 0lf 5j> — индукционная модель. Так как
<^V, 0, Sy — модель Пеано, то мы можем применить тео-
теорему I, из которой следует, что существует (единственный)
гомоморфизм /г, преобразующий сЛГ в gN\. Чтобы закончить
доказательство, остается только показать, что область зна-
значений функции h охватывает все множество Nt.
Ясно, что область значений h содержит 01? так как
h0 = 0l. Она замкнута относительно Sv так как для
любого элемента z из области значений h должен сущест-
существовать элемент x?N, такой, что hx = z; отсюда следует,
что Slz = Sl(hx) = h(Sx), так что 5^ тоже принадлежит
области значений h. Но СЛГ1 удовлетворяет аксиоме РЗ;
следовательно, область значений h есть Nv что и требо-
требовалось доказать.
Из теоремы IV следует важное и хорошо известное
следствие:
"С
27

Теорема V. Любые две модели Пеано изоморфны1).
Доказательство. Пусть o!f и olV\ — две любые
модели Пеано. По теореме IV существует гомоморфизм А,
преобразующий оЛг* в Jft и гомоморфизм А,, преобразующий
сЛ'\ в g,V\ Ясно, что сложная функция (АХА), т. е. унарная
операция на N, определяемая для всех л;? N равенством
(hxh) x = Aj (hx) есть гомоморфизм o!f в оДГ. Но по теореме
I существует только один гомоморфизм <ЛГ в оДР, и очевидно,
что таким гомоморфизмом является тождественная операция
на оЛГ. Следовательно, (hth)x — x для всех x?N. Отсюда
легко следует, что А взаимно-однозначно, поэтому А есть
изоморфизм моделей оДР и сЛГ,.
Принципиальное значение теоремы состоит в следующем
метаматематическом 2) следствии:
Если взять какое-то обширное множество предложе-
предложений, содержащих символы «М>, «О» и «б1», то любое
предложение из этого множества, справедливое для одной
модели Пеано, будет справедливо также и для всякой
другой модели Пеано.
Таким образом, если предложение из этого множества
справедливо для некоторой частной модели Пеано, например
для системы <N*, О*, S*> натуральных чисел, известных
нам из интуиции, то оно будет справедливо и для всех
других моделей Пеано, а следовательно, будет являться
логическим следствием из аксиом Р1—РЗ. Множество пред-
предложений, к которому применим этот вывод, содержит все
те предложения о моделях, которыми мы интересуемся
в настоящей работе. Соответственно этому в дальнейшем,
вместо того чтобы говорить о произвольной модели Пеано,
мы можем говорить о системе <ЛР, О*, S*> натуральных
чисел.
В теореме II мы видели, что для каждой индукционной
модели q)\P = <jV, 0, ?> определена единственная операция
сложения «-J-». В свете теоремы IV, указывающей на
тесную связь модели N с системой натуральных чисел
с1\р*==<М*, 0*, 5*>, естественно исследовать отношение
между операцией «-j-» в <#' и операцией сложения «-[- *»
1) То есть существует гомоморфное отображение одной из них
на другую, являющееся взаимно-однозначным (изоморфное
отображение).
2) Метаматематика — название науки, содержащей общую
теорию доказательств (термин был введен Д. Гильбертом). См.
С. К. Клини, Введение в метаматематику, М„ 1957. (Прим. ред.)
28
в системе off*. Эта постановка вопроса приводит к следую-
следующему результату:
Теорема VI. Пусть off = <yv, 0, 5> — любая индук-
индукционная модель и « -\- » — ее операция сложения; пусть
h — однозначно определенный гомоморфизм, преобразую-
преобразующий <JV'* в off. Тогда для всех х,у ? /V* имеет место
свойство h(x-{-*y) = hx-{-hy.
Доказательство. Пусть х — любой элемент мно-
множества N* и G—такое подмножество ЛР, что y?G тогда
и только тогда, когда h(x-\-*y) = hx-\-hy. Так как
h(x + *O*) = hx = hx-{-O = hx-\-hO*, TQ o* g G. Далее,
пусть у — любой элемент G. Тогда h(x-\- *y) = hx-\- hyy
так что
А {х + *SV) = h (S*(x + *y))=S(h (x + *y))=S (hx + hy)=
= hx + S (hy) = Ax + A (S*j>),
а следовательно, S*y?G. Из замкнутости G относительно
5* в силу аксиомы РЗ (справедливой для JV'*) мы заклю-
заключаем, что G=N^y что и доказывает теорему.
В принятых в теории множеств и алгебре терминах
можно выразить содержание теоремы VI так: операция «-{-»
на N является (при гомоморфизме /г) образом операции
«-}-*» на N*. Соответствующая теорема для умножения
также справедлива и может быть доказана, по существу,
тем же способом. Хорошо известен следующий общий
результат, относящийся к общим алгебраическим системам:
Если уравнение тождественно удовлетворяется в одной
системе, то оно будет удовлетворяться в любом гомо-
гомоморфном образе системы (где каждая входящая в уравнение
операция первоначальной системы заменена операцией второй
системы, являющейся ее образом при этом гомоморфизме).
Отсюда следует, что такие тождества, как ассоциатив-
ассоциативный, коммутативный и дистрибутивный законы, справедливые
для операций «-|-*» и «•*» в системе о)\Р*, будут справед-
справедливы и для операций «-|-» и «•» в любой индукционной
модели.
Этот факт может быть выведен и непосредственно, без
использования какого-либо результата, справедливого для
общих алгебраических систем; рассмотрев обычный вывод
этих законов для моделей Пеано, получаемый из соотноше-
соотношений A.1), A.2), A1.1) и A1.2), мы обнаружили бы, что
используется только аксиома РЗ, в то время как ни Р1,
ни Р2 нигде не используются.
29

6. ОТНОШЕНИЯ КОНГРУЭНТНОСТИ \
Существует еще одно обстоятельство, касающееся гомо-
гомоморфизмов, которое хорошо известно для общих алгебраи-
алгебраических систем и может быть установлено непосредственно
для моделей, составляющих объект нашего исследования.
Это — тесная связь гомоморфизмов с отношением конгруэнт-
конгруэнтности. Под отношением конгруэнтности для модели
О)\Г = <Л/Г, 0, Sy подразумевается такое отношение эквива-
эквивалентности R на множестве N1), что из xRy следует
{Sx)R(Sy)*).
Пусть h — любой гомоморфизм модели оЛГ в некоторую
другую модель; тогда отношение Rh такое, что для любых
х, y?N мы имеем xRhy в том и только в том случае,
когда hx — hy является отношением конгруэнтности. Обратно
для каждого отношения конгруэнтности R в модели Jf су-
существует гомоморфизм Л, отображающий <ЛГ на некоторую дру-
другую модель JfR так, что Rh=R.
Чтобы по заданным модели <ЛР и отношению конгруэнт-
конгруэнтности R построить модель «ЛГR1 возьмем для каждого эле-
элемента х ? N все эквивалентные ему элементы: они образуют
некоторый «класс эквивалентности» xR. Множество этих
классов для всех х ? N примем в качестве множества NPi
') Отношение эквивалентности на множестве N — это такое
рефлексивное, симметричное и транзитивное бинарное отношение R,
для которого N является как областью определения, так и областью
значений. Для каждого такого отношения R существует разбиение
множества N на непересекающиеся подмножества, причем два
элемента принадлежат одному и тому же подмножеству тогда и
только тогда, когда эти элементы находятся в отношении R (это
весьма простое обстоятельство имеет чисто теоретико-множественный
характер). Подмножество, содержащее элемент х, называется мно-
множеством эквивалентности элемента х относительно R\ мы обозна-
обозначим его через xR. [Бинарное отношение xRy называется рефлексив-
рефлексивным, если имеет место xRx, симметричным, если из xRy следует
yRx, и транзитивным, если из xRy и yRz следует xRz. (Прим. ред.)]
') Приведем простой пример отношения конгруэнтности. Пусть
N— множество целых чисел, Sx — x-\-m (m — некоторое целое
число), а отношение xRy есть сравнимость х и у по модулю р
[язв у (mod р)}. Тогда 1) х =з х (mod p), 2) если xs= у (той р), то
у е= х (mod р), 3) если х яе у (mod р) и у г= z (mod p), то x = z (mod p),
и, наконец, 4) если x^y(modp), то и х + т — У + т, (mod p).
Следовательно, сравнимость двух чисел есть отношение конгру-
конгруэнтности. Этот пример бу^ет специально рассмотрен ниже; мы
увидим, что он является частным случаем более общего соотноше-
соотношения конгруэнтности в множестве натуральных чисел. (Прим, ред.)
30
а в качестве операции SR— такую, что SRxR = (Sx)R для
всех х ? N и х ? xR (существование этой операции следует
из того, что R — отношение конгруэнтности на Л/), и поло-
поло№ N 0 S
жим
0R, SRy.
м <№R <NR, R, SRy.
Если мы определим h как функцию, отображающую N на
h ?N лко у
x?N, то легко уви-
увии что Rhz=R (т. е.
NR и такую, что hx = xR для всех
дим, что h есть гомоморфизм Ж на сЛ
из xRy следует hx = hy и обратно).
Если hx и Нг — гомоморфизмы Ж соответственно на мо-
модели Жх и с)\Р2 и если Rhi=Rhn, то оМ\ и <ЛГ2 изоморфны.
Отсюда следует, что каждый гомоморфный образ модели
<ЛГ изоморфен одной из моделей cH*R, определенных (спосо-
(способом, описанным выше) некоторым отношением конгруэнтно-
конгруэнтности R на N.
Следовательно, на основании теорем IV и V каждая ин-
индукционная модель изоморфна модели о!\Г^, определенной
некоторым отношением конгруэнтности R в системе сЛг*
натуральных чисел.
Оказывается, мы можем дать явное описание всех
отношений конгруэнтности на модели о!\Г* в терминах хо-
хорошо известного отношения порядка — отношения «<j>
на off*1).
Именно, пусть т, п — любые элементы множества N*
натуральных чисел. Мы определим отношение конгруэнтно-
конгруэнтности Rm n на N* посредством следующего правила: xRm ny
тогда и только тогда, когда справедливо одно из следую-
следующих двух условий:
1) х, у<Сп и х = у;
2) ху у^п и для некоторого z?N* имеет место либо
х — у-\~* (z-*m), либо y — x-\-*{z-*m).
Теорема VII. Бинарное- отношение R на множестве
N* является отношением конгруэнтности в модели сЛГ*
тогда и только тогда, когда оно либо является отно~
шением тождества в о)\Г*, либо0 существуют числа
т, n?N*, такие, что R — Rm n.
f) Это отношение порядка можно ввести внутри аксиоматической
теории Ж* (т. е. в теории моделей Пеано), положив по определению,
что х < у тогда и только тогда, когда существует элемент г Ф 0, для
которого х -\- *z = у. Так как каждая индукционная модель обладает
функцией сложения, мы можем воспользоваться этим определением,
чтобы определить отношение « < » в каждой индукционной модели;
но в общем случае отношение, полученное таким образом, не будет
отношением порядка. ;* , ,.. .
31

Предоставляем доказательство этой теоремы читателю,
ограничась лишь следующими указаниями.
Если R— отношение конгруэнтности, отличное от отно-
отношения тождества, то должен существовать хотя бы один
x?N*, такой, что xRy для некоторого уфх. Выберем в
качестве п наименьшее из этих чисел х. Из выбора п
следует, что имеются числа z=?0, такие, что nR(n-\-*z)\
выберем т наименьшим из этих чисел z. Тогда можно
показать, что R=Rmn.
Отношения конгруэнтности Rm^ 0 являются так называе-
называемыми «конгруэнтностями по модулю», хорошо изученными
в теории чисел1). Индукционная модель d\P/?m,0> соответст-
соответствующая такому отношению, есть просто система классов
вычетов по модулю т, а операции сложения и умножения
в этой модели являются обычными операциями -|- (mod m) и
• (mod/w). Отношение конгруэнтности Rm,n для я^>0,
по-видимому, мало отражено в литературе2); однако доста-
достаточно небольшого размышления, чтобы читатель мог полу- •
чить ясное интуитивное представление о моделях cJ\P/?w, „, так
же как и о соответствующих операциях сложения и умно-
умножения.
Между прочим, очевидно, что если R — одно из «моду-
«модулярных» отношений конгруэнтности Rm 0, то S*r является
перестановкой элементов Nr, так что Mr в этом случае
удовлетворяет аксиоме Р2. С другой стороны, если R — одно
из отношений конгруэнтности Rm%n для я^>0, то ясно, что
0^=^=SRxp для всех xR?N#, так что Mr удовлетворяет
в этом случае аксиоме Р1. Таким образом, каждая индукци-
индукционная модель удовлетворяет Р1 или Р2, что уже отмеча-
отмечалось в 1.
Пусть/—любая операция на ЛГ*, для определенности —
бинарная операция. Если R есть произвольное отношение
конгруэнтности на М*> то, вообще говоря, не существует
ни одной бинарной операции g на Л^, которая является го-
гомоморфным образом / при гомоморфизме h, соответствующем
R. Нетрудно видеть, что необходимым и достаточным усло-
условием для существования такой гомоморфной операции g слу-
1) В теории чисел принято писать x^y(modm) вместо xRm^Qy.
[См. сноску *) на стр. 30. (Прим. ред.)]
2) Краткое упоминание о нем имеется в статье Н. S. Vandi-
ver, Bull. Amer. Math. Soc. 40 A934), стр. 914—920.
32
жйт то, что для всех x, л:,, у, .V^N*, таких, что xRx1
и yRyiy имеет место условие (fxy) RifxjJ. Если это усло-
условие справедливо, то g есть такая операция на Nr, что
SxRyp=(fxy)R для всех х, y,?N*.
Например, хотя 2 = 2 (mod 3) и 0 = 3(mod3), мы имеем
2° ^ 28 (mod 3). Следовательно, операция возведения в сте-
степень в N* не имеет гомоморфного образа в Л/#8|0. С дру-
другой стороны, -[-* и •* суть примеры так называемых уни-
универсальных (бинарных) операций на TV*, т. е. они являются
операциями /, обладающими тем свойством, что для лю-
любого отношения конгруэнтности R на N* (fxy)
если х, у, Xj, ух — такие элементы N*, что х/?х, и
Именно в силу этого обстоятельства каждая индукционная
модель обладает операциями сложения и умножения.
Предположим, что операция j на N* получена путем
примитивной рекурсии2) из универсальных операций /и g"8);
является ли эта операция j обязательно универсальной?
Пример операции возведения в степень показывает, что это
может не иметь места. Однако если j окажется коммута-
коммутативной, то она будет универсальной: это может быть^ по-
показано путем обобщения доказательства теоремы II. Таким
образом, вследствие некоммутативности операции возведения
в степень на множестве TV* натуральных чисел невозможно
вывести существование операции возведения в степень в
каждой индукционной модели путем соответствующего рас-
распространения доказательства теоремы II.
Конечно, при высказанных условиях коммутативность, до-
достаточная для универсальности, ни в коем случае не яв-
является необходимой. Например, операция у, такая, что
jxy = x2>y для всех х, y?N'*, есть универсальная опера-
операция, и она получается путем примитивной рекурсии из уни-
универсальных функций/, g", таких, что /х = 0 и gxyz = z-\-x2
для всех х, у, z.?N*, но j не коммутативна.
J) Мы можем называть / модулярной операцией, если она обладает
этим свойством для всех модулярных отношений конгруэнтности
R (и не обязательно для других отношений конгруэнтности). Инте-
Интересную характеризацию модулярных операций дал N. G. Bruijn
[см. Proc. Kon. Ned. Akad Wetenschap, Amsterdam, серия А, 58
(Indigationes Math. 17), 1955, стр. 363—367].
2) См. сноску 4) на стр. 24.
8) Ясно, что приведенное выше определение универсальных би-
бинарных операций без труда переносится и на случай п-арных опера-
операций, где п любое. (Прим. ред.)
33

7. ХАРАКТЕРИЗАЦИЯ МОДЕЛЕЙ ПЕАНО
В 2 мы видели, что основанием для определения по ма-
математической индукции в модели о)\Р является существование
единственного гомоморфизма о)\Г в какую-нибудь другую мо-
модель; таким образом, теорема I служит основанием всех
определений по математической индукции для моделей
Пеано.
Оказывается, это свойство характерно для моделей
Пеано — единственных моделей, в которых все опре-
определения по математической индукции могут быть обосно-
обоснованы.
Теорема VIII. Пусть qJ\T — такая модель, что для
любой модели JV^ имеется единственный гомомор-
гомоморфизм А, преобразующий модель Ж в сАГг Тогда Ж есть модель
Пеано.
Доказательство. Пусть о)\Р=<Л^ О, Sy удовлетво-
удовлетворяет условию теоремы. Мы покажем сначала, что Ж удов-
удовлетворяет аксиоме РЗ. С этой целью допустим, что G —
любое подмножество N, которое содержит 0 и замкнуто
относительно S. Пусть И—дополнение подмножества G
(в множестве N); допустим, что И непусто.
Рассмотрим взаимно однозначное отображение k множе-
множества И на множество* Р, не пересекающееся с TV, и обозна-
обозначим через М объединение множеств N и Р.
Определим унарную операцию Т на М следующим
образом:
1) если x?N, то Tx = Sx;
-, 2) если х?Н и Sx?H, то T{kx) = k(Sx);
3) если х?Н и Sx?G, то T(kx) = Sx.
Пусть оЖ — модель <Af, 0, Ту. Ясно, что отобра-
отображение h1 множества N в М, такое, что hlx = x для всех
x?N, является гомоморфизмом JV в оЛ. С другой сторо-
стороны, рассмотрим следующее отображение А2 множества
N в М:
1) если x?G, то h2x—x;
2) если х?Ну то hzx = kx.
Нетрудно видеть, что А2 также является гомоморфизмом
и А2 отлично от Аг Но это противоречит условию нашей
теоремы, и следовательно, не верно допущение, что И
непусто.
Итак, Н пусто, т. е. G=/V. Поэтому модель qJ\P должна
быть индукционной.
34
Из теоремы IV мы можем теперь заключить, что суще-
существует гомоморфизм А' модели сЛГ* на off. С другой стороны,
условие нашей теоремы утверждает, что имеется гомомор-
гомоморфизм А модели off в сЛГ*. Как и в доказательстве теоремы V,
мы рассмотрим сложную функцию (АА'), которая является
гомоморфизмом Ж* в себя и, следовательно (по теореме I),
должна быть тождественной операцией на <ЛГ*. Стало быть,
гомоморфизм К взаимно однозначен и поэтому является изо-
изоморфизмом сАГ* на X Это доказывает теорему.
Из теоремы VIII вытекает, что любое доказательство
теоремы I должно использовать все аксиомы Р1 — РЗ, как
и утверждалось в 2.
¦*:-

ЗАКЛЮЧЕНИЕ
Мы закончили обсуждение понятия определения по мате-
математической индукции в теории чисел, опирающееся на аксио-
аксиоматическое обоснование этой теории, данное Пеано. В ма-
математической литературе используются и другие типы ин-
индуктивных определений, например определения по трансфи-
нитной индукции или по индукции в некоторых типах час-
тично-упорядоченных систем. Многие из идей этой работы
можно обобщить, включив .и эти другие типы индукции.
Метод изложения материала в этой работе, может быть,
и претендует в некоторой степени на оригинальность, но
кое-какие из приведенных здесь доказательств хорошо из-
известны математикам. В особенности это касается двух дока-
доказательств теоремы I (одно из них изложено детально, а дру-
другое только намечено). Как указывает профессор А. Чёрч
(Alonzo Church), первое доказательство дано венгерским ма-
математиком Л. Кальмаром (L. Kalmar), идея же второго при-
принадлежит П. Лоренцену, а также Д. Гильберту и П. Бер-
найсу, которые получили это доказательство независимо друг
от друга и опубликовали свои работы почти одновременно 1).
Доказательство теоремы II принадлежит Е. Ландау2),
который приписывает его Л. Кальмару. Однако Ландау не
заметил значение того факта, что доказательство не исполь-
использует аксиом Р1 и Р2 3).
*) Статья Кальмара появилась в Acta Sci. Math. (Szeged) (9, № 4
A940), стр. 227—232), статья Лоренцена в Monatschr. Math, und
Phys. D7 A938—39), стр. 356—358), а доказательство Гильберта и Бер-
найса — в дополнении к т. 2 их книги «Grundlagen der Mathematik».
2) См. Э. Ландау, Основы анализа, ИЛ, 1947.
s) Только что я познакомился со статьей, некоторые идеи кото-
которой тесно связаны с,идеями этой работы: М. Lenz, Zur Mathema-
Mathematik der Zahlen, Acta Math. Acad. Sci. Hungar, 9 A958), стр.
33—44. [Примечание добавлено автором 2/Х 1958.— Ред.\