Fonction de Veblen

Fonction de Veblen

En mathématiques, et plus précisément en théorie des ensembles, les fonctions de Veblen forment une suite de fonctions définies sur les ordinaux, introduite en 1908 par Oswald Veblen.

Sommaire

Les fonctions de Veblen

Soit f une fonction normale (en) définie sur les ordinaux, c'est-à-dire une fonction continue pour la topologie de l'ordre, strictement croissante. En 1908, Oswald Veblen a montré[1] qu'on pouvait construire une suite de fonctions indexée par les ordinaux, toutes normales, définie comme suit : φ0 =f, et pour tout ordinal non nul α, φα est la fonction qui énumère les points fixes communs à tous les φβ pour β<α[2].

La hiérarchie de Veblen

Dans le cas particulier où φ0(α)=ωα, la famille des fonctions de Veblen est connue sous le nom de hiérarchie de Veblen.

La fonction φ1 est alors la fonction ε : φ1(α)= εα. Ainsi, \phi_1(0)=\varepsilon(0)=\omega^{\omega^{\omega^\dots}}. Si \alpha < \beta \,, alors \phi_{\alpha}(\phi_{\beta}(\gamma)) = \phi_{\beta}(\gamma) \,. Cela, et le fait que φβ est strictement croissante, entraîne que l'on a l'ordre : \phi_\alpha(\beta) < \phi_\gamma(\delta) \, si et seulement si (\alpha = \gamma \, et \beta < \delta \,), ou (\alpha < \gamma \, et \beta < \phi_\gamma(\delta) \,) ou (\alpha > \gamma \, et \phi_\alpha(\beta) < \delta \,).

Suites fondamentales pour la hiérarchie de Veblen

Une suite fondamentale pour un ordinal limite (de cofinalité (en) ω, 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) \alpha = \phi_{\beta_1}(\gamma_1) + \phi_{\beta_2}(\gamma_2) + \cdots + \phi_{\beta_k}(\gamma_k), où k>0 est un entier naturel, la suite des termes est décroissante (non nécessairement strictement) : \phi_{\beta_m}(\gamma_m) \geq \phi_{\beta_{m+1}}(\gamma_{m+1}) \,, et où chaque \gamma_m < \phi_{\beta_m}(\gamma_m) \,. Si une suite fondamentale existe pour le dernier terme, on pourra réécrire celui-ci, obtenant une suite fondamentale pour α : \alpha [n] = \phi_{\beta_1}(\gamma_1) + \cdots + \phi_{\beta_{k-1}}(\gamma_{k-1}) + (\phi_{\beta_k}(\gamma_k) [n]) \,.

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

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

Pour \phi_{\beta+1}(0) \,, on prend \phi_{\beta+1}(0) [0] = 0 \, et \phi_{\beta+1}(0) [n+1] = \phi_{\beta}(\phi_{\beta+1}(0) [n]) \,, autrement dit la suite 0, ϕβ(0),ϕβ(ϕβ(0)), etc..

Pour ϕβ + 1(γ + 1), on prend \phi_{\beta+1}(\gamma+1) [0] = \phi_{\beta+1}(\gamma)+1 \, et \phi_{\beta+1}(\gamma+1) [n+1] = \phi_{\beta} (\phi_{\beta+1}(\gamma+1) [n]) \,.

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

Pour ϕβ(γ + 1), on prend \phi_{\beta}(\gamma+1) [n] = \phi_{\beta [n]}(\phi_{\beta}(\gamma)+1) \,.

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

La fonction Γ

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

Pour Γ0, on peut prendre comme séquence fondamentale \Gamma_0 [0] = 0 \, et \Gamma_0 [n+1] = \phi_{\Gamma_0 [n]} (0) \,.

Pour Γβ+1, on prend \Gamma_{\beta+1} [0] = \Gamma_{\beta} + 1 \, et \Gamma_{\beta+1} [n+1] = \phi_{\Gamma_{\beta+1} [n]} (0) \,.

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

Généralisations

Pour pouvoir généraliser ces notations, il est plus simple de considérer φα(β) comme une fonction φ(α,β) de deux variables. Veblen a montré comment en déduire une fonction à plusieurs variables φ(αn,αn-1, ...,α0), et plus généralement il a montré comment φ peut être défini même pour une suite transfinie d'ordinaux αβ, à condition que seuls un nombre fini d'entre eux soient non nuls.

