Transfinite recursion theorem

In mathematics, the transfinite recursion theorem says a function can be defined using a recursion over a well-ordered set; for example,

N

{\displaystyle \mathbb {N} }

but also over general well-ordered sets.

Since each well-ordered set is isomorphic to an ordinal, the theorem is also often stated in terms of ordinals.

Statements

Transfinite recursion is an instance of transfinite induction and the latter works over a well-ordered set (in fact, the feasibility of such an induction is equivalent to well-ordered-ness). In particular, the theorem can be stated for well-ordered sets. If

A

{\displaystyle A}

is a partially ordered set, we write

A

a

=

{

b

∈

A

∣

b

<

a

}

.

{\displaystyle A^{a}=\{b\in A\mid b<a\}.}

The transfinite recursion theorem is also commonly stated for ordinals. One simple version is: let a set

X

{\displaystyle X}

and a class function

G

{\displaystyle G}

with values in

X

{\displaystyle X}

defined on the class of all functions be given. Then, for each ordinal

α

{\displaystyle \alpha }

, there exists a unique function

f

:

α

→

X

{\displaystyle f:\alpha \to X}

such that, for every ordinal

β

<

α

{\displaystyle \beta <\alpha }

; that is,

β

∈

α

{\displaystyle \beta \in \alpha }

or

β

⊊

α

{\displaystyle \beta \subsetneq \alpha }

,

f

(

β

)

=

G

(

f

|

β

)

{\displaystyle f(\beta )=G(f|_{\beta })}

.

Since an ordinal is a well-ordered set, the above version follows from the well-ordered version (as

β

=

α

β

{\displaystyle \beta =\alpha ^{\beta }}

). Although it is common to ask

G

{\displaystyle G}

to be defined for all functions, this is just a convenient way of stating the theorem.