LA CLASSE II LEZ

la superposition se poursuit dans le transfini (:), le type « étant, par exemple, caractérisé par (2) :

Po (&) Z II LE) +8 (EE) (0)

Pour atteindre la théorie des ensembles cantorienne il faut, en outre, supposer dans le type 1 non plus une seule, mais autant d'espèces de variables qu’il y a de classes de nombres ordinaux transfinis, chaque classe étant caractérisée par un mode d’engendrement des individus. A la classe I correspond la récurrence ordinaire (axiomes de PEANO et axiome d’induction complète) ; à la classe II la récurrence transfinie sur des individus que caractérisent les axiomes :

Le (0) (xo) Y, (a) + Y, (sa) (x1) (&) | Pi (4) + Pi (a (&)) | + V1 (ma (4)] 72)

(où w., est la caractéristique de la variable de type z ; ®, celle de la variable numérique ordinaire £,, « une expression quelconque). Enfin l’axiome d’induction transfinie (°) :

lab) AÏMmeu+-em)ll-1Ila() (13) Das Li Li

(le signe < représente la relation d’ordination entre les nombres de la classe II, il doit donc lui même être préalablement défini, de même que dans (12) le signe 2»). Est-il possible d’aller plus loin et de régler, à l’intérieur de chaque

(1) D'une façon générale, toute liaison logique établie entre types déjà définis procure un type supérieur. Comme les liaisons n’appartiennent qu'à un nombre fini d'espèces, il y a moyen de bien ordonner les types. (Pour l'étude de fonctions d’entiers, HILBERT n’a besoin que de la liaison introduite par Il). Il n’y a jamais, bien entendu, qu’une infinité dénombrable de types dans un formalisme déterminé : mais l’engendrement transfini dont HizBERT montre le mécanisme, ne peut s’arrêter arbitrairement, V. ci-après, CHAINE:

(2) H1LBERT (XI), p. 184.

(3) Nous prenons des caractères gothiques pour la catégorie de variables

correspondant à la classe II.

J. CA VAILLÈS 8

II8 FONCTIONS RÉCURRENTES

type, les définitions de fonctions ? HILBERT ne s’est occupé que du type 2 : il n’est pas question de lois puisqu'on resterait dans le dénombrable et qu’il y a déjà 2X° fonctions d’entiers. On peut, toutefois, au moins pour une partie importante d’entre elles, uniformiser leur définition grâce à un approfondissement de la notion de récurrence ; celle-ci, puisqu'elle préside à l’engendrement des individus, il est naturel qu’elle permette de dominer au moins en partie les modes de mise en correspondance entre individus. Au sens classique, on appelle fonction récurrente toute fonction + obtenue soit directement par la définition

e (1 G...4,) —= Ÿ NE | a p (SM; M1.) = AIN, 41:24, NN, dr .&y))

