EDB — 08Z

[08Z]

Let \(A\) be a non-empty set; suppose that \(a∈ A\) is fixed, and functions \(g_ n:A→ A\) are given, one for each \(n∈ℕ\). Then there exists an unique function \(f:ℕ→ A\) such that

• \(f(0)=a\), and

• for every \(n∈ℕ\) we have \(f(S(n))=g_ n(f(n))\).

We will say that the function \(f\) is defined by recurrence by the two previous conditions.

More generally given \(g_ n:A^{n+1}→ A\), an unique function \(f:ℕ→ A\) exists, such that \(f(0)=a\) and for every \(n∈ℕ\) \(f(S(n))=g_ n(f(0),f(1),\ldots f(n))\).