\(\DeclarePairedDelimiterX{\Set}[2]{\{}{\}}{#1 \nonscript\;\delimsize\vert\nonscript\; #2}\) \( \DeclarePairedDelimiter{\set}{\{}{\}}\) \( \DeclarePairedDelimiter{\parens}{\left(}{\right)}\) \(\DeclarePairedDelimiterX{\innerproduct}[1]{\langle}{\rangle}{#1}\) \(\newcommand{\ip}[1]{\innerproduct{#1}}\) \(\newcommand{\bmat}[1]{\left[\hspace{2.0pt}\begin{matrix}#1\end{matrix}\hspace{2.0pt}\right]}\) \(\newcommand{\barray}[1]{\left[\hspace{2.0pt}\begin{matrix}#1\end{matrix}\hspace{2.0pt}\right]}\) \(\newcommand{\mat}[1]{\begin{matrix}#1\end{matrix}}\) \(\newcommand{\pmat}[1]{\begin{pmatrix}#1\end{pmatrix}}\) \(\newcommand{\mathword}[1]{\mathop{\textup{#1}}}\)
Peano Axioms
Needed by:
Natural Sums
Sheet PDF
Graph PDF

Recursion Theorem


It is natural to want to define a sequence by giving its first term and then giving its later terms as functions of its earlier ones. In other words, we want to define sequences inductively.1

Let $X$ be a set, let $a \in X$ and let $f: X \to X$. There exists a unique function $u$ so that $u(0) = a$ and $u(\ssuc{n}) = f(u(n))$.2
When one uses the recursion theorem to assert the existence of a function with the desired properties, it is called definition by induction.
  1. Future editions will expand on this. We are really headed toward natural addition, multiplication and exponentiation. ↩︎
  2. The account is somewhat straightforward, given a good understanding of the results of  Peano Axioms. The full account will appear in future editions. ↩︎
Copyright © 2023 The Bourbaki Authors — All rights reserved — Version 13a6779cc About Show the old page view