Universal functions and \(\Sigma_\omega \)-bounded structures. (English. Russian original) Zbl 1515.03195
Algebra Logic 60, No. 2, 139-153 (2021); translation from Algebra Logika 60, No. 2, 210-230 (2021).
Summary: We introduce the notion of a \(\Sigma_\omega \)-bounded structure and specify a necessary and sufficient condition for a universal \(\Sigma \)-function to exist in a hereditarily finite superstructure over such a structure, for the class of all unary partial \(\Sigma \)-functions assuming values in the set \(\omega\) of natural ordinals. Trees and equivalences are exemplified in hereditarily finite superstructures over which there exists no universal \(\Sigma \)-function for the class of all unary partial \(\Sigma \)-functions, but there exists a universal \(\Sigma \)-function for the class of all unary partial \(\Sigma \)-functions assuming values in the set \(\omega\) of natural ordinals. We construct a tree \(T\) of height 5 such that the hereditarily finite superstructure \(\mathbb{H} (T)\) over \(T\) has no universal \(\Sigma \)-function for the class of all unary partial \(\Sigma \)-functions assuming values 0, 1 only.
MSC:
| 03D60 | Computability and recursion theory on ordinals, admissible sets, etc. |
Keywords:
admissible set; \( \Sigma \)-function; universal \(\Sigma \)-function; hereditarily finite superstructure; treeReferences:
| [1] | Yu. L. Ershov, Definability and Computability, Sib. School Alg. Log. [in Russian], 2nd ed., Ekonomika, Moscow (2000). |
| [2] | Rogers, H., Theory of Recursive Functions and Effective Computability (1967), Maidenhead, Berksh: McGraw-Hill, Maidenhead, Berksh · Zbl 0183.01401 |
| [3] | Rudnev, VA, A universal recursive function on admissible sets, Algebra and Logic, 25, 4, 267-273 (1986) · Zbl 0633.03033 · doi:10.1007/BF01979014 |
| [4] | Yu. L. Ershov, V. G. Puzarenko, and A. I. Stukachev, “ℍ𝔽-computability,” in Computability in Context. Computation and Logic in the Real World, S. B. Cooper and A. Sorbi (Eds.), Imperial College Press, London (2011), pp. 169-242. · Zbl 1260.03086 |
| [5] | Morozov, AS; Puzarenko, VG, Σ-subsets of natural numbers, Algebra and Logic, 43, 3, 162-178 (2004) · Zbl 1115.03051 · doi:10.1023/B:ALLO.0000028930.44605.68 |
| [6] | Kalimullin, IS; Puzarenko, VG, Computability principles on admissible sets, Mat. Trudy, 7, 2, 35-71 (2004) · Zbl 1095.03029 |
| [7] | Puzarenko, VG, Computability in special models, Sib. Math. J., 46, 1, 148-165 (2005) · Zbl 1095.03030 · doi:10.1007/s11202-005-0016-z |
| [8] | Khisamiev, AN, On a universal Σ-function over a tree, Sib. Math. J., 53, 3, 551-553 (2012) · Zbl 1250.03072 · doi:10.1134/S0037446612020358 |
| [9] | Khisamiev, AN, Universal functions and KΣ-structures, Sib. Math. J., 61, 3, 552-562 (2020) · Zbl 1481.03039 · doi:10.1134/S0037446620030192 |
| [10] | Khisamiev, AN, Σ-bounded algebraic systems and universal functions. I, Sib. Math. J., 51, 1, 178-192 (2010) · Zbl 1208.03048 · doi:10.1007/s11202-010-0019-2 |
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.
