На этом шаге мы рассмотрим определения и задания таких функций.

МетаОпределение (по [1, с.43-44]).

Рекурсивными определениями (в математике) называются индуктивные определения операций и предикатов.

Определение (по [2, с.66]).

Если линейно упорядоченное множество A разбито на две (непересекающиеся) части B и C, причём любой элемент B меньше любого элемента C, то B называют начальным отрезком множества A.

Другими словами, подмножество B линейно упорядоченного множества A является начальным отрезком, если любой элемент B меньше любого элемента A\B.

Еще одна переформулировка: B ⊂ A является начальным отрезком, если из a,b ∈ A, b ∈ B и a ≤ b следует a ∈ B.

В частности, начальным отрезком вполне упорядоченного множества A является множество элементов A, меньших x (обозначается: [0,x)).

Пусть A - вполне упорядоченное множество. Мы хотим дать рекурсивное определение некоторой функции f: A → B, где B - некоторое множество. Такое определение должно связывать значение f(x) на некотором элементе x ∈ A со значениями f(y) при всех y<x.

Другими словами, рекурсивное определение задает f(x), предполагая известным ограничение функции f на начальный отрезок [0,x).

Вот точная формулировка.

Теорема (по [2, с.70]).

Пусть A - вполне упорядоченное множество, а B - произвольное множество. Пусть имеется некоторое рекурсивное правило, т.е. отображение F, которое ставит в соответствие элементу x ∈ A и функции g:[0,x) → B некоторый элемент множества B.

Обозначим f¦_[0,x) - ограничение функции f на начальный отрезок [0,x) - мы отбрасываем все значения функции на элементах, больших или равных x.

Тогда существует единственная функция f: A → B, для которой при всех x ∈ A.

Определение (по [3, с.146]).

Индуктивным определением (или построением) функции f(a) на множестве натуральных чисел называется её определение по следующим двум свойствам:

Задано значение функции f(0)=x₀ для числа 0.
Значение функции f(a) для натурального числа a>0 однозначно выражено через ее значения f(b) для натуральных чисел b<a при помощи данных рекурсивных правил.

Теорема (о законности индуктивного определения) (по [3, с.146]).

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

⁽¹⁾Марков А.А., Нагорный Н.М. Теория алгорифмов.- М.: ФАЗИС, 1996.- 496 с.
⁽²⁾Н.К.Верещагин, А.Шень. Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств. 2-е изд., исправленное. М.:МЦНМО, 2002. - 128 с.
⁽³⁾Энциклопедия элементарной математики. Кн.1. - М.-Л.: ГИТТЛ, 1951. - 448 с.

На следующем шаге мы рассмотрим принцип трансфинитной индукции.

Предыдущий шаг Содержание Следующий шаг