Шаг 3.
Основы языка Haskell. Индуктивные определения операций и предикатов, заданных на множествах слов. Рекурсивные определения функций

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

МетаОпределение (по [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.

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

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

Определение (по [3, с.146]).
Индуктивным определением  (или  построением) функции f(a) на множестве натуральных чисел называется её определение по следующим двум свойствам:
  1. Задано значение функции f(0)=x0 для числа 0.
  2. Значение функции f(a) для натурального числа a>0 однозначно выражено через ее значения f(b) для натуральных чисел b<a при помощи данных рекурсивных правил.
Теорема (о законности индуктивного определения) (по [3, с.146]).
При заданных рекурсивных правилах существует одна и только одна функция f(a), заданная на множестве всех натуральных чисел и обладающая свойствами (1) и (2), указанными в предыдущем определении.

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

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




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