Well-Founded Recursion

From ProofWiki
Jump to: navigation, 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