# Well-Founded Recursion

Jump to navigation
Jump to search

## Theorem

Let $A$ be a class.

Let $\mathcal R$ be a relation that is foundational on $A$.

Let every $\mathcal R$-initial segment of any element $x$ of $A$ be a small class.

Let $K$ be a class of mappings $f$ that satisfy:

- $(1): \quad$ The domain of $f$ is some subset $y \subseteq A$ such that $y$ is transitive with respect to $\mathcal R$.
- $(2): \quad \forall x \in y: f \left({x}\right) = G \left({F \restriction \mathcal R^{-1} x}\right)$

where $F \restriction R^{-1} x$ denotes the restriction of $F$ to the $\mathcal R$-initial segment of $x$.

Let $F = \bigcup K$, the union of $K$.

Then:

- $F$ is a mapping with domain $A$
- $\forall x \in A: F \left({x}\right) = G \left({F \restriction \mathcal R^{-1} x}\right)$
- $F$ is unique, in the sense that if another mapping $A$ has the above two properties, then $A = F$.

## Proof

## Sources

- 1971: Gaisi Takeuti and Wilson M. Zaring:
*Introduction to Axiomatic Set Theory*: $\S 9.7$