scientific article; zbMATH DE number 3557777

From MaRDI portal
Publication:4133625





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.











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)