Fonction de Veblen

Une suite fondamentale pour un ordinal limite (de cofinalité ω, mais c'est toujours le cas pour les ordinaux dénombrables de cet article) est une suite strictement croissante ayant cet ordinal comme limite. La donnée d'un système de suites fondamentales pour tous les ordinaux limites inférieurs à un ordinal donné α permet de construire une bijection explicite (n'utilisant en particulier pas l'axiome du choix) entre ω et α. Les suites fondamentales qui vont être décrites couvrent les ordinaux atteints par la hiérarchie de Veblen, et allant jusqu'à l'ordinal de Feferman-Schütte. Le n-ième élément de la suite fondamentale choisie pour α sera noté α[n].

Une forme analogue à la forme normale de Cantor utilisée dans ce contexte consiste à écrire tout ordinal non nul α sous la forme (unique) ${\displaystyle \alpha =\varphi _{\beta _{1}}(\gamma _{1})+\varphi _{\beta _{2}}(\gamma _{2})+\cdots +\varphi _{\beta _{k}}(\gamma _{k})}$, où k > 0 est un entier naturel, la suite des termes est décroissante (non nécessairement strictement) : ${\displaystyle \varphi _{\beta _{m}}(\gamma _{m})\geq \varphi _{\beta _{m+1}}(\gamma _{m+1})\,,}$ et où chaque ${\displaystyle \gamma _{m}<\varphi _{\beta _{m}}(\gamma _{m})\,.}$ Si une suite fondamentale existe pour le dernier terme, on pourra réécrire celui-ci, obtenant une suite fondamentale pour α : ${\displaystyle \alpha [n]=\varphi _{\beta _{1}}(\gamma _{1})+\cdots +\varphi _{\beta _{k-1}}(\gamma _{k-1})+(\varphi _{\beta _{k}}(\gamma _{k})[n])\,.}$

Pour tout β, si γ est un ordinal limite avec ${\displaystyle \gamma <\varphi _{\beta }(\gamma )\,,}$ alors on pose ${\displaystyle \varphi _{\beta }(\gamma )[n]=\varphi _{\beta }(\gamma [n])\,.}$

Bien entendu, il n'y a pas de suite fondamentale pour ${\displaystyle \varphi _{0}(0)}$ = ω⁰ = 1 ; pour ${\displaystyle \varphi _{0}(\gamma +1)=\omega ^{\gamma +1}=\omega ^{\gamma }\cdot \omega \,,}$ on pose ${\displaystyle \varphi _{0}(\gamma +1)[n]=\varphi _{0}(\gamma )\cdot n=\omega ^{\gamma }\cdot n\,.}$

Pour ${\displaystyle \varphi _{\beta +1}(0)\,,}$ on prend ${\displaystyle \varphi _{\beta +1}(0)[0]=0\,}$ et ${\displaystyle \varphi _{\beta +1}(0)[n+1]=\varphi _{\beta }(\varphi _{\beta +1}(0)[n])\,,}$ autrement dit la suite 0, ${\displaystyle \varphi _{\beta }(0)}$,${\displaystyle \varphi _{\beta }(\varphi _{\beta }(0))}$, etc.

Pour ${\displaystyle \varphi _{\beta +1}(\gamma +1)}$, on prend ${\displaystyle \varphi _{\beta +1}(\gamma +1)[0]=\varphi _{\beta +1}(\gamma )+1\,}$ et ${\displaystyle \varphi _{\beta +1}(\gamma +1)[n+1]=\varphi _{\beta }(\varphi _{\beta +1}(\gamma +1)[n])\,.}$

Supposons alors que β soit un ordinal limite : si ${\displaystyle \beta <\varphi _{\beta }(0)}$, on pose ${\displaystyle \varphi _{\beta }(0)[n]=\varphi _{\beta [n]}(0)\,.}$

Pour ${\displaystyle \varphi _{\beta }(\gamma +1)}$, on prend ${\displaystyle \varphi _{\beta }(\gamma +1)[n]=\varphi _{\beta [n]}(\varphi _{\beta }(\gamma )+1)\,.}$

Sinon, l'ordinal ne peut être décrit à l'aide d'ordinaux plus petits et des fonctions ${\displaystyle \varphi }$, et cette méthode ne s'applique pas : c'est ce qui se produit à partir de l'ordinal de Feferman-Schütte.

La fonction Γ énumère les ordinaux α pour lesquels la méthode précédente ne s'applique pas, c'est-à-dire ceux pour lesquels ${\displaystyle \varphi _{\alpha }(0)=\alpha }$. Γ₀ est l'ordinal de Feferman-Schütte, donc le plus petit α tel que ${\displaystyle \varphi _{\alpha }(0)=\alpha }$.

Pour Γ₀, on peut prendre comme séquence fondamentale ${\displaystyle \Gamma _{0}[0]=0\,}$ et ${\displaystyle \Gamma _{0}[n+1]=\varphi _{\Gamma _{0}[n]}(0)\,.}$

Pour Γ_β+1, on prend ${\displaystyle \Gamma _{\beta +1}[0]=\Gamma _{\beta }+1\,}$ et ${\displaystyle \Gamma _{\beta +1}[n+1]=\varphi _{\Gamma _{\beta +1}[n]}(0)\,.}$

Enfin, pour Γ_β, où ${\displaystyle \beta <\Gamma _{\beta }\,}$ est un ordinal limite, on prend ${\displaystyle \Gamma _{\beta }[n]=\Gamma _{\beta [n]}\,.}$. À nouveau, on ne peut continuer au-delà du premier ordinal tel que ${\displaystyle \beta =\Gamma _{\beta }\,}$, et il faudrait créer une nouvelle fonction ; le processus, répété transfiniment, conduit au petit ordinal de Veblen (en).