# zbMATH — the first resource for mathematics

Computing and dominating the Ryll-Nardzewski function. (English. Russian original) Zbl 1323.03038
Algebra Logic 53, No. 2, 176-183 (2014); translation from Algebra Logika 53, No. 2, 271-281 (2014).
Summary: For a countably categorical theory T, we study the complexity of computing and the complexity of dominating the function specifying the number of $$n$$-types consistent with T.
##### MSC:
 03C35 Categoricity and completeness of theories 03C57 Computable structure theory, computable model theory 03D45 Theory of numerations, effectively presented structures
Full Text:
##### References:
 [1] Engeler, E, ¨aquivalenzklassen von n-tupeln, Z. Math. Log. Grundl. Math., 5, 340-345, (1959) · Zbl 0092.24903 [2] Ryll-Nardzewski, C, On the categoricity on power $$≤$$ ℵ_{0}, Bull. Acad. Pol. Sci., S’er. Sci. Math. Astron. Phys., 7, 545-548, (1959) · Zbl 0117.01101 [3] Svenonius, L, $$ℵ$$_{0}-categoricity in first-order predicate calculus, Theoria (Lund), 25, 82-94, (1959) [4] Schmerl, JH, A decidable $$ℵ$$_{0}-categorical theory with a non-recursive ryll-nardzewski function, Fund. Math., 98, 121-125, (1978) · Zbl 0372.02025 [5] Khoussainov, B; Montalb’an, A, A computable $$ℵ$$_{0}-categorical structure whose theory computes true arithmetic, J. Symb. Log., 75, 728-740, (2010) · Zbl 1201.03020 [6] Andrews, U, The degrees of categorical theories with recursive models, Proc. Am. Math. Soc., 141, 2501-2514, (2013) · Zbl 1323.03044 [7] W. Hodges, A Shorter Model Theory, Cambridge Univ. Press, Cambridge (1997). · Zbl 0873.03036 [8] C. J. Ash and J. F. Knight, Computable Structures and the Hyperarithmetical Hierarchy, Stud. Log. Found. Math., 144, Elsevier, Amsterdam (2000). · Zbl 0960.03001 [9] Jockusch, CG; McLaughlin, TG, Countable retracing functions and π\^{0}_{2} predicates, Pac. J. Math., 30, 67-93, (1969) · Zbl 0181.30602 [10] Rogers, LA, Ulm’s theorem for partially ordered structures related to simply presented abelian $$p$$-groups, Trans. Am. Math. Soc., 227, 333-343, (1977) · Zbl 0357.20032 [11] Kuznetsov, AV; Trakhtenbrot, BA, Investigation of partial recursive operators by techniques of Baire spaces, Dokl. Akad. Nauk SSSR, 105, 897-900, (1955) · Zbl 0066.26102 [12] Knight, J, Nonarithmetical $$ℵ$$_{0}-categorical theories with recursive models, J. Symb. Log., 59, 106-112, (1994) · Zbl 0804.03021
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.