scientific article; zbMATH DE number 3557777
The notion of primitive recursive functions on ordinal numbers (PRO) is a natural generalisation of that on natural numbers. The generalisation consists in taking all ordinal numbers as primitives and taking \(f(\lambda)\) to be the \(\sup_{\xi <\lambda} f(\xi)\) for the primitive recursion schema at a limit stage \(\lambda\). An ordinal number \(\alpha\) is called closed if the values of any PRO on ordinals less than \(\alpha\) are also less than \(\alpha\), and a subset of \(\alpha\) is called a basis if the segment \([0,\alpha)\) is generated from that set by means of PROs. (Thus the situation on the natural numbers may be expressed as: \(\omega\) is closed, and \(\{0\}\) is a basis of it.) The main results of this paper consist in determining all closed ordinals, and in giving their bases. (Are they minimal bases? -- whatever `minimal' should mean!). The author also shows that all arithmetical functions (in the sense of [\textit{K. Gödel}, Monatsh. Math. Phys. 38, 173--198 (1931; Zbl 0002.00101; JFM 57.0054.02)]) are definable in terms of PRO based on the set \(\{0,\omega\}\), hence the class of all PROs loses the notion of computability. The exposition of this paper is very clear, although it is extremely formal (even including semantical meanings), as is the wont of the author. There is no reference, bibliography, or mention of any relevant work, which is a pity for such an interesting and fundamental paper as this.
- A new system of proof-theoretic ordinal functions
- Self-monitoring machines and an \(\omega^ \omega\) hierarchy of loops
- Recursion on generalized computable ordinals
- scientific article; zbMATH DE number 440486
- scientific article; zbMATH DE number 3983154
- scientific article; zbMATH DE number 1215495
- Undecidable complexity statements in -arithmetic
- scientific article; zbMATH DE number 1390019
- A complete characterization of primitive recursive intensional behaviours
- scientific article; zbMATH DE number 4019039 (Why is no real title available?)
- Über die mit dem Bar-Rekursor vom Typ 0 definierbaren Ordinalzahlen
- scientific article; zbMATH DE number 19776 (Why is no real title available?)
- How is it that infinitary methods can be applied to finitary mathematics? Gödel's T: a case study
- Unary primitive recursive functions
- Term rewriting theory for the primitive recursive functions
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4133625)