Definicja rekurencyjna - Recursive definition

Cztery etapy budowy płatka śniegu Kocha . Podobnie jak w przypadku wielu innych fraktali , etapy są uzyskiwane poprzez definicję rekurencyjną.

W matematyce i informatyce , a rekurencyjnej definicji lub definicji indukcyjnej , jest używany do określenia elementów w A zestawu w odniesieniu do innych elementów w zestawie ( Aczél 1977: 740ff). Niektóre przykłady rekurencyjnie definiowanych przedmiotów obejmują silnię , liczby naturalne , liczby Fibonacciego , oraz zbiór Cantora trójskładnikowego .

Rekurencyjne definicji z funkcji określa wartości funkcji dla wejścia w pewnych warunkach wartości tej samej funkcji, o innych (zwykle mniejszy) nakładów. Na przykład funkcja silnia n ! jest określony przez zasady

0! = 1.

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

Ta definicja jest ważna dla każdej liczby naturalnej n , ponieważ rekursja ostatecznie osiąga podstawowy przypadek 0. Definicja może być również traktowana jako dająca procedurę obliczania wartości funkcji n !, Zaczynając od n = 0 i kontynuując dalej gdzie n = 1, n = 2, n = 3 itd.

Twierdzenie o rekurencji stwierdza, że taka definicja rzeczywiście definiuje unikalną funkcję. Dowód wykorzystuje indukcję matematyczną .

Indukcyjna definicja zbioru opisuje elementy w zestawie pod względem innych elementów w zestawie. Na przykład, jeden zestaw definicji N z liczb naturalnych jest:

1 w N .
Jeżeli element n w N a następnie n + 1 jest N .
N jest przecięciem wszystkich zbiorów spełniających (1) i (2).

Jest wiele zbiorów spełniających (1) i (2) - na przykład zbiór {1, 1.649, 2, 2.649, 3, 3.649, ...} spełnia definicję. Jednak warunek (3) określa zbiór liczb naturalnych, usuwając zbiory z obcymi elementami. Zauważ, że ta definicja zakłada, że N jest zawarte w większym zbiorze (takim jak zbiór liczb rzeczywistych) - w którym operacja + jest zdefiniowana.

Właściwości rekurencyjnie zdefiniowanych funkcji i zbiorów można często udowodnić za pomocą zasady indukcji, która jest zgodna z definicją rekurencyjną. Na przykład, definicja liczb naturalnych przedstawiona tutaj bezpośrednio implikuje zasadę indukcji matematycznej dla liczb naturalnych: jeśli własność ma liczbę naturalną 0 (lub 1), a własność ma n + 1, ilekroć ma n , wówczas własność wszystkich liczb naturalnych (Aczel 1977: 742).

Forma definicji rekurencyjnych

Większość definicji rekurencyjnych ma dwie podstawy: przypadek bazowy (podstawa) i klauzulę indukcyjną.

Różnica między definicją cykliczną a definicją rekurencyjną polega na tym, że definicja rekurencyjna musi zawsze mieć przypadki bazowe, przypadki , które spełniają definicję, ale nie są zdefiniowane w kategoriach samej definicji, oraz że wszystkie inne wystąpienia w klauzulach indukcyjnych muszą być „mniejsze” w pewnym sensie (tj. bliżej tych przypadków bazowych, które kończą rekursję) - reguła znana również jako „powtarzaj tylko w prostszym przypadku”.

W przeciwieństwie do tego definicja cykliczna może nie mieć przypadku bazowego, a nawet może definiować wartość funkcji w kategoriach samej tej wartości - zamiast na podstawie innych wartości funkcji. Taka sytuacja doprowadziłaby do nieskończonego regresu .

Że definicje rekurencyjne są poprawne - co oznacza, że definicja rekurencyjna identyfikuje unikalną funkcję - jest twierdzeniem teorii mnogości znanym jako twierdzenie o rekurencji , którego dowód jest nietrywialny. Tam, gdzie dziedziną funkcji są liczby naturalne, wystarczające warunki, aby definicja była ważna, są takie, że podano wartość $f (0)$ (tj. Przypadek bazowy), a dla $n > 0$ podano algorytm do wyznaczania $f (n)$ pod względem $n, f (0), f (1),\dots, f (n - 1)$ (tj. klauzula indukcyjna).

Mówiąc bardziej ogólnie, rekurencyjne definicje funkcji można tworzyć zawsze, gdy dziedzina jest zbiorem dobrze uporządkowanym , stosując zasadę rekursji pozaskończonej . Formalne kryteria określające prawidłową definicję rekurencyjną są bardziej złożone dla przypadku ogólnego. Zarys ogólny dowodu i kryteriów można znaleźć w James Munkres ' topologii . Jednak szczególny przypadek (dziedzina jest ograniczona do dodatnich liczb całkowitych zamiast dowolnego dobrze uporządkowanego zbioru) ogólnej definicji rekurencyjnej zostanie podany poniżej.

