You are here
Hometransfinite recursion
Primary tabs
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 $\mathbf{On}$, the class of ordinals, such that
$F(\alpha)=G(F\alpha)$ 
where $F\alpha$ is the function whose domain is $\operatorname{seg}(\alpha):=\{\beta\mid\beta<\alpha\}$ and whose values coincide with $F$ on every $\beta\in\operatorname{seg}(\alpha)$. In other words, $F\alpha$ is the restriction of $F$ to $\operatorname{\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 $\varphi(x,y)$ be a formula such that
$\forall x\exists y\forall z(\varphi(x,z)\leftrightarrow z=y).$ 
Think of $G=\{(x,y)\mid\varphi(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. 2. $\forall x\forall y\Big(\mathbf{On}(x)\wedge\big(\psi(x,y)\leftrightarrow% \exists f(A\wedge B\wedge C\wedge D)\big)\Big)$, where

$A$ is the formula β$f$ is a functionβ,

$B$ is the formula β$\operatorname{dom}(f)=x$β,

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

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

A stronger form of the transfinite recursion theorem says:
Theorem 2.
Let $\varphi(x,y)$ be any formula (in the language of set theory). Then the following is a theorem: assume that $\varphi$ satisfies property that, for every $x$, there is a unique $y$ such that $\varphi(x,y)$. If $A$ be a wellordered set (wellordered by $\leq$), then there is a unique function $f$ defined on $A$ such that
$\varphi(f\operatorname{seg}(s),f(s))$ 
for every $s\in A$. Here, $\operatorname{seg}(s):=\{t\in A\mid t<s\}$, 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.
Mathematics Subject Classification
03E45 no label found03E10 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
Recent Activity
new problem: Geometry by parag
Aug 24
new question: Scheduling Algorithm by ncovella
new question: Scheduling Algorithm by ncovella