Welcome guest
You're not logged in.
317 users online, thereof 0 logged in

Not only natural numbers, but also ordinal numbers are well-ordered. The usual recursion can be extended to ordinal numbers. However, functions defined like are only of theoretical interest, since they have only little to do with practical combinatorial problems like it was the case for usual recursive functions.

## Proposition: Transitive Recursion

Let $X$ be a set and let $\Omega$ be the proper class of all ordinals. A function $f:\mathbb \Omega\to X$ can be defined by specifying

1. the initial values of $f(\alpha)$ for all $\alpha \subseteq \omega$ and some ordinal number $\omega\in\mathbb\Omega,$ and
2. the recursion formula $f(\beta)=\mathcal R(f(\alpha)\mid \alpha \subset \beta)$ for all $\beta \supset \omega.$

| | | | | created: 2020-07-12 10:16:31 | modified: 2020-07-12 10:20:41 | by: bookofproofs | references: [8635]