Функция следования¶

Функция следования (англ. successor function) — в математике, теории множеств и математической логике одна из базовых арифметических функций, которая каждому натуральному числу \( n \) ставит в соответствие непосредственно следующее за ним число \( n+1 \). Функция следования является фундаментальным понятием при аксиоматическом построении арифметики, в частности в системе аксиом Пеано, где она служит основой для определения всех натуральных чисел и операций сложения и умножения.

¶Определение и обозначение

Функция следования обычно обозначается латинской буквой \( S \) (от англ. successor) или символом \( \prime \) (штрих). В аксиоматике Пеано она определяется как отображение \( S: \mathbb{N} \to \mathbb{N} \), удовлетворяющее следующим условиям:

• \( S(n) \neq 0 \) для любого \( n \in \mathbb{N} \) (нуль не является последователем никакого числа);
• Если \( S(n) = S(m) \), то \( n = m \) (инъективность функции);
• Аксиома индукции: если некоторое свойство выполняется для нуля и для каждого числа, для которого оно выполняется, выполняется и для его последователя, то оно выполняется для всех натуральных чисел.

В десятичной системе счисления значение функции следования для числа \( n \) записывается как \( n+1 \). Например, \( S(0) = 1 \), \( S(1) = 2 \), \( S(5) = 6 \).

¶История

Понятие «следования» восходит к античным представлениям о натуральном ряде как о последовательности, порождаемой повторением операции прибавления единицы. Однако строгое формальное определение функции следования было введено лишь в конце XIX века в рамках программы обоснования математики. Итальянский математик Джузеппе Пеано в 1889 году в работе «Арифметические принципы, изложенные новым методом» (лат. Arithmetices principia, nova methodo exposita) сформулировал аксиомы натуральных чисел, центральное место в которых заняла функция следования. Пеано использовал символ \( +1 \) для обозначения операции перехода к следующему числу, а впоследствии — штрих \( \prime \).

В начале XX века функция следования стала ключевым объектом в теории рекурсивных функций. Американский математик Алонзо Чёрч в 1930-х годах в рамках лямбда-исчисления определил функцию следования как комбинатор, позволяющий строить натуральные числа (так называемые «числа Чёрча»). В советской математической школе, в частности в работах Андрея Николаевича Колмогорова и его учеников, функция следования рассматривалась как одна из базовых примитивно рекурсивных функций, наряду с нулём и проекцией.

¶Свойства

Функция следования обладает рядом фундаментальных свойств, вытекающих из аксиом Пеано:

• Инъективность: если \( S(a) = S(b) \), то \( a = b \). Это означает, что у разных чисел не может быть одного и того же последователя.
• Сюрьективность на множество положительных чисел: каждое натуральное число, кроме нуля, является последователем некоторого числа. Формально: \( \forall n \in \mathbb{N} \setminus \{0\} \; \exists m \in \mathbb{N} : S(m) = n \).
• Неподвижные точки: функция следования не имеет неподвижных точек, то есть не существует такого \( n \in \mathbb{N} \), что \( S(n) = n \).
• Коммутативность с операцией сложения: \( S(n) + m = S(n + m) \). Это свойство используется при рекурсивном определении сложения.
• Итерация: \( n \)-кратное применение функции следования к нулю даёт число \( n \): \( S(S(\ldots S(0)\ldots)) = n \) (где \( S \) применена \( n \) раз).

¶Роль в аксиоматике Пеано

Аксиомы Пеано (PA) представляют собой формальную систему, описывающую натуральные числа. Функция следования является единственной неопределяемой операцией в этой системе. Аксиомы Пеано включают:

1. \( 0 \in \mathbb{N} \).
2. Если \( n \in \mathbb{N} \), то \( S(n) \in \mathbb{N} \).
3. \( \forall n \in \mathbb{N} : S(n) \neq 0 \).
4. \( \forall n, m \in \mathbb{N} : (S(n) = S(m)) \Rightarrow (n = m) \).
5. Аксиома индукции (схема аксиом).

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

• \( n + 0 = n \);
• \( n + S(m) = S(n + m) \).

Умножение определяется аналогично:

• \( n \cdot 0 = 0 \);
• \( n \cdot S(m) = (n \cdot m) + n \).

¶Функция следования в теории рекурсивных функций

В теории рекурсивных функций функция следования рассматривается как одна из трёх базовых примитивно рекурсивных функций (наряду с нулём и проекцией). Она обозначается как \( s(x) = x + 1 \). Из неё и других базовых функций путём композиции и примитивной рекурсии строятся все арифметические функции, включая сложение, умножение, возведение в степень и факториал.

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

¶Функция следования в информатике

В программировании функция следования часто используется в рекурсивных алгоритмах, связанных с натуральными числами. Например, в функциональных языках программирования (Haskell, Lisp, Scheme) натуральные числа могут быть представлены в виде «чисел Чёрча», где функция следования определяется как лямбда-выражение:

\[ \text{succ} = \lambda n. \lambda f. \lambda x. f (n f x) \]

В этом представлении число \( n \) — это функция, которая применяет \( f \) к \( x \) \( n \) раз. Функция следования добавляет ещё одно применение \( f \).

В языках с поддержкой рекурсии (например, Python, C++) функция следования может быть реализована тривиально: def succ(n): return n + 1. Однако в контексте формальной верификации программ и доказательства корректности (например, в системе Coq) функция следования задаётся аксиоматически как конструктор индуктивного типа nat.

¶Функция следования в теории множеств

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

• \( 0 = \varnothing \);
• \( 1 = \{\varnothing\} \);
• \( 2 = \{\varnothing, \{\varnothing\}\} \);
• \( n+1 = n \cup \{n\} \).

В этой конструкции функция следования \( S(n) = n \cup \{n\} \). Она строго возрастает по включению: \( n \subset S(n) \). Каждое натуральное число есть множество всех предыдущих чисел.

¶Обобщения

Понятие функции следования может быть обобщено на другие множества, имеющие структуру линейного порядка с выделенным наименьшим элементом. Например, в теории ординалов функция следования определяется для каждого ординала \( \alpha \) как \( S(\alpha) = \alpha + 1 \). Для предельных ординалов (например, \( \omega \)) функция следования не определена, так как они не имеют непосредственного предшественника.

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

¶Критика и ограничения

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

¶Источники

• Пеано, Джузеппе. Arithmetices principia, nova methodo exposita (1889).
• Мендельсон, Эллиот. Введение в математическую логику. — М.: Наука, 1976.
• Колмогоров, А. Н., Драгалин, А. Г. Математическая логика. — М.: УРСС, 2005.
• Черч, Алонзо. Введение в математическую логику. — М.: ИЛ, 1960.
• Эндертон, Герберт. Элементы теории множеств. — М.: Мир, 1977.