Notes

  1. ↑ Veblen 1908
  2. ↑ La démonstration de ce résultat, et de tous ceux mentionnés dans cet article, se trouve dans Veblen 1908 ; pour une approche rigoureuse, mais plus intuitive, on pourra consulter, par exemple, ce texte de Xavier Caruso [PDF]. Le point-clé de la plupart de ces démonstrations est que si β est un ordinal quelconque, la suite β, f(β), f(f(β)),... a pour limite un ordinal supérieur à β, et qui est un point fixe de f.

Références

  • Xavier Caruso, Bons ordres sur N[PDF], article introductif en français.
  • (en) Hilbert Levitz, Transfinite Ordinals and Their Notations: For The Uninitiated, article introductif (8 pages, en PostScript)
  • (en) Wolfram Pohlers, Proof theory, vol. 1407, Springer-Verlag, 1989 (ISBN 3-540-51842-8) 
  • (en) Kurt Schütte, Proof theory, vol. 225, Springer-Verlag, 1977 (ISBN 3-540-07911-4), p. xii+299 
  • (en) Gaisi Takeuti, Proof theory, vol. 81, North-Holland Publishing Co., 1987 (ISBN 0-444-87943-9) 
  • (en) C. Smorynski, The varieties of arboreal experience, vol. 4, 1982 [lire en ligne], p. 182–189  [PDF] : une description informelle de la hiérarchie de Veblen.
  • (en) Oswald Veblen, « Continuous Increasing Functions of Finite and Transfinite Ordinals », dans Transactions of the American Mathematical Society, vol. 9, no 3, 1908, p. 280–292 [texte intégral]  [PDF]
  • (en) Larry W. Miller, « Normal Functions and Constructive Ordinal Notations », dans The Journal of Symbolic Logic, vol. 41, no 2, 1976, p. 439–459 [lien DOI] 

Voir aussi




Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Fonction de Veblen de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • VEBLEN (T.) — VEBLEN THORSTEIN (1857 1929) Né aux États Unis de parents norvégiens immigrés, Thorstein Bunde Veblen a enseigné, après avoir passé un doctorat de philosophie à Yale en 1884, dans plusieurs universités américaines (Chicago, Stanford, Missouri).… …   Encyclopédie Universelle

  • Courbe de Jordan — Théorème de Jordan La courbe de Jordan (en noir) divise le plan en deux régions : un « intérieur » (en bleu) et un « extérieur » (en rose). Ce résultat porte le nom de théorème de Jordan. En mathématiques, le théorème de… …   Wikipédia en Français

  • Theoreme de Jordan — Théorème de Jordan La courbe de Jordan (en noir) divise le plan en deux régions : un « intérieur » (en bleu) et un « extérieur » (en rose). Ce résultat porte le nom de théorème de Jordan. En mathématiques, le théorème de… …   Wikipédia en Français

  • Théorème de Jordan — En mathématiques, le théorème de Jordan est un théorème de topologie plane. Il est célèbre par le caractère apparemment intuitif de son énoncé et la difficulté de sa démonstration. « En fait, il n y a pratiquement aucun autre théorème qui… …   Wikipédia en Français

  • Théorème de Jordan-Brouwer — Théorème de Jordan La courbe de Jordan (en noir) divise le plan en deux régions : un « intérieur » (en bleu) et un « extérieur » (en rose). Ce résultat porte le nom de théorème de Jordan. En mathématiques, le théorème de… …   Wikipédia en Français

  • Théorème de jordan — La courbe de Jordan (en noir) divise le plan en deux régions : un « intérieur » (en bleu) et un « extérieur » (en rose). Ce résultat porte le nom de théorème de Jordan. En mathématiques, le théorème de Jordan est un… …   Wikipédia en Français

  • Mouvement technocratique — Symbole officiel de Technocracy Inc. La monade symbolise l équilibre dynamique. Le mouvement technocratique est un mouvement social promouvant un ordre social technocratique, qui a connu une certaine importance et notoriété dans les années 1930… …   Wikipédia en Français

  • Technocratie — Pour les articles homonymes, voir Technocratie (homonymie). Types de gouvernements Cette série fait partie des séries sur la politique Liste de formes de gouvernements A …   Wikipédia en Français

  • MODE (sociologie) — Le français, et diverses autres langues avec lui, désigne par le terme de mode à la fois les canons périodiquement changeants de l’élégance vestimentaire et, plus généralement, les phénomènes d’engouement qui règnent sur le vêtement, mais… …   Encyclopédie Universelle

  • Institutionnalisme Américain — L institutionnalisme est un courant de pensée économique qui a émergé aux États Unis au début du XXe siècle, sous l impulsion principalement des écrits de Thorstein Veblen, John Rogers Commons et Wesley Clark Mitchell. Il se concentre sur la …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”