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 question: Prime numbers out of sequence by Rubens373
Oct 7
new question: Lorenz system by David Bankom
Oct 19
new correction: examples and OEIS sequences by fizzie
Oct 13
new correction: Define Galois correspondence by porton
Oct 7
new correction: Closure properties on languages: DCFL not closed under reversal by babou
new correction: DCFLs are not closed under reversal by petey
Oct 2
new correction: Many corrections by Smarandache
Sep 28
new question: how to contest an entry? by zorba
new question: simple question by parag