Введение

Определение элементов множества через другие элементы этого множества

В математике и информатике рекурсивное определение, или индуктивное определение, используется для определения элементов множества в терминах других элементов этого множества (Aczel 1977:740ff). Примеры рекурсивно определяемых объектов включают факториалы, натуральные числа, числа Фибоначчи и канторово троичное множество. Рекурсивное определение функции определяет значения функции для некоторых аргументов через значения той же функции для других (обычно меньших) аргументов. Например, факториальная функция n! определяется следующими правилами:

Это определение верно для каждого натурального числа n, поскольку рекурсия в конечном итоге достигает базового случая 0. Определение также можно рассматривать как процедуру вычисления значения функции n!, начиная с 1 = 0! и продолжая для 1 = 1!, 2 = 2!, 3 = 3! и т. д. Теорема о рекурсии утверждает, что такое определение действительно определяет единственную функцию. Доказательство использует математическую индукцию. Индуктивное определение множества описывает элементы множества в терминах других элементов этого множества. Например, одно из определений множества \N натуральных чисел следующее:
1 принадлежит \N. Если элемент n принадлежит \N, то n + 1 принадлежит \N. \N – наименьшее множество, удовлетворяющее условиям (1) и (2). Существует множество множеств, удовлетворяющих условиям (1) и (2) – например, множество {1, 1.649, 2, 2.649, 3, 3.649, } удовлетворяет этому определению. Однако условие (3) определяет множество натуральных чисел, исключая множества с лишними элементами. Свойства рекурсивно определенных функций и множеств часто можно доказать с помощью принципа индукции, вытекающего из рекурсивного определения. Например, представленное здесь определение натуральных чисел непосредственно подразумевает принцип математической индукции для натуральных чисел: если свойство верно для натурального числа 0 (или 1), и если свойство верно для n + 1 всякий раз, когда оно верно для n, то свойство верно для всех натуральных чисел (Aczel 1977:742).

Форма рекурсивных определений

Большинство рекурсивных определений имеют две основы: базовый случай (базис) и индуктивное правило. Различие между циркулярным определением и рекурсивным определением состоит в том, что рекурсивное определение всегда должно иметь базовые случаи – случаи, удовлетворяющие определению, не будучи определенными через само это определение, – и что все остальные случаи в индуктивных правилах должны быть в некотором смысле "меньше" (то есть ближе к базовым случаям, завершающим рекурсию) – правило, также известное как "рекурсия только с более простым случаем". В отличие от этого, циркулярное определение может не иметь базового случая и даже может определять значение функции через само это значение, а не через другие значения функции. Такая ситуация приведет к бесконечному регрессу. Тот факт, что рекурсивные определения являются корректными – то есть, что рекурсивное определение определяет единственную функцию – является теоремой теории множеств, известной как теорема о рекурсии, доказательство которой нетривиально. Если область определения функции – натуральные числа, то достаточными условиями корректности определения являются задание значения f(0) (то есть базового случая) и наличие алгоритма для определения f(n) для n > 0 (то есть индуктивного правила) через n. В более общем случае рекурсивные определения функций могут быть построены, когда область определения является вполне упорядоченным множеством, используя принцип трансфинитной рекурсии. Формальные критерии корректности рекурсивного определения в общем случае более сложны. Описание общего доказательства и критериев можно найти в "Топологии" Джеймса Мункреса. Однако ниже будет представлен частный случай (область определения ограничена положительными целыми числами вместо любого вполне упорядоченного множества) общего рекурсивного определения.

Принцип рекурсивного определения

Пусть A — множество, а a₀ — элемент A. Если ρ — функция, которая сопоставляет каждой функции f, отображающей непустое подмножество натуральных чисел в A, элемент A, то существует единственная функция, такая, что