Hostname: page-component-78c5997874-m6dg7 Total loading time: 0 Render date: 2024-11-16T17:03:16.893Z Has data issue: false hasContentIssue false
  • English
  • Français

Normal functions and constructive ordinal notations

Published online by Cambridge University Press:  12 March 2014

Larry W. Miller
Larry W. Miller*
Affiliation:
Tulane University, New Orleans, Louisiana 70118
Get access Rights & Permissions [Opens in a new window]

Extract

An r-normal function is a strictly increasing continuous function from r to r where r is a regular ordinal > ω (identify an ordinal with the set of smaller ordinals). Given an r-normal function f one can form a sequence {f(x, −)} x<r of r-normal functions—the Veblen hierarchy [33] on f—as follows: f(0, −) = f and, for x > 0, f(x, −) enumerates in order {z ∣ f(y, z) = z for all y < x}, the common fixed points of the f(y, −)'s for y < x. In this paper we give as readable an exposition as we can of Veblen hierarchies and of Bachmann's and Isles's techniques in [3] and [15] of using higher finite number classes for forming sequences {f(x, −)} x<y where y > r of r-normal functions which extend the Veblen hierarchy on f. We will show how these sequences—Bachmann hierarchies—yield extremely natural constructive notations for ordinals in various initial segments of the second number class. We will also consider various other techniques for obtaining constructive ordinal notations and relate them to the notations obtained by Bachmann's and Isles's techniques. In particular, we will use these notations to characterize as directly and as usefully as we can various of Takeuti's systems of constructive ordinal notations, which he calls ordinal diagrams ([31], [32]).

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 41 , Issue 2 , June 1976 , pp. 439 - 459
Copyright
Copyright © Association for Symbolic Logic 1976

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1] Ackermann, W., Konstruktiver Aufbau eines Abschnittes der zweiten Cantorschen Zahlenklasse, Mathematische Zeitschrift, vol. 53 (1951), pp. 403–413.CrossRefGoogle Scholar
[2] Aczel, P., Describing ordinals using functionals of transfinite type, this Journal, vol. 37 (1972), pp. 35–47.Google Scholar
[3] Bachmann, H., Die Normalfunktionen und das Problem der ausgezeichneten Folgen von Ordnungszahlen, Vierteljahrsschrift der Naturforschenden Gesellschaft in Zurich, vol. 95 (1950), pp. 115–147.Google Scholar
[4] Bachmann, H., Transfinite Zahlen, 2nd. ed., Springer-Verlag, Berlin, 1967.CrossRefGoogle Scholar
[5] Church, A., Alternatives to Zermelo's assumption, Transactions of the American Mathematical Society, vol. 29 (1927), pp. 178–208.Google Scholar
[6] Feferman, S., Systems of predicative analysis, this Journal, vol. 29 (1964), pp. 1–30.Google Scholar
[7] Feferman, S., Systems of predicative analysis. II: Representations of ordinals, this Journal, vol. 33 (1968), pp. 193–220.Google Scholar
[8] Feferman, S., Hereditarily replete functionals over the ordinals, Intuitionism and proof theory, North-Holland, Amsterdam, 1970, pp. 289–301.Google Scholar
[9] Feferman, S., Formal theories for transfinite iterations of generalized inductive definitions and some subsystems of analysis, Intuitionism and proof theory, North-Holland, Amsterdam, 1970, pp. 303–326.Google Scholar
[10] Gerber, H., An extension of Schütte's Klammersymbols, Mathematische Annalen, vol. 174 (1967), pp. 203–216.CrossRefGoogle Scholar
[11] Gerber, H., Brouwer's bar theorem and a system of ordinal notations, Intuitionism and proof theory, North-Holland, Amsterdam, 1970, pp. 327–338.Google Scholar
[12] Gerber, H., A system of ordinal notations based on normal functionals of finite type (unpublished).Google Scholar
[13] Hardy, G., A theorem concerning the infinite cardinal numbers, The Quarterly Journal of Pure and Applied Mathematics, vol. 35 (1903), pp. 87–94.Google Scholar
[14] Howard, W., A system of abstract constructive ordinals, this Journal, vol. 37 (1972), pp. 355–374.Google Scholar
[15] Isles, D., An extension of Bachmann's sequence of normal functions, 1967 (unpublished).Google Scholar
[16] Isles, D., Regular ordinals and normal forms, Intuitionism and proof theory, North-Holland, Amsterdam, 1970, pp. 339–361.Google Scholar
[17] Isles, D., Natural well-orderings, this Journal, vol. 36 (1971), pp. 288–300.Google Scholar
[18] Kino, A., On ordinal diagrams, Journal of the Mathematical Society of Japan, vol. 13 (1961), pp. 346–356.Google Scholar
[19] Levitz, H., On the ordinal notations of Schütte and the ordinal diagrams of Takeuti, Ph.D. Thesis, Pennsylvania State University, 1965.Google Scholar
[20] Levitz, H., On the relationship between Takeuti's ordinal diagrams O(n)) and Schütte's system of ordinal notations Σ(n), Intuitionism and proof theory, North-Holland, Amsterdam, 1970, pp. 377–405.Google Scholar
[21] Levitz, H., A simplification of Takeuti's ordinal diagrams of finite order, Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 15 (1969), pp. 141–154.CrossRefGoogle Scholar
[22] Pfeiffer, H., Ausgezeichnete Folgen für gewisse Abschnitte der zweiten und weiterer Zahlklassen, Ph.D. Thesis, Technischen Hochschule Hannover, 1964.Google Scholar
[23] Pfeiffer, H., Über zwei Bezeichnungssysteme für Ordinalzahlen (unpublished).Google Scholar
[24] Quigley, F., Manual of axiomatic set theory, Meredith, New York, 1970.Google Scholar
[25] Schütte, K., Kennzeichnung von Ordnungszahlen durch rekursiv erklärte Funktionen, Mathematische Annalen, vol. 127 (1954), pp. 15–32.CrossRefGoogle Scholar
[26] Schütte, K., Predicative well-orderings, Formal systems and recursive functions, North-Holland, Amsterdam, 1965, pp. 279–302.Google Scholar
[27] Schütte, K., Neuere Ergebnisse der Beweistheorie, Proceedings of the International Congress of Mathematics (Moscow 1966), ed. Petrovsky, I. G., Moscow, 1968, pp. 130–138.Google Scholar
[28] Schütte, K., Ein konstruktives System von Ordinalzahlen, Archiv für Mathematische Logik und Grundlagenforschung, vol. 11 (1968), pp. 126–137, and vol. 12 (1969), pp. 3–11.CrossRefGoogle Scholar
[29] Sierpinski, W., Cardinal and ordinal numbers, 2nd. ed., Warsaw, 1965.Google Scholar
[30] Simauti, T., A note on the construction of ordinal numbers, Commentarii mathematici Universitatis Sancti Pauli, vol. 12 (1963), pp. 37–39.Google Scholar
[31] Takeuti, G., Ordinal diagrams, Journal of the Mathematical Society of Japan, vol. 9 (1957), pp. 386–394.CrossRefGoogle Scholar
[32] Takeuti, G., Ordinal diagrams. II, Journal of the Mathematical Society of Japan, vol. 12 (1960), 389–391.CrossRefGoogle Scholar
[33] Veblen, O., Continuous increasing functions of finite and transfinite ordinals, Transactions of the American Mathematical Society, vol. 9 (1908), pp. 280–292.Google Scholar
[34] Zucker, J., Proof theoretic studies of systems of iterated inductive definitions and subsystems of analysis, Ph.D. Thesis, Stanford University, 1971.Google Scholar
[35] Bridge, J., A simplification of the Bachmann method for generating large countable ordinals, this Journal, vol. 40 (1975), pp. 171–185.Google Scholar