(où y et x sont des fonctions récurrentes déjà introduites, 4,.….a, des paramètres, # un nombre), soit par substitution, dans une fonction récurrente connue, d’autres fonctions également connues à la place des variables. Comme point de départ (!) on prend (au lieu de 4 et x) les signes connus o et s. Procédé régulier qui répond exactement aux exigences d’un formalisme (?) (schéma et comme seule opération substitution), mais qui ne permet pas de dépasser le dénombrable, ACKERMANN () a donné l’exemple effectif d’une fonction d’entiers, dont la croissance est supérieure à toute fonction récurrente. Mais la définition classique et le schéma (14) n’épuisent pas la notion de récurrence : on peut

(1) Par exemple, la définition de l’addition : d+0—=a a+sn=s(a+ mn).

(2) V. ci-après, ch. IV.

(3) ACKERMANN (II), p. 118, c’est la fonction 9 (a, b, c) égale à & + b pour b ‘ be Ci— "0, aa. bipour cr aa (avec n—2 exposants égaux à b superposés) pour c — #.La démonstration d'ACKERMANN a été depuis simplifiée dans deux He de R. PÉTER (1), p. 612 et (IL), p. 43.

FONCTIONS RÉCURRENTES 119

établir d’autres modes réglés de construction progressive au moyen d'opérations connues des valeurs d’une fonction (récurrence adhérente, récurrence encastrée, récurrence croisée) (:). La fonction d'ACKERMANN est définie par une récurrence ordinaire à condition d'utiliser (à la place de x dans le schéma (r14)) une fonction de type 3 (2). D'où l’idée que l'intervention des types supérieurs permet à la fois

(1) Classification empruntée à R. PÉTER (I), p. 613. Dans la récurrence adhérente, la valeur + (n + 1) ne dépend pas seulement de + (n) mais d’un certain nombre des valeurs précédentes ® (0), æ (1)... ® (n — 1). Dans la récurrence encastrée, + est fonction aussi des paramètres ; on a, par exemple, le schéma :

p (041 ...ar) = Ÿ (ay... ar) D(n+ I, 4j...) = (M3 y +. Ar, ? (n1 db... br)), les b représentant de nouvelles valeurs des paramètres a, .… a. Enfin, la récurrence croisée (ou multiple) procède suivant deux ou plusieurs variables portantes simultanées, ex. :

(a; 0) =2a+I Ÿ (0, Sn) = y (x, ) Ÿ (sa, sn) = Ÿ (Y (a, sn), n)

R. PÉTER a démontré (oc. cit.) que les fonctions définies au moyen des 2 premières espèces de récurrence appartenaient au système des fonctions récurrentes ordinaires. On peut même considérer pour celles-ci (schéma (14)) un schéma avec un seul paramètre. Au contraire, la récurrence croisée est

irréductible.

(2) I suffit, par exemple, de considérer la fonction de type 3: tx (f (4), b, n) égale à » itérations de la fonction f, avec pour valeur initiale b — on la définit par :

tx (f(x), b, 0) = b tx (/(), b, sn) = f (sx ( (x), 8, n)).

La fonction d’Ackermann s'écrit alors :

o (a, b, 0) = a + b (16) ? (a, b, sn) = 7x (g (a. x, n), a, b) (17)

Avec cependant une exception pour # = 1 (c’est-à-dire s 0) : la 2° équation doit être remplacée par :

p (a, b, 2) = tx ( (a, x, 1), 1, b).

On obtient un schéma général en faisant intervenir des fonctions récurrentes élémentaires telles que l’une y soit toujours nulle sauf si son argument = 1, auquel cas elle prend aussi la valeur 1 et l’autre À faisant l'inverse. Il suffit alors dans (17) de remplacer a par y (x) + a k (n) dans l’argument de tx.

de donner un canon à toutes les variétés de récurrences et d'atteindre la majeure partie — sinon la totalité — des procédés de construction de fonctions d’entiers. HILBERT pose le schéma général :

(où à et g sont des expressions données de types quelconques — et pouvant comporter des paramètres — ; ga deux arguments, le premier de même type que a, le 2€ une variable numérique ; la valeur de 4 a le type de a). Pour un certain choix de g et de a, il y a engendrement réglé de fonctions par substitutions de fonctions déjà introduites aux places vides des arguments. L'unité obtenue ainsi est, sans doute, peu satisfaisante : g et a ne sont pas déterminables à l’avance et sont empruntés à des types supérieurs (par hypothèse encore inexplorés). Mais, d’une part, il semble impossible d’exiger davantage, d’autre part elle procure une suffisante domination de la pensée finie sur le formalisme pour que, grâce à elle, HILBERT puisse esquisser une solution au problème du continu, premier « fruit à quoi reconnaître la valeur de sa théorie » (1).

Le paraliélisme entre la définition progressive des types et l’engendrement des ordinaux de la classe IT est frappant (d’ailleurs marqué par l’utilisation de ces ordinaux comme indices pour les types) : à la substitution d’une variable de type # dans un argument de type # — x (élévation du type d’une unité) correspond l’adjonction + x ; à la réunion de tous les types d’une suite dénombrable satisfaisant à une même condition, en un type immédiatement supérieur (exemple schéma (9)), correspond le passage à la limite. Mais la coordination biunivoque peut être établie entre les fonctions mêmes, définies au moyen de ces types, et les ordi-

(x) Loc. cit., p. 180.

naux. L’engendrement de ceux-ci, en effet, — si on veut le formaliser — exige une récurrence, à la vérité transfinie. Peut-on la ramener (comme les récurrences croisées où la simultanéité des variables exige aussi un passage par le transfini) au schéma (15), en remplaçant les types supérieurs de la variable numérique (dans a et g) par ceux de la variable correspondant à la classe II ? La récurrence serait encore ordinaire (c’est-à-dire non transfinie) puisque le progrès s’effectuerait uniquement par adjonction d’unité (c'est-à-dire la variable « portante » de la récurrence resterait un nombre #) et d'autre part le parallélisme serait complet avec les définitions de fonction, si l’on met en correspondance les types de même hauteur dans les 2 catégories de variables. HILBERT définit ainsi une application : si l’on fixe une borne supérieure pour la hauteur des types employés (dans les deux processus) on ne pourra définir grâce à (15) (et sa transposition pour les constructions d’ordinaux) qu’une infinité dénombrable de nombres ordinaux et de fonctions d’entiers (on peut donner un schéma — déduit de (1x5) — universel pour toutes les définitions ainsi possibles et où intervient un paramètre du type immédiatement supérieur (1) : si on ordonne alors d’après leur hauteur les types dont la substitution est effectivement utilisée, on a une suite dénombrable de systèmes de fonctions, euxmêmes finis et ordonnables d’après le nombre des substitutions utilisées pour chaque fonction). Le procédé de la diagonale permet alors de définir une nouvelle fonction d’entiers, par exemple + (a,) + I si +(a,) est le numérotage

(x) On n’a donc, pour la définition du schéma, à faire intervenir qu’une fonction du type supérieur (ou égal) à la borne posée : pour la détermination de cette fonction, aucune règle n’est donnée; qu’elle soit toujours possible est l'affirmation du lemme II, les fonctions de type > 2 intervenant dans un schéma universel pour une borne quelconque ne seront donc dans chaque type qu’en nombre fini (il est possible que la construction du paramètre en exige plusieurs).

obtenu dans l’ensemble dénombrable précédent, de type immédiatement supérieur et que l’on coordonnera au premier nombre ordinal suivant l’ensemble symétrique des nombres ordinaux (c’est l’élément initial de l’ensemble des ordinaux pour la définition desquels des types supérieurs à la borne posée soient nécessaires). L'application est biunivoque : l’ensemble des fonctions récurrentes (au sens large) a même puissance que la classe IT.

La démonstration est exemple de la manière à la fois dont la théorie cantorienne des ensembles peut être intégrée au formalisme et dont la méthode métamathématique situe et résoud les problèmes. Mais elle n’est pas complète ; dans sa forme : « esquisse qu’il faudrait remanier pour la soumettre aux exigences de la pensée finie » (1). Pour le fond; elle s'appuie sur deux affirmations jusqu'ici non prouvées : d’une part, qu'il n’y a pas plus de fonctions d’entiers que de fonctions récurrentes (au sens large) — ou du moins que le dépassement est sans importance pour la puissance de l’ensemble total ; d’autre part, que la récurrence transfinie est entièrement éliminable. — Plus précisément « si une fonction d’entiers a été construite au moyen d’une récurrence transfinie ou grâce à des types introduits par une telle récurrence... on peut toujours la définir par la récurrence ordinaire, en utilisant exclusivement des types de même origine...» (/emme IT). D'autre part (/emmme 1) «si par l’utilisation de fonctions définies au moyen du symbole e on a pu donner une réfutation formalisée du théorème du continu, ces fonctions peuvent toujours être remplacées dans la démonstration par des fonctions définissables sans e, simplement par récurrence finie ou transfinie de sorte que le transfini n’apparaisse que par les signes > et II ». Il est toujours possible de faire dépendre les valeurs d’une fonction d’entiers de la solution d’un problème encore ouvert : dans la

(1) Zbid., p. 190.

formalisation de la définition de la fonction il faut faire intervenir le symbole +: qui désigne un nombre qu’aucun calcul effectif ne peut procurer (II et > seraient insuffisants puisqu'il faut fixer un individu déterminé). De telles fonctions ne sont évidemment pas récurrentes (au sens large) puisque le propre de la récurrence est de permettre le calcul effectif de la valeur pour chaque argument. Le lemme I n’est qu’une partie (:) — un affaiblissement — d’un «lemme général de la métamathématique : la résolubilité de tout problème mathématique bien déterminé » ; il suffit de situer la question dans son lieu propre — une axiomatique assez puissante — acte de foi en la puissance sans limite des instaurations de formalismes. Toute fonction d’entiers précise est, par essence, calculable : l’axiome d’< n'appartient donc pas à son lieu, le problème du continu doit pouvoir être résolu sans choix.— Quant au lemme II, il exprimedavantage encore : que l'infini des fonctions d’entiers et celui de la classe IT sont assez petits pour être dominés par la récurrence ordinaire (ce qui n’est évidemment pas vrai pour l’in fini des fonctions de variables réelles, par exemple) ; non seulement le mode de démonstration employé l'exige, mais la possibilité même d’une coordination formalisée entre nombres réels et ordinaux de la classe II.

Si aucune possibilité de démonstration n’est apparue pour les deux lemmes, du moins ont-ils provoqué les recherches — déjà citées — sur les définitions de fonction par récurrence et sur l'exploration de la classe IT aumoyÿende la récurrence ordinaire (2). L’esquisse tout entière — outre sa beauté

(1) Le lemme I restreint s'occupe seulement de la réfutation possible : si elle était faite, elle ne pourrait consister que dans la mise en évidence d’un système de fonctions d’entiers non coordonnables aux ordinaux de la classe II (puisque de toutes façons IN, Z No; si le système est déterminé (peut servir dans une démonstration précise), alors on doit se passer d’e dans sa définition.

(2) Travaux non publiés de P. BERNAYS et J. von NEUMANN : ils ont

propre — a l'intérêt d’une première confrontation précise entre théorie cantorienne des ensembles et puissance d’un formalisme rigoureux. Mais ici se produit un phénomène inattendu : la frontière entre mathématique et métamathématique en devient plus floue (alors qu’elle avait été tracée justement à cause de la théorie des ensembles). D'une part, la démonstration même esquissée par HILBERT est métamathématique, alors qu’il s’agit d’un problème mathématique (1) ; on pourrait sans doute y séparer le moment de sifuation du problème (par exemple lemme I) et le moment proprement mathématique (établissement de la correspondance) formalisable dans une théorie plus vaste. Mais, d'autre part, l’édification finie de cette théorie — mise en rapports avec la théorie inférieure — devient un nouveau problème : il suffit de songer à la définition irréductiblement transfinie de la fonction coordonnante (2?) (entre nombres réels et ordinaux de classe IT) et des types correspondants. C’est une difficulté dont les essais de traitement des problèmes spécifiques de la théorie de la démonstration — non contradiction, saturation, résolubilité (c’est-à-dire établissement d’une méthode de décision) — devaient faire apparaître le caractère fondamental. |

réussi à définir par récurrence de schéma (14) et types correspondants appliqués à la variable x le nombre cantorien <, (premier nombre transfini « tel que w%—a) et le premier nombre critique e — cité par BERNAYS (VI), p. 208. (1) Remarqué déjà par ©. BECKER (I). (2) Fonction de la forme € (x, #) où x parcourt tous les nombres de la. classe IT et où # est entier. 7