×

Les premiers récursivement inaccessible et Mahlo et la théorie des dilatateurs. (French) Zbl 0556.03043

Dilators were first connected with generalized recursion over successor admissibles: if f is a function which is \(\Sigma^ 1\) over \(L_{\alpha^+}\) then there is a recursive dilator D such that: \(\forall x (\alpha \leq x<\alpha^+\to f(x)<D(x))\). The value of such results (true for cofinally many \(\alpha\) ’s in the first stable ordinal) lies in a reduction of generalized recursion to usual recursion. The paper gives a generalization of such boundedness results in the case of two typical non-successor admissibles: the first recursively inaccessible (case already solved by Girard and Normann), and the first recursively Mahlo. Using proof-theoretic methods, it is shown that \(\Sigma^ 1\) functions over such admissibles can be bounded by means of hierarchies indexed by recursive dilators. The main difference with the original results for successors, is that the hierarchies make use of the oracle \(\Xi_ 1\), the sum of all recursive dilators. (For reasonably small admissibles, \(\alpha^+=\Xi_ 1(\alpha)\), i.e. the oracle can be viewed as the function giving the next admissible.)

MSC:

03F10 Functionals in proof theory
03F15 Recursive ordinals and ordinal notations
03D60 Computability and recursion theory on ordinals, admissible sets, etc.
03F05 Cut-elimination and normal-form theorems
03D65 Higher-type and set recursion theory
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] Bachmann, H.: Die Normalfunktionen und das Problem der ausgezeichneten Folgen von Ordinalzahlen. Vierteljahresschrift der Naturforschenden Gesellschaft in ZürichXCV, 115–117 (1950). · Zbl 0041.02103
[2] Girard, J.Y.:{\(\Pi\)} 2 1 -Logic. Part 1: Dilators. Ann. Math. Logic21, 75–219 (1981). Amsterdam: North-Holland 1981. · Zbl 0496.03037 · doi:10.1016/0003-4843(81)90016-4
[3] Girard, J.Y.: A survey of{\(\Pi\)} 2 1 -logic. Dans: Pfeiffer, H., Los, J., Cohen, L.J. (eds.): Logic, methodology, and philosophy of science, Vol. VI. Amsterdam: North-Holland (1982).
[4] Girard, J.Y.: Proof theory and logical complexity. Bibliopolis. Napoli (a paraître). · Zbl 0635.03052
[5] Girard, J.Y., Norman, D.: Set recursion and{\(\Pi\)} 2 1 -logic. Ann. Math. Logic (a paraître).
[6] Girard, J.Y., Ressayre, J.P.: A paraître dans: Proceedings of the A.M.S. Conference in recursion theory (1982).
[7] Masseron, M.: Majoration des fonctions{\(\omega\)} 1 CK -récursives par des échelles. Thèse de 3ième cycle. Université Paris-Nord (Fev. 1980).
[8] Ressayre, J.P.: Bounding generalized recursive functions of ordinals by effective functors; a complement to the Girard theorem. Dans: Stern, J. (ed.): Proc. of the Herbrand Symposium. Logic Colloquium ’81. Amsterdam: North-Holland 1981. · Zbl 0513.03020
[9] Vauzeilles, J.: Dilators and gardens. Dans: Stern. J. (ed.): Proc. of the Herbrand Symposium. Logic Colloquium ’81. Amsterdam: North-Holland 1981. · Zbl 0568.03029
[10] Van de Wiele, J.: Recursive dilators and generalized recursions: Dans: Stern. J. (ed.): Proc of the Herbrand Symposium. Logic Colloquium ’81. Amsterdam: North-Holland 1981. · Zbl 0499.03035
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.