Content deleted Content added
m *recursively defined sets |
*statement of the recursion theorem |
||
Line 1:
'''Recursion''' is a way of specifying a process by means of itself. More precisely (and to dispel the appearance of circularity in the definition), "complicated" instances of the process are defined in terms of "simpler" instances, and the "simplest" instances are given explicitly.
Examples of mathematical objects often defined recursively are functions and sets.
Line 19:
= 6
In [[set theory]] there is a theorem guaranteeing that such functions exist.
''[A statement and proof of the recursion theorem from set theory is needed]''▼
'''The recursion theorem.''' Given a set ''X'', an element ''a'' of ''X'' and a function ''f'':''X''->''X'', then there is a unique function ''F'':'''N'''->''X'' such that
:''F''(0)=''a'', and
:''F''(''n''+1)=''f''(''F''(''n'')).
The canonical example of a recursively defined set is the [[natural numbers]]:
| |||