Zasada definicji rekurencyjnej

Niech będzie zbiorem i niech $0$ stanowić element $A$ . Jeśli $ρ$ jest funkcją, która przypisuje każdej funkcji $f$ mapując niepustą sekcję liczb całkowitych dodatnich na $A$ , element $A$ , to istnieje unikalna funkcja taka, że ${\ displaystyle h: \ mathbb {Z} _ {+} \ do A}$

{\ displaystyle h (1) = a_ {0}}

{\ Displaystyle h (i) = \ rho (h | _ {\ {1,2, \ ldots, i-1 \}}) {\ tekst {dla}} ja> 1.}

Przykłady definicji rekurencyjnych

Podstawowe funkcje

Dodawanie jest definiowane rekurencyjnie na podstawie liczenia jako

{\ displaystyle 0 + a = a,}

{\ Displaystyle (1 + n) + a = 1 + (n + a).}

Mnożenie jest definiowane rekurencyjnie jako

{\ displaystyle 0a = 0,}

{\ Displaystyle (1 + n) a = a + na.}

Potęgowanie jest definiowane rekurencyjnie jako

{\ displaystyle a ^ {0} = 1,}

{\ Displaystyle a ^ {1 + n} = aa ^ {n}.}

Współczynniki dwumianowe można zdefiniować rekurencyjnie jako

{\ displaystyle {\ binom {a} {0}} = 1,}

{\ Displaystyle {\ binom {1 + a} {1 + n}} = {\ Frac {(1 + a) {\ binom {a} {n}}} {1 + n}}.}

liczby pierwsze

Zbiór liczb pierwszych można zdefiniować jako unikalny zbiór dodatnich liczb całkowitych spełniających

1 nie jest liczbą pierwszą,
każda inna dodatnia liczba całkowita jest liczbą pierwszą wtedy i tylko wtedy, gdy nie jest podzielna przez żadną liczbę pierwszą mniejszą od siebie.

Pierwotność liczby całkowitej 1 jest przypadkiem podstawowym; sprawdzenie pierwotności dowolnej większej liczby całkowitej X według tej definicji wymaga znajomości pierwotności każdej liczby całkowitej między 1 a X , co jest dobrze zdefiniowane w tej definicji. Ten ostatni punkt można udowodnić za pomocą indukcji na X , dla którego istotne jest, aby druga klauzula mówiła „wtedy i tylko wtedy”; gdyby powiedział tylko „jeśli” pierwotność na przykład 4 nie byłaby jasna, a dalsze stosowanie drugiej klauzuli byłoby niemożliwe.

Nieujemne liczby parzyste

Te numery nawet może być zdefiniowany jako składający się z

0 znajduje się w zbiorze E nieujemnych zdarzeń parzystych (klauzula podstawowa),
Dla dowolnego elementu x ze zbioru E , x + 2 jest w E (klauzula indukcyjna),
Nic nie jest w E, chyba że zostało uzyskane z podstawy i klauzul indukcyjnych (klauzula ekstremalna).

Dobrze sformułowane formuły

Definicje rekurencyjne znajdują się głównie w logice lub programowaniu komputerowym. Na przykład dobrze sformułowany wzór (wff) można zdefiniować jako:

symbol oznaczający propozycję - podobnie jak p oznacza „Connor jest prawnikiem”.
Symbol negacji, po którym następuje wff - jak Np, oznacza „Nie jest prawdą, że Connor jest prawnikiem”.
Dowolny z czterech binarnych łączników ( C , A , K lub E ), po których następują dwa wffs. Symbol K oznacza „oba są prawdziwe”, więc Kpq może oznaczać „Connor jest prawnikiem, a Mary lubi muzykę”.

Wartość takiej rekurencyjnej definicji polega na tym, że można jej użyć do określenia, czy dany ciąg symboli jest „dobrze sformułowany”.

Kpq jest dobrze uformowane, ponieważ jest to K, po którym następują atomowe wffs p i q .
NKpq jest dobrze sformułowane, ponieważ występuje po nim N, po którym następuje Kpq , co z kolei jest wff.
KNpNq to K, po którym następuje Np i Nq ; a Np to wff itp.

Zobacz też

Uwagi

Bibliografia

Halmos, Paul (1960). Naiwna teoria mnogości . van Nostrand . OCLC 802530334 .
Aczel, Peter (1977). „Wprowadzenie do definicji indukcyjnych”. W Barwise, J. (red.). Podręcznik logiki matematycznej . Studia z logiki i podstaw matematyki. 90 . Północna Holandia . pp. 739–782. doi : 10.1016 / S0049-237X (08) 71120-0 . ISBN 0-444-86388-5 .
Hein, James L. (2010). Struktury dyskretne, logika i obliczalność . Jones & Bartlett . ISBN 978-0-7637-7206-2 . OCLC 636352297 .

Languages

In other projects