Recursion: Difference between revisions

Revision as of 23:34, 9 November 2023

Revision as of 00:21, 10 November 2023

Line 121:

===The recursion theorem===

In [[set theory]], this is a theorem guaranteeing that recursively defined functions exist. Given a set {{mvar|X}}, an element {{mvar|a}} of {{mvar|X}} and a function {{math|''f'': ''X'' → ''X''}}, the theorem states that there is a unique function {{<math|''>F'': <math>\N \to X</math> → ''X''}} (where <math>\N</math> denotes the set of natural numbers including zero) such that

:<math>F(0) = a</math>

:<math>F(n + 1) = f(F(n))</math>