Рекурсивне означення

Чотири стадії побудови сніжинки Коха. Як і для багатьох інших фракталів, стадії задаються рекурсивним означенням.

Рекурсивне означення (також індуктивне означення) у математичній логіці та інформатиці — задання елементів множин через інші елементи цієї ж множини (Aczel 1978:740).

Рекурсивне означення функції встановлює результат функції для деяких параметрів через її ж результат для інших параметрів. Наприклад, функція факторіала n! визначається наступними правилами:

0! = 1.

(n+1)! = (n+1)·n!.

Дане означення дійсне для всіх n, через те, що в процесі рекурсії врешті-решт досягається початковий варіант 0. Означення можна також розуміти як опис процедури, що визначає функцію n!, починаючи з n = 0 і прогресуючи далі для n = 1, n = 2, n = 3, і т.д.

Теорема рекурсії стверджує, що таке означення насправді задає функцію. Доведення ґрунтується на методі математичної індукції.

Індуктивне означення множини описує її елементи через інші елементи. Наприклад, означення множини натуральних чисел N:

1. 1 належить N.
2. Якщо елемент n належить N, то n+1 також належить N.
3. N — об'єднання попарних перетинів всіх множин, що задовольняють умовам (1) і (2).

Можна сконструювати багато множин, що задовольняють (1) і (2) — наприклад, множина {1, 1.649, 2, 2.649, 3, 3.649, ...}. Однак саме умова (3) визначає множину натуральних чисел, видаляючи всі підмножини, що містять ненатуральні числа.

Властивості рекурсивно-означених функцій і множин часто можна вивести з принципу математичної індукції (який слідує рекурсивному означенню). Наприклад, означення натуральних чисел наведене вище напряму містить принцип індукції для натуральних чисел: якщо властивість чинна для натурального числа 0, і властивість чинна для n+1 кожного разу, коли вона чинна для n, тоді властивість чинна для всіх натуральних чисел (Aczel 1978:742).

Види рекурсивних означень

Більшість рекурсивних означень у своїй основі мають два елементи: початкове значення (базис, Шаблон:Lang-en) і індуктивне твердження. Наявність базису — основна відмінність рекурсивного означення від кругового: базис (або кілька базисів) дає означення функції без звернення до самої функції (тобто, без рекурсії). На противагу, кругове (або циркулярне, Шаблон:Lang-en) означення часто не має базису, і задає значення функції через те саме значення (замість інших значень) цієї функції. Дана ситуація приводить до нескінченної регресії.

Чинність рекурсивного означення (іншими словами, твердження, що рекурсивне означення задає унікальну функцію) є теоремою у теорії множин, доказ якої нетривіальний. Коли областю визначення функції є натуральні числа, достатніми умовами для чинності означення є наявність значення $f(0)$ (базис), і наявність алгоритму, що для всіх n>0 задає $f(n)$ у термінах $n,f(0),f(1),...,f(n-1)$ (індуктивне твердження).

Див. також

• Рекурсивні типи даних
• Рекурсія
• Математична індукція
• Непредикативність (математика)

Джерела

• Paul Halmos: Naive set theory, van Nostrand, 1960
• P. Aczel (1977), "An introduction to inductive definitions", Handbook of Mathematical Logic, J. Barwise (ed.), Шаблон:Isbn.
• James L. Hein (2009), Discrete Structures, Logic, and Computability. Шаблон:Isbn.