Recursive Linear Orderings

Resume Dans ce bref discours sur les chaines recursives, je voudrais vous presenter certaines questions qu'on se pose et vous donner un echantillon des methodes et techniques qu'on emploie pour repondre a ces questions. Le contexte de ce discours est fourni par la question generale suivante: Etant donne in theoreme combinatoire concernant les chaines, est-il vrai effectivement? Si non, comment peut-on mesurer l'effectivite du resultat? Un exemple de theoreme combinatoire vrai effectivement est le resultat de Cantor selon lequel toute chaine denombrable est isomorphe a un sous-ensemble des nombres rationnels. On peut modifier la demonstration standard de ce resultat pour decrire un algorithme qui produit le theoreme suivant: Toute chaine recursive est recursivement isomorphe a un sousensemble recursif des nombres rationnels. Remarquez que tout emploi du mot “recursif” doit ětre precisement defini; ainsi par exemple, la phrase “chaine recursive” entraine l'existence d'un algorithme au moyen duquel on peut determiner si a ≤ b ou non, et la phrase “recursivement isomorphe” entraine l'existence d'un algorithme au moyen duquel on peut calculer les valeurs de la fonction. Dans l'exemple que j'ai cite ci-dessus, la demonstration traditionnelle peut ětre effectivisee; il y a des exemples ou cela n'est pas possible. Dans ces cas-la on doit ou fabriquer un nouvel algorithme ou demontrer qu'il n'existe pas d'algorithme convenable. Par exemple, la demonstration standard que tout ensemble bien ordonne a une extension lineaire bien ordonnee ne peut pas s'effectiviser. Cependant, un autre algorithme, que j'ai decrit avec H. Kierstead, demontre que: Tout ensemble bien ordonne qui est recursif a une extension lineaire qui est bien ordonnee et recursive. La question de savoir si tout ensemble ordonne qui est disperse et recursif a une extension lineaire qui est dispersee et recursive reste ouverte. Il n'y a pas toujours une maniere unique d'effectiviser une formulation combinatoire. Par exemple, une autre maniere d'approcher l'exemple mentionne cidessus est de demander si tout ensemble ordonne qui est recursif et recursivement bien ordonne a une extension lineaire qui est recursive et recursivement bien ordonnee. (“Recursivement bien ordonne” signifie que l'ensemble ordonne n'a aucune suite infinie recursive qui soit decroissante). Cette approche mene plutot a une solution negative, due a moi-měme et a R. Statman: Il existe un ensemble ordonne qui est recursif et recursivement bien ordonne, mais qui n'a pas d'extension lineaire qui soit recursive et recursivement bien ordonnee. Apres avoir introduit la hierarchie arithmetique de Kleene, nous repondons a 1'autre moitie de la question generale: Etant donne un ensemble ordonne qui est recursif et recursivement bien ordonne, quelle complexite l'extension lineaire desiree doit-elle posseder ? Tout ensemble ordonne qui est recursif est recursivement oedonne a une extenaion lineaire qui est recursivement bien ordonnee et est situee au niveau Δ 2 dans la hierarchie arithmetique de Kleene. La demonstration de ce theoreme est un exemple de l'utilisation des “argumentations diagonales” dans la theorie de la recursivite. Les versions effectives de quelques autres resultats combinatoires sont discutees dans 1'article y compris le theoreme de Dushnik et Miller selon lequel toute chaine denombrable peut s'abriter dans un sous-ensemble propre d'elle-měme. Ces sujets sont discutes a fond dans mon livre Linear Orderings (Academic Press, 1982) dans le chapitre intitule, comme on peut s'y attendre, Linear Orderings and Recursion Theory.