Editing Recursion (section)

===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: \N \to X</math> (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>
for any natural number {{mvar|n}}.

Dedekind was the first to pose the problem of unique definition of set-theoretical functions on <math>\mathbb N</math> by recursion, and gave a sketch of an argument in the 1888 essay "Was sind und was sollen die Zahlen?" <ref>A. Kanamori, "[https://math.bu.edu/people/aki/20.pdf In Praise of Replacement]", pp.50--52. Bulletin of Symbolic Logic, vol. 18, no. 1 (2012). Accessed 21 August 2023.</ref>

====Proof of uniqueness====
Take two functions <math>F: \N \to X</math> and <math>G: \N \to X</math> such that:

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

where {{mvar|a}} is an element of {{mvar|X}}.

It can be proved by [[mathematical induction]] that {{math|1=''F''(''n'') = ''G''(''n'')}} for all natural numbers 
{{mvar|n}}:

:'''Base Case''': {{math|1=''F''(0) = ''a'' = ''G''(0)}} so the equality holds for {{math|1=''n'' = 0}}.

:'''Inductive Step''': Suppose {{math|1=''F''(''k'') = ''G''(''k'')}} for some {{nowrap|<math>k \in \N</math>.}} Then {{math|1=''F''(''k'' + 1) = ''f''(''F''(''k'')) = ''f''(''G''(''k'')) = ''G''(''k'' + 1)}}.
::Hence {{math|1=''F''(''k'') = ''G''(''k'')}} implies {{math|1=''F''(''k'' + 1) = ''G''(''k'' + 1)}}.

By induction, {{math|1=''F''(''n'') = ''G''(''n'')}} for all <math>n \in \N</math>.