|
|
|
|
transfinite recursion
|
(Theorem)
|
|
|
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 CWoo.
|
|
(view preamble | get metadata)
Cross-references: difference, collection, initial segment, well-ordered set, property, satisfies, language, stronger, axioms, derivable, sentences, formulas, order, set theory, ZF, theorem, restriction, domain, class of ordinals, class, transfinite induction, function
There are 7 references to this entry.
This is version 9 of transfinite recursion, born on 2008-03-11, modified 2008-03-16.
Object id is 10387, canonical name is TransfiniteRecursion.
Accessed 1466 times total.
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) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
