This is a place holder for potential sponsor logos.

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):=\lbrace \beta\mid \beta<\alpha\rbrace$ 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=\lbrace (x,y)\mid \varphi(x,y)\rbrace$ . Then there is a unique formula $\psi(\alpha,z)$ (think of $F$ as $\lbrace (\alpha,z)\mid \psi(\alpha,z)\rbrace$ ) such that the following two sentences are derivable using ZF axioms:

$\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'',
$\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 $\le$ ), 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):=\lbrace t\in A\mid t<s\rbrace$ , 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.

transfinite recursion is owned by Chi Woo.

How to Cite This Entry

Chi Woo. "transfinite recursion" (version 9). PlanetMath.org. Freely available at http://planetmath.org/TransfiniteRecursion.html.

Classification

AMS MSC:	03E10 (Mathematical logic and foundations :: Set theory :: Ordinal and cardinal numbers)
	03E45 (Mathematical logic and foundations :: Set theory :: Inner models, including constructibility, ordinal definability, and core models)

Username:
Password:

Register
I've forgotten my login details

transfinite recursion

How to Cite This Entry

Classification

Tags

Pending Errata and Addenda

Interact

Discussion

Login

transfinite recursion

How to Cite This Entry

Classification

Tags

Pending Errata and Addenda

Interact

Discussion