transfinite recursion
Transfinite recursion, roughly speaking, is a statement about the ability to define a function recursively using transfinite induction^{}. In its most general and intuitive form, it says
Theorem 1.
Let $G$ be a (class) function on $V$, the class of all sets. Then there exists a unique (class) function $F$ on $\mathrm{On}$, the class of ordinals^{}, such that
$$F(\alpha )=G(F\alpha )$$ 
where $F\mathrm{}\alpha $ is the function whose domain is $$ and whose values coincide with $F$ on every $\beta \mathrm{\in}\mathrm{seg}\mathit{}\mathrm{(}\alpha \mathrm{)}$. In other words, $F\mathrm{}\alpha $ is the restriction^{} of $F$ to $\alpha $.
Notice that the theorem above is not provable in ZF set theory^{}, as $G$ and $F$ are both classes, not sets. In order to prove this statement, one way of getting around this difficulty is to convert both $G$ and $F$ into formulas^{}, and modify the statement, as follows:
Let $\phi (x,y)$ be a formula such that
$$\forall x\exists y\forall z(\phi (x,z)\leftrightarrow z=y).$$ 
Think of $G=\{(x,y)\mid \phi (x,y)\}$. Then there is a unique formula $\psi (\alpha ,z)$ (think of $F$ as $\{(\alpha ,z)\mid \psi (\alpha ,z)\}$) such that the following two sentences^{} are derivable^{} using ZF axioms:

1.
$\forall x\exists y\forall z(\mathrm{\mathbf{O}\mathbf{n}}(x)\wedge (\psi (x,z)\leftrightarrow z=y)),$ where $\mathrm{\mathbf{O}\mathbf{n}}(x)$ means “$x$ is an ordinal”,

2.
$\forall x\forall y(\mathrm{\mathbf{O}\mathbf{n}}(x)\wedge (\psi (x,y)\leftrightarrow \exists f(A\wedge B\wedge C\wedge D)))$, where

–
$A$ is the formula “$f$ is a function”,

–
$B$ is the formula “$\mathrm{dom}(f)=x$”,

–
$C$ is the formula $\forall z(z\in x\wedge \phi (fz,f(z)))$, and

–
$D$ is the formula $\phi (f,y)$.

–
A stronger form of the transfinite recursion theorem says:
Theorem 2.
Let $\phi \mathit{}\mathrm{(}x\mathrm{,}y\mathrm{)}$ be any formula (in the language^{} of set theory). Then the following is a theorem: assume that $\phi $ satisfies property that, for every $x$, there is a unique $y$ such that $\phi \mathit{}\mathrm{(}x\mathrm{,}y\mathrm{)}$. If $A$ be a wellordered set (wellordered by $\mathrm{\le}$), then there is a unique function $f$ defined on $A$ such that
$$\phi (f\mathrm{seg}(s),f(s))$$ 
for every $s\mathrm{\in}A$. Here, $$, the initial segment of $s$ in $A$.
The above theorem is actually a collection^{} of theorems, or known as a theorem schema, where each theorem corresponds to a formula. The other difference between this and the previous theorem is that this theorem is provable in ZF, because the domain of the function $f$ is now a set.
Title  transfinite recursion 

Canonical name  TransfiniteRecursion 
Date of creation  20130322 17:53:51 
Last modified on  20130322 17:53:51 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  12 
Author  CWoo (3771) 
Entry type  Theorem 
Classification  msc 03E45 
Classification  msc 03E10 
Related topic  WellFoundedRecursion 
Related topic  TransfiniteInduction 