## You are here

Homewell-founded recursion

## Primary tabs

# well-founded recursion

###### Theorem 1.

Let $G$ be a binary (class) function on $V$, the class of all sets. Let $A$ be a well-founded set (with $R$ the well-founded relation). Then there is a unique function $F$ such that

$F(x)=G(x,F|\operatorname{seg}(x)),$ |

where $\operatorname{seg}(x):=\{y\in A\mid yRx\}$, the initial segment of $x$.

Remark. Since every well-ordered set is well-founded, the well-founded recursion theorem is a generalization of the transfinite recursion theorem. Notice that the $G$ here is a function in two arguments, and that it is necessary to specify the element $x$ in the first argument (in contrast with the $G$ in the transfinite recursion theorem), since it is possible that $\operatorname{seg}(a)=\operatorname{seg}(b)$ for $a\neq b$ in a well-founded set.

Related:

TransfiniteRecursion

Type of Math Object:

Theorem

Major Section:

Reference

Parent:

Groups audience:

## Mathematics Subject Classification

03E10*no label found*03E45

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections