Direkt zum Inhalt

Lexikon der Mathematik: Rekursionssatz

von Julius Wilhelm Richard Dedekind im Jahr 1888 angegebener Satz, der besagt, daß es zu einer Menge A mit einem Element aA und einer Abbildung \(\varphi :{\mathbb{N}}\times A\to A\) genau eine Abbildung \(f:{\mathbb{N}}\to A\) mit \begin{eqnarray}\begin{array}{rcl}f(1) & = &a\\ f(n+1) & = &\varphi (n,f(n))\,\,\,\,(n\in {\mathbb{N}})\end{array}\end{eqnarray} gibt.

Dieser recht einleuchtende Satz, zu beweisen mittels vollständiger Induktion, ist Grundlage der Definition durch Rekursion. Als Verallgemeinerung hat man die Rekursion mit Parametern: Zu Mengen A, B mit Abbildungen a : B → A und \(\varphi :B\times {\mathbb{N}}\times A\to A\) gibt es genau eine Abbildung \(f:B\times {\mathbb{N}}\to A\) mit \begin{eqnarray}\begin{array}{rcl}f(k,1) & = & a(k)\\ f(k,n+1) & = & \varphi (k,n,f(k,n))\,\,\,\,\,(n\in {\mathbb{N}})\end{array}\end{eqnarray} für alle kB. Damit kann man nicht nur einstellige Abbildungen auf ℕ, also Folgen, sondern auch mehrstellige Abbildungen definieren.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos