×

Natural well-orderings. (English) Zbl 0634.03055

This is an expository essay on constructive well-orderings and ordinal notation systems, in chronological order. There are no formally stated theorems or proofs; but the major ideas and results are discussed very nicely. It starts with Hardy’s and Veblen’s papers (1904 and 1908, respectively). There, main tools, derivation \([=\) fixed points] and (transfinite) iteration, are explained. After the Church-Kleene notational system (mid 1930’s), Schütte’s ‘Klammersymbols’ (ca. 1955) are expounded. Then, many pages are devoted to the Bachmann hierarchy (that uses uncountable ordinals as subscripts to describe ” small ” countable ordinals), and its extensions and modifications by many people, including Aczel and Feferman (about 1950-1980). The last topic is dilators and category theoretical approaches of the late 1970’s on (Girard et al.). Ordinal diagrams are mentioned but not explained, because applications of constructive orderings to proof theory are not the authors’ concern. As to the meaning of the title of the paper, they say in the Introduction: ”Unfortunately we can only give a rather unsatisfying and imprecise answer...”. In Some Conclusions, they argue that there may not be one underlying notion ( = ” natural ” well- orderings) corresponding to various characterizations and constructions (that are explained in the main text), in contrast to the notion of computability. An extensive bibliography is included.
Reviewer: M.Yasuhara

MSC:

03F15 Recursive ordinals and ordinal notations
03E10 Ordinal and cardinal numbers
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] W. Ackermann [1950] Konstruktiver Aufbau eines Abschnitts der zweiten Cantorschen Zahlenklasse. Math. Zeit.53 (1950) 403–413. · Zbl 0042.05004 · doi:10.1007/BF01175640
[2] P. H. G. Aczel [1966] Mathematical problems in logic. D. Phil. thesis, Oxford.
[3] [1967] Normal functors on linear orderings. (Abstract) J. Symbolic Logic32 (1967) 430. · doi:10.2307/2270848
[4] [1969] A new approach to the Bachmann method for describing countable ordinals. (Preliminary summary) (Unpublished).
[5] [1972] Describing ordinals using functionals of transfinite type. J. Symbolic Logic37 (1972) 35–47. · Zbl 0264.02025 · doi:10.2307/2272543
[6] H. Bachmann [1950] Die Normalfunktionen und das Problem der ausgezeichneten Folgen von Ordnungszahlen. Vierteljahresschr. Naturforsch. Ges. Zürich95 (1950) 115–147. · Zbl 0041.02103
[7] [1952] Vergleich und Kombination zweier Methoden von Veblen und Finsler zur Lösung des Problems der ausgezeichneten Folgen von Ordnungszahlen. Comment. Math. Helv.26 (1952) 55–67. · Zbl 0046.05103 · doi:10.1007/BF02564291
[8] [1954] Normalfunktionen und Hauptfolgen. Comment. Math. Helv.28 (1954) 9–16. · Zbl 0055.04901 · doi:10.1007/BF02566922
[9] [1955]Transfinite Zahlen. Springer, Berlin.
[10] J. E. Bridge [1972] Some problems in mathematical logic. Systems of ordinal functions and ordinal notations. D. Phil. thesis, Oxford.
[11] [1975] A simplification of the Bachmann method for generating large countable ordinals. J. Symbolic Logic40 (1975) 171–185. · Zbl 0309.02027 · doi:10.2307/2271898
[12] [1978] A summary of the literature concerning ordinal notations. (Unpublished)
[13] L. E. J. Brouwer [1918–19] Begründung der Mengenlehre unabhängig vom logischen Satz vom ausgeschlossenen Dritten. Reprinted inCollected works (Ed: A. Heyting, Vol. I [150]–[221]. · JFM 46.0310.06
[14] W. Buchholz [1974] Rekursive Bezeichnungssysteme für Ordinalzahlen auf der Grundlage der Feferman-Aczelschen Normalfunktionen{\(\Theta\)} {\(\alpha\)}. Dissertation, Munich.
[15] [1975] Normalfunktionen und konstruktive Systeme von Ordinalzahlen.Proof theory symposium, Kiel 1974, pp. 4–25, Lecture Notes in Mathematics, 500, Springer, Berlin.
[16] [1976] Über Teilsysteme von \(\bar \theta (\{ g\} )\) . Arch. Math. Logik Grundlag.18 (1976) 85–98. · Zbl 0366.02017 · doi:10.1007/BF02007261
[17] [1982] Collapsing functions. (Preprint)
[18] [1986] A new system of proof theoretic ordinal functions. Ann. Pure Appl. Logic32 (1986) 195–207. · Zbl 0655.03038 · doi:10.1016/0168-0072(86)90052-7
[19] [198?] An independence result for ({\(\Pi\)} 1 1 -CA) + BI. To appear in Ann. Pure Appl. Logic. · Zbl 0636.03052
[20] W. Buchholz, S. Feferman, W. Pohlers, and W. Sieg [1981]Iterated inductive definitions and subsystems of analysis: Recent prooftheoretical studies. Lecture Notes in Mathematics, 897, Springer, Berlin. · Zbl 0489.03022
[21] W. Buchholz and W. Pohlers [1978] Provable well-orderings of formal theories for transfinitely iterated inductive definitions. J. Symbolic Logic43 (1978) 118–125. · Zbl 0411.03046 · doi:10.2307/2271954
[22] W. Buchholz and K. Schütte [1976] Die Beziehungen zwischen den Ordinalzahlsystemen{\(\Sigma\)} und \(\bar \theta (\omega )\) . Arch. Math. Logik Grundlag.17 (1976) 179–189. · Zbl 0339.02027 · doi:10.1007/BF02276806
[23] [1983] Ein Ordinalzahlensystem für die beweistheoretische Abgrenzung der {\(\Pi\)} 1 1 -Separation und Bar-Induktion. Bayer. Akad. Wiss. Math.-Nature. Kl.1983, 99–132. · Zbl 0573.03028
[24] A. Church [1927] Alternatives to Zermelo’s assumption. Trans. Amer. Math. Soc.29 (1927) 178–208. · JFM 53.0170.05
[25] A. Church and S. C. Kleene [1937] Formal definitions in the theory of ordinal numbers. Fund. Math.28 (1937) 11–21. · Zbl 0016.00201
[26] E. A. Cichon and S. S. Wainer [1983] The slow-growing and Grzegorczyk hierarchies. J. Symbolic Logic48 (1983) 399–408. · Zbl 0567.03020 · doi:10.2307/2273557
[27] J. N. Crossley [1965] Constructive order types I.Formal systems and recursive functions (Eds: J.N. Crossley and M.A.E. Dummett), pp. 189–264, North-Holland, Amsterdam.
[28] [1969]Constructive order types. North-Holland, Amsterdam.
[29] [1980]The emergence of number. Upside Down A Book Co., Steel’s Creek, Victoria, Australia 3775.
[30] J. N. Crossley, A. B. M. Manaster, and M. Moses [1986] Recursive categoricity and recursive stability. Ann. Pure Appl. Logic31 (1986) 191–204. · Zbl 0605.03023 · doi:10.1016/0168-0072(86)90070-9
[31] J. N. Crossley and R. J. Parikh [1963] On isomorphisms of recursive well-orderings. (Abstract) J. Symbolic Logic28 (1963) 308.
[32] J. N. Crossley and K. Schütte [1966] Non-uniqueness at {\(\omega\)}2 in Kleene’s . Arch. Math. Logik Grundlag.9 (1966) 95–101. · Zbl 0192.05501 · doi:10.1007/BF01973029
[33] R. Dedekind [1888] Was sind und was sollen die Zahlen? English translation in: R. Dedekind,Essays on the theory of numbers (translated by W. Berman), Dover, New York, 1963. · JFM 20.0049.05
[34] A. Denjoy [1946–54]L’énumération transfinie. 4 volumes. Gauthier-Villars, Paris.
[35] E. C. Dennis-Jones and S. S. Wainer [1984] Subrecursive hierarchies via direct limits.Computation and proof theory, pp. 117–128. Lecture Notes in Mathematics, 1104, Springer, Berlin.
[36] H. C. Doets [1970] A generalization in the theory of normal functions. Z. Math. Logik Grundlag. Math.16 (1970) 389–392. · Zbl 0208.01701 · doi:10.1002/malq.19700160704
[37] S. Feferman [1964] Systems of predicative analysis. J. Symbolic Logic29 (1964) 1–30. · Zbl 0134.01101 · doi:10.2307/2269764
[38] [1968] Systems of predicative analysis II: Representations of ordinals. J. Symbolic Logic33 (1968) 193–220. · Zbl 0162.02201 · doi:10.2307/2269866
[39] [1970] Hereditarily replete functionals over the ordinals. In Kino et al. [1970], pp. 289–301.
[40] [1972] Infinitary properties, local functors, and systems of ordinals functions.Conference in mathematical logic – London ’70, pp. 63–97, Lecture Notes in Mathematics, 255, Springer, Berlin.
[41] [1981] Preface: How we got from there to here. In Buchholz et al. [1981], pp. 1–15.
[42] [198?] Proof theory: A personal report. (Preprint)
[43] P. Finsler [1951] Eine transfinite Folge arithmetischer Operationen. Comment. Math. Helv.25 (1951) 75–90. · Zbl 0042.28002 · doi:10.1007/BF02566448
[44] H. Gaifman [1967] A generalization of Mahlo’s method for obtaining large cardinal numbers. Israel J. Math.5 (1967) 188–199. · Zbl 0207.30301 · doi:10.1007/BF02771107
[45] [1967a] Uniform extension operators for models and their applications.Sets, models and recursion theory (Ed: J.N. Crossley), pp. 122–155, North-Holland, Amsterdam.
[46] H. Gerber [1967] An extension of Schütte’s Klammersymbols. Math. Ann.174 (1967) 203–216. · Zbl 0162.01901 · doi:10.1007/BF01360719
[47] [1970] Brouwer’s bar theorem and a system of ordinal notations. In Kino et al. [1970], pp. 327–338.
[48] J.-Y. Girard [1977] Functionals and ordinoids.Colloque International de Logique (Clermont-Ferrand, 1975), pp. 59–71, CNRS, Paris.
[49] [1981]{\(\Pi\)}1/2-logic. Part I: Dilators. Ann. Math. Logic21 (1981) 75–219. · Zbl 0496.03037 · doi:10.1016/0003-4843(81)90016-4
[50] [1982] A survey of{\(\Pi\)}1/2-logic.Logic, methodology and philosophy of science VI (Hannover, 1979), pp. 89–107, North-Holland, Amsterdam.
[51] [1985] Introduction to{\(\Pi\)}1/2-logic. Synthese62 (1985) 191–216. · Zbl 1069.03503 · doi:10.1007/BF00486046
[52] J.-Y. Girard and J. P. Ressayre [1985] Eléments de logique{\(\Pi\)}1/n.Symposia in Pure Math. 42, pp. 389–445, Amer. Math. Soc., Providence, RI. · doi:10.1090/pspum/042/791069
[53] J.-Y. Girard and J. Vauzeilles [1984] Functors and ordinal notations I: A functorial construction of the Veblen hierarchy. J. Symbolic Logic49 (1984) 713–729. · Zbl 0568.03027 · doi:10.2307/2274127
[54] [1984a] Functors and ordinal notations II: A functorial construction of the Bachmann hierarchy. J. Symbolic Logic49 (1984) 1079–1114. · Zbl 0568.03028 · doi:10.2307/2274263
[55] [1984b] Les premiers recursivement inaccessible et Mahlo et la théorie des dilatateurs. Arch. Math. Logik Grundlag.24 (1984) 167–191. · Zbl 0556.03043 · doi:10.1007/BF02007148
[56] A. Grzegorczyk [1953] Some classes of recursive functions. Rozprawy Mat. No. 4. · Zbl 0052.24902
[57] G. H. Hardy [1904] A theorem concerning the infinite cardinal numbers. Quarterly J. Math.35 (1904) 87–94. · JFM 34.0077.02
[58] W. A. Howard [1972] A system of abstract constructive ordinals. J. Symbolic Logic37 (1972) 355–374. · Zbl 0264.02026 · doi:10.2307/2272979
[59] D. Isles [1970] Regular ordinals and normal forms. In Kino et al. [1970], pp. 339–361. · Zbl 0206.28302
[60] [1971] Natural well-orderings. J. Symbolic Logic36 (1971) 288–300. · Zbl 0278.02030 · doi:10.2307/2270263
[61] G. Jäger [1983] A well-ordering proof for Feferman’s theoryT 0. Arch. Math. Logik Grundlag.23 (1983) 65–77. · Zbl 0511.03025 · doi:10.1007/BF02023014
[62] [1984] -inaccessible ordinals, collapsing functions and a recursive notation system. Arch. Math. Logik Grundlag.24 (1984) 49–62. · Zbl 0545.03031 · doi:10.1007/BF02007140
[63] [1985] Countable admissible ordinals and dilators. (Preprint)
[64] G. Jäger and W. Pohlers [1983] Eine beweistheoretische Untersuchung von ({\(\Delta\)}1/2-CA) + (BI) und verwandter Systeme. Bayer. Akad. Wiss. Math.-Natur. Kl.1982, 1–28. · Zbl 0526.03035
[65] A. Kino, J. Myhill, and R. E. Vesley (Eds.) [1970]Intuitionism and Proof theory. Proceedings of the summer conference. Buffalo, New York, 1968. North-Holland, Amsterdam. · Zbl 0195.01201
[66] J. E. Kister (see J. E. Bridge)
[67] S. C. Kleene [1938] On notation for ordinal numbers. J. Symbolic Logic3 (1938) 150–155. · Zbl 0020.33803 · doi:10.2307/2267778
[68] [1955] On the forms of predicates in the theory of constructive ordinals (second paper). Amer. J. Math.77 (1955) 405–428. · Zbl 0067.25203 · doi:10.2307/2372632
[69] G. Kreisel [1965] Mathematical logic. InLectures in modern mathematics, Vol. III (Ed: T.L. Saaty), pp. 95–195, Wiley, New York.
[70] H. Levitz [1965] On the ordinal notations of Schütte and the ordinal diagrams of Takeuti. Ph.D. thesis, Penn. State University.
[71] [1966] Über die Finslerschen höheren arithmetischen Operationen. Comment. Math. Helv.41 (1966) 273–286. · Zbl 0147.25104 · doi:10.1007/BF02566881
[72] [1969] A simplification of Takeuti’s ordinal diagrams of finite order. Z. Math. Logik Grundlag. Math.15 (1969) 141–154. · Zbl 0196.01403 · doi:10.1002/malq.19690150708
[73] [1969a] On the Finsler and Doner-Tarski arithmetical hierarchies. Comment. Math. Helv.44 (1969) 89–92. · Zbl 0177.01501 · doi:10.1007/BF02564515
[74] [1970] On the relationship between Takeuti’s ordinal diagramsO(n) and Schütte’s system of notations{\(\Sigma\)}(n). In Kino et al. [1970], pp. 377–405.
[75] [1973] A characterization of the Veblen-Schütte functions by means of functionals. Comment. Math. Helv.48 (1973) 382–393. · Zbl 0272.02051 · doi:10.1007/BF02566131
[76] H. Levitz and K. Schütte [1971] A characterization of Takeuti’s ordinal diagrams of finite order. Arch. Math. Logik Grundlag.14 (1971) 75–97. · Zbl 0244.02011 · doi:10.1007/BF01974151
[77] L. W. Miller [1976] Normal functions and constructive ordinal notations. J. Symbolic Logic41 (1976) 439–459. · Zbl 0345.02018 · doi:10.1017/S0022481200051501
[78] Y. N. Moschovakis [1966] Many-one degrees of the predicatesH {\(\alpha\)} (x). Pacific J. Math.18 (1966) 329–342. · Zbl 0147.25203 · doi:10.2140/pjm.1966.18.329
[79] W. Neumer [1953–56] Zur Konstruktion von Ordnungszahlen. Math. Zeit.58 (1953) 391–413; ibid.59 (1953) 434–454; ibid.60 (1954) 1–16; ibid.61 (1954) 47–69; ibid.64 (1956) 435–456. · Zbl 0056.04901 · doi:10.1007/BF01174155
[80] [1957–70] Algorithmen für Ordnungszahlen und Normalfunktionen. Z. Math. Logik Grundlag. Math.3 (1957) 108–150; ibid.6 (1960) 1–65; ibid.16 (1970) 1–112. · Zbl 0082.04403 · doi:10.1002/malq.19570030604
[81] P. Päppinghaus [1985] Ptykes in Gödel’s T und Verallgemeinerte Rekursion über Mengen und Ordinalzahlen. Habilitationsschrift, Hannover. · Zbl 0576.03035
[82] [1985a] A typed {\(\lambda\)}-calculus and Girard’s model of ptykes.Foundations of logic and linguistics: problems and their solutions (Eds: P. Weingartner and G. Dorn), pp. 245–279, Plenum.
[83] J. Pearce [1984] A constructive consistency proof of a fragment of set theory. Ann. Pure Appl. Logic27 (1984) 25–62. · Zbl 0599.03059 · doi:10.1016/0168-0072(84)90034-4
[84] H. Pfeiffer [1964] Ausgezeichnete Folgen für gewisse Abschnitte der zweiten und weiterer Zahlklassen. Dissertation, Hannover.
[85] [1969] Ein Bezeichnungssystem für Ordinalzahlen. Arch. Math. Logik Grundlag.12 (1969) 12–17. · Zbl 0193.31103 · doi:10.1007/BF01982045
[86] [1970] Ein Bezeichnungssystem für Ordinalzahlen. Arch. Math. Logik Grundlag.13 (1970) 74–90. · Zbl 0209.02202 · doi:10.1007/BF01967653
[87] [1972] Vergleich zweier Bezeichnungssysteme für Ordinalzahlen. Arch. Math. Logik Grundlag.15 (1972) 41–56. · Zbl 0278.02029 · doi:10.1007/BF02019775
[88] [1974] Über zwei Bezeichnungssysteme für Ordinalzahlen. Arch. Math. Logik Grundlag.16 (1974) 23–36. · Zbl 0336.02025 · doi:10.1007/BF02025116
[89] W. Pohlers [198?] Ordinal notations based on a hierarchy of inaccessible cardinals. To appear in Ann. Pure Appl. Logic. · Zbl 0656.03038
[90] D. Schmidt [1972] Topics in mathematical logic. Characterisations of small constructive ordinals; constructive finite number classes. D. Phil. thesis, Oxford.
[91] [1975] Bounds for the closure ordinals of replete monotonic increasing functions. J. Symbolic Logic40 (1975) 305–316. · Zbl 0325.02019 · doi:10.2307/2272156
[92] [1976] Built-up systems of fundamental sequences and hierarchies of number theoretic functions. Arch. Math. Logik Grundlag.18 (1976) 47–53; ibid.18 (1976) 145–146. · Zbl 0358.02061 · doi:10.1007/BF02007256
[93] K. Schütte [1954] Kennzeichnung von Ordnungszahlen durch rekursiv erklärte Funktionen. Math. Ann.127 (1954) 15–32. · Zbl 0055.04902 · doi:10.1007/BF01361109
[94] [1960]Beweistheorie. Springer, Berlin. (Completely revised English edition 1977)
[95] [1963] Lecture Notes in Mathematical Logic. Vol. 2. Penn. State University.
[96] [1965] Predicative well-orderings.Formal systems and recursive functions (Eds: J.N. Crossley and M.A.E. Dummett), pp. 280–303, North-Holland, Amsterdam.
[97] [1968–69] Ein konstruktives System von Ordnungszahlen. Arch. Math. Logik Grundlag.11 (1968) 126–137; ibid.12 (1969) 3–11. · Zbl 0193.31102 · doi:10.1007/BF01967820
[98] [1976] Einführung der Normalfunktionen{\(\Theta\)} {\(\alpha\)} ohne Auswahlaxiom und ohne Regularitätsbedingung. Arch. Math. Logik Grundlag.17 (1976) 171–178. · Zbl 0338.02013 · doi:10.1007/BF02276805
[99] J. Stern (Ed.) [1982]Proceedings of the Herbrand Symposium, Logic Colloquium ’81. North-Holland, Amsterdam. · Zbl 0489.00007
[100] M. E. Szabo [1969]The collected papers of Gerhard Gentzen. North-Holland, Amsterdam. · Zbl 0209.30001
[101] G. Takeuti [1957] Ordinal diagrams. J. Math. Soc. Japan9 (1957) 386–394. · Zbl 0079.24410 · doi:10.2969/jmsj/00940386
[102] [1975]Proof theory. North-Holland, Amsterdam.
[103] J. van de Wiele [1982] Recursive dilators and generalized recursions. In J. Stern [1982], pp. 325–332. · Zbl 0499.03035
[104] J. Vauzeilles [1982] Functors and ordinal notations III: Dilators and gardens. In J. Stern [1982], pp. 333–364. · Zbl 0568.03029
[105] [1985] Functors and ordinal notations IV: The Howard ordinal and the functor{\(\Lambda\)}. J. Symbolic Logic50 (1985) 331–338. · Zbl 0621.03036 · doi:10.2307/2274218
[106] O. Veblen [1908] Continuous increasing functions of finite and transfinite ordinals. Trans. Amer. Math. Soc.9 (1908) 280–292. · JFM 39.0102.01 · doi:10.1090/S0002-9947-1908-1500814-9
[107] S. S. Wainer [1985] The ”slow-growing”{\(\Pi\)}1/2 approach to hierarchies.Proc. Symposia in Pure Math. 42, pp. 487–502, Amer. Math. Soc., Providence, RI. · Zbl 0626.03037 · doi:10.1090/pspum/042/791073
[108] [1985a] Subrecursive ordinals.Recursion Theory Week, pp. 405–418, Lecture Notes in Mathematics, 1141, Springer, Berlin.
[109] R. W. Weyrauch [1972] Relations between some-hierarchies of ordinal functions and functionals. Ph. D. thesis, Stanford Univ., California.
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.