# 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. 1.

$\forall x\exists y\forall z\big{(}\mathbf{On}(x)\wedge(\psi(x,z)% \leftrightarrow z=y)\big{)},$ where $\mathbf{On}(x)$ means “$x$ is an ordinal”,

2. 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(f|z,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 well-ordered set (well-ordered 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, 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 TransfiniteRecursion 2013-03-22 17:53:51 2013-03-22 17:53:51 CWoo (3771) CWoo (3771) 12 CWoo (3771) Theorem msc 03E45 msc 03E10 WellFoundedRecursion TransfiniteInduction