von Julius Wilhelm Richard Dedekind im Jahr 1888 angegebener Satz, der besagt, daß es zu einer Menge A mit einem Element a ∈ A 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 k ∈ B. Damit kann man nicht nur einstellige Abbildungen auf ℕ, also Folgen, sondern auch mehrstellige Abbildungen definieren.