Множество K будем называть индуктивным, если для него выполняются равенства (I) и (II).

ГЛАВА III. НАТУРАЛЬНЫЕ ЧИСЛА. КОНЕЧНЫЕ И БЕСКОНЕЧНЫЕ МНОЖЕСТВА.

В этой главе мы исходим из системы аксиом ∑º, причём, как обычно теоремы, не помеченные символом º, можно доказать без аксиомы выбора VI.

Натуральные числа.

Для каждого множества X обозначим

Множество X' называется последователем множества X.

Теорема 1. Существует единое семейство K множеств N, обладающие следующими свойствами:

I.

II.

III. Если K удовлетворяет I и II, то

Множество K будем называть индуктивным, если для него выполняются равенства (I) и (II).

Д о к а з а т е л ь с т в о.Из аксиомы бесконечности (IV) следует, что существует по крайней мере одно семейство R, обладающее свойствами (I) и (II). Пусть Ф – семейство всех тех подмножеств семейства R, которые обладают свойствами (I) и (II):

Легко проверить, что P(Ф) является искомым семейством K. Элементами множества N будут множества 0, {0}, {0, {0}}, … Можно считать, что эти множества играют роль натуральных чисел 0, 1, 2, 3,.. , а роль операции +1 играет операция '.

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

Для упрощения символики будем в дальнейшем обозначать элементы семейства N буквами m, n, p, …

Прежде всего докажем, что

                                                               (1)

Пусть  Достаточно показать, что  т.е. что множество K индуктивно. Условие (I) выполняется очевидно.

Чтобы доказать (II), возьмём  и . Тогда  или  В 1-ом случае  по определению множества K, а во 2-ом случае  в силу равенства этих множеств. Следовательно, , значит,  и формула (1) доказана.

Доказательства такого вида называют доказательствами по индукции.

Далее                (2).

Доказательство (2) проводится по индукции; оно основано на том, что множество  индуктивно

                                                      (3)

В самом деле,  и значит,  или , откуда согласно (1),  Аналогично доказывается обратное включение.

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

a) нуль является натуральным числом;

b) каждое натуральное число имеет последовательность;

c) нуль не является последователем никакого натурального числа;

d) числа, имеющие одинаковые последователи, равны;

e) множество, содержащее нуль и вместе с каждым число его последователь, содержит все натуральные числа.

Из формул (I), (II), (3), (III) и  следует, что элементы множества N удовлетворяют всем аксиомам Пеано.

Для произвольных m, n выполняется одна и только одна из               (4)

Д о к а з а т е л ь с т в о. Из (1) и (2) следует, что любые две из этих зависимостей исключают друг друга. Чтобы доказать, что для каждой пары m, n одна из этих зависимостей выполняется, применим индукцию. Обозначим

Утверждение (4) равносильно утверждению , поэтому достаточно показать, что множество K(n) для любого n индуктивно.

Множество K(0) индуктивно, т.к. K(0) состоит из множества 0 и тех m, для которых  и .

Пусть K(n) индуктивно, т.е. . Покажем, что K(n') также индуктивно. Из  следует, что .

Т.к. первые два члена этой дизъюнкции ложны, то , следовательно,  Условие (I) индуктивности множества выполнено.

Проверим условие (II). Пусть  т.е. выполняется один из случаев

Во 2-м и 3-м случае очевидно, что  и, значит,

В 1-м случае:

· или  тогда  и, значит,

· или  тогда  и

поскольку по предположению множество  индуктивно.

Отсюда получаем  3-й член этой дизъюнкции можно отбросить, т.к. он вместе с  даёт  что противоречит (2). Таким образом, остаются только возможности  и

Учитывая, что  получаем в обоих случаях  и утверждение (4) доказано.

Множество   совпадает с произведением    всех семейств  удовлетворяющих условию (II) и содержащих . (5)

Д о к а з а т е л ь с т в о. Множество  удовлетворяет условию (II), т.к.  Из этого следует, что  поскольку  Остаётся показать, что если K удовлетворяет условию (II) и  то

Рассмотрим для этого множество  Достаточно показать, что  т.е. что Z индуктивно. Условие (I) с очевидностью выполняется, т.к.

Чтобы доказать, что Z удовлетворяет условию (II), возьмем элемент    

Тогда:

1)

2)

В 1-м случае  поскольку  удовлетворяет условию (II) и, значит,  2-й случай, согласно (4), распадается на 3 подслучая в соответствии с зависимостями  и  1-й подслучай противоречит условию   2-й подслучай даёт  и, значит,  откуда  т.к.  Наконец, в последнем случае, согласно (4),  Если верны 1-й и 2-й члены этой дизъюнкции, то опять же по (4)  поэтому  и  Последний член дизъюнкции ведет к противоречию, т.к. из него следует, что  в то время как по условию

В арифметике множество чисел, больших данного числа n, определяется как общая часть всех множеств, содержащих последовательность числа n и вместе с каждым числом b содержащих его последовательность.

Утверждение (5) показывает, что отношение принадлежности в множестве  соответствует отношению «меньше» между натуральными числами. Поэтому вместо  и  мы будем часто писать  и  соответственно.

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

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

Очевидно, что множеством всех бесконечных последовательностей, члены которых принадлежат множеству A, будет AN; множеством всех конечных последовательностей с  членами будет AN. Множество всех конечных последовательностей с членами из A можно определить так:

× (R – функция)

Из этого определения следует, что такое множество существует.

Определения по индукции.

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

a)  где  а функция, отображающая в , ( ).

b)

Это определение по индукции с параметром  пробегающим множество

Схемы (a) и (b) соответствуют переходу от «  к », т.е. значение  (или  зависит от значения  (или . Значение  может зависеть от всех значений , где  (т.е. .

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

c)

d)

В схеме (c)  и  где  - множество конечных последовательностей с членами из

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

Примеры определения по индукции.

Пример 1. Функция сложения

Это определение попадает под схему (b), где  и

Пример 2. Функция  

Это определение попадает под схему (a), где

Пример 3. Пусть в схеме (b)  Тогда

Функцию  будет обозначать  и называть -й итерацией функции  (Итерация – повторное ( -е) использование одного и того же).

Таким образом,

Пример 4. Пусть  и пусть в схеме (b):

Тогда  

Функция  определённая по такой схеме, обозначается  Аналогично определяется  и т.п.

Очевидно, что схема (d) наиболее общая из всех упомянутых здесь схем. Это означает, что при подходящем выборе функций  и  можно получить из (d) любую из схем (a), (b), (c). Например, возьмём в качестве функцию, определённую равенством:

 для  Получим из (d) схему (b).

Покажем теперь, что схему (d) в свою очередь можно свести к схеме (a). Пусть  и  - функции, принадлежащие соответственно  и  и пусть -функция, удовлетворяющая схеме (d). Покажем, что последовательность , заданную формулой  можно определить по схеме (a).

Очевидно, что  для каждого  Первый член последовательности  равен  т.е. множеству:

.

Связь между  и  задаётся формулой:

причём

Отсюда видно, что последовательность  можно определить схемой (a), заменяя в этой схеме  на , элемент  множеством  и полагая

 для

Теперь докажем существование и единственность функции, удовлетворяющей равенствам (a). Такая теория позволяет нам пользоваться определениями по индукции по схеме (a). Согласно сделанному выше замечанию, отсюда будет следовать существование функций, удовлетворяющих равенствам (b), (c), (d). Единственность этих функций доказывается так же, как и для схемы (a), и в дальнейшем мы будем пользоваться определениями по индукции по любой из схем (a)-(d).

Теорема 1. Если  - произвольное множество,  и , то существует одна и только одна последовательность , удовлетворяющая равенствам (a).

Д о к а з а т е л ь с т в о. Единственность. Пусть равенствам (a) удовлетворяют две последовательности  и . Рассмотрим множество . Из (a) следует, что множество K индуктивно, поэтому и .

Существование. Пусть - высказывательная функция , a - высказывательная функция вида:

(F есть функция)&

Другими словами, -функция, определённая на множестве чисел , для которой  и  для всех .

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

В качестве  возьмём множество таких пар , что ,  и .

Т.к. - единственная функция, удовлетворяющая , то  будет функцией. Для  имеем .

Если , то , по определению функции , откуда .

Часто определяются по индукции не одна, а одновременно несколько функций (со значениями из одного и того же множества ), например:

где ; .

Такое определение также сводится к предыдущим определениями. Достаточно заметить, что для последовательности .

Справедливы формулы:

, ,

где , а  и  - такие функции, что  для .

Таким образом, функция  определена индуктивно по схеме (a). Определим теперь функции  и  равенствами , . Теорему об определениях по индукции можно обобщить на случай операций. Ограничится только одним частным случаем. Пусть - такая высказывательная функция, что

,

.

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

Д о к а з а т е л ь с т в о. Единственность доказывается так же, как в теореме 1. Для доказательства существования  рассмотрим высказывательную функцию:

(F есть функция)

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

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

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

§3. Отображение множества N N на N и связанные с ним отображения.

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

1. Отображение множества  на .

Положим для .

.

Теорема 1. Функция  взаимно однозначно отображает множество  на .

Д о к а з а т е л ь с т в о. Пусть . Покажем сначала, что . Если бы было , т.е. , , то мы имели бы

                                                               (1)

Откуда следовало бы, что , т.к. - возрастающая функция. Значит, , где . Подставив в (1) и обозначив , мы получили бы

Но это невозможно, т.к. , и, значит,

Аналогично доказывается, что не может быть . Значит, , и тогда

Предположение , т.е. , , ведет к противоречию

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

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

Если , то .

Если , то . Для  это выражение можно переписать в виде . И, значит, снова . Наконец, если , то  и , так что и здесь . Теорема 1 доказана.

Теорема 2. Существуют функции , отображающие  на , для которых . Эти функции удовлетворяют неравенствам

                                                                   (2)

Д о к а з а т е л ь с т в о. Существование функций  и  следует из теоремы 7 (гл. II, §6) и неравенства (2) выполняются, т.к. , .

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

                                                    N_{столбца}=Z(n)+1

            N_строки                           